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.