Longest Valid Parentheses Substring

Given a string s consisting only of the characters ('), your task is to find the length of the longest substring which is a well-formed (valid) parentheses sequence. A valid parentheses sequence is one in which each opening parenthesis has a matching closing parenthesis and the pairs are properly nested.

For example, in the string "(()())", the entire string is a valid sequence and its length is 6, whereas in "))((", there is no valid substring so the answer is 0.

You need to handle multiple test cases. Each test case will be given as a single line string after an initial line containing the number of test cases. Read from standard input and write your answer for each test case to standard output on a separate line.

Note: If there is no valid substring, output 0.

inputFormat

Input is read from standard input. The first line contains an integer T denoting the number of test cases. The next T lines each contain a string s composed only of the characters '(' and ')'.

outputFormat

For each test case, output a single line containing an integer representing the length of the longest valid (well-formed) parentheses substring.

## sample

5
(()())
))((
()(()))))
((()))
()

6
0
6
6
2

</p>