Problem 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.

3
()
((((
(())

1
0
2