Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Pota(t)o

Limits: 1s, 1.0 GB

Every weekend, Potato becomes a couch potato and spends the whole time at home. Now, he got bored of the monotonous pattern and wants to spice things up. He wants to hang out with Tomato.

Tomato, however, is stuck with a problem. She has a string of bracket sequence and she has to find the longest pretty sequence. A pretty sequence is a balanced bracket sequence where 1st half consists of “(” and the remaining half consists of “)”. Potato is too lazy as usual and asked you to solve the problem for him.

Input

The first line contains $T$, the number of test cases. Each of the following $T$ lines contains a bracket sequence $s$ of variable lengths.

Constraints

${1 \leq T \leq 10}$
${2 \leq |s| \leq 10^5}$

Output

Print T integers, is of which is the maximum length of pretty sequence in the ith input string.

Samples

InputOutput
5
)(
()
()(())
)()())
()(()())
0
2
4
2
2

Discussion
Submit

Login to submit