Scaena Felix

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

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.

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.

Sample Input

3 () (((( (())

Sample Output

1 0 2

Hint

hujie

Source

BestCoder Round #57 (div.2)

提交代码