Longest Balanced Parentheses Substring

You are given a string s consisting only of the characters (' and ')'. Your task is to find the length of the longest balanced substring of s. A balanced (or valid) parentheses substring is one where every opening bracket ( is matched with a closing bracket ) in the correct order.

For example, for the string (())) the longest balanced substring is (()) which has a length of 4. Formally, if you use a stack-based approach, whenever you match a pair of parentheses you can compute the current valid substring length using the formula:

$$L = i - j$$

where i is the current index and j is the index of the last unmatched bracket. Use this idea to maintain and update the length of the longest valid substring as you iterate through the string.

inputFormat

The first line of input contains an integer T representing the number of test cases. Each of the following T lines contains a non-empty string s composed solely of the characters (' and ')'.

Note: Some test cases may contain an empty string.

outputFormat

For each test case, output a single integer that represents the length of the longest balanced parentheses substring. Each result should be printed on a new line.

## sample

3
(()))
)((())()
()(())

4
6
6

</p>