Practice on Toph

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

Potato

By prantoran · Limits 1s, 512 MB

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 (1 ≤ T ≤ 10), the number of test cases. Each of the following T lines contains a bracket sequence s (2 ≤ s ≤ 105) of variable lengths.

Output

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

Sample

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

Discussion

Statistics


88% Solution Ratio

fsshakkhorEarliest, Dec '18

Taran106Fastest, 0.0s

fsshakkhorLightest, 262 kB

mdvirusShortest, 198B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.