1704 - 111qqz's match

Time Limit: 1s Memory Limit: 256MB

Submissions: 1 Solved:
Description

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.

Input

The first line of the input is a integer T, meaning that there are TT<=1E5 test cases.

Every test cases contains a parentheses sequence S only consists of '(' and ')'.

1≤|S|≤1,000.

Output

For every test case output the least number of modification.

Sample Input
3
()
((((
(())
Sample Output
1
0
2
Hint
Source
111qqz