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