You are given a string ~s~ that consists of the characters (, ) and ?. Let x be the number of ways to replace the ? characters with ( and ) to form a regular bracket string. Print \min(x, 10).

Remember, a regular bracket string is defined as follows:

• An empty string is a regular bracket string

• If ~s~ is a regular bracket string, ~\texttt{(} + s + \texttt{)}~ is also a regular bracket string

• If ~s_1~ and ~s_2~ are regular bracket strings, ~s_1 + s_2~ is also a regular bracket string

Input

The first line consists of a single integer ~t~ (~1 \le t \le 10^5~), the number of test cases.

Description of each test case follows. Every test case consists of a string ~s~ with length in the range ~[1, 10^5]~.

The total length of the strings never exceeds ~10^5~.

Output

For each test case, print ~\min(x, 10)~, where ~x~ is the number of ways to form a regular bracket string.

Sample Input 1

10
)(??
)(((
())?
))?)
?(?)
?)?(
???)
((?)
)?()
))?(

Sample Output 1

0
0
0
0
1
0
2
1
0
0