Fill in the blanks

View as PDF

Submit solution


Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Authors:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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

Please read the guidelines before commenting.


There are no comments at the moment.