Given a parentheses sequence consist of '(' and ')', a modify can filp a parentheses, changing '(' to ')' or ')' to '('.
If we want every not empty substring 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.
Input
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$.
Output
For every test case output the least number of modification.
