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
Comments