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 ')'.

1≤|S|≤1,000.

For every test case output the least number of modification.

3
()
((((
(())

1
0
2