Time Limit: 1s
Memory Limit: 256MB
111qqz is a cute girl who likes algorithm very much. However,she is so weak that she is always called "cai ji" by god cows in the ACM team of hust. At this time,she falls into trouble again,can you help her?
Here is the problem:Given a string consist of '(' and ')', a flip operation can change '(' to ')' or ')' to '('.
If we want every not empty substring of this string not to be "paren-matching", how many times at least to perform the flip operations?
For example, "()","(())","()()" are "paren-matching" strings, but "((", ")(", "((()" are not.
The first line of the input is a integer T, meaning that there are T（T<=1E5） test cases.
Every test cases contains a parentheses sequence S only consists of '(' and ')'.
For every test case output the least number of modification.
3 () (((( (())
1 0 2