Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
Given a parentheses sequence consist of '(' and ')', a modify can filp a parentheses, changing '(' to ')' or ')' to '('.
If we want every not empty <b>substring</b> of this parentheses sequence not to be "paren-matching", how many times at least to modify this parentheses sequence?
For example, "()","(())","()()" are "paren-matching" strings, but "((", ")(", "((()" are not.
The first line of the input is a integer $T$, meaning that there are $T$ test cases.
Every test cases contains a parentheses sequence $S$ only consists of '(' and ')'.
$1 \leq |S| \leq 1,000$.
For every test case output the least number of modification.
BestCoder Round #57 (div.2)