Longest Valid Parentheses Substring

You are given n strings, each consisting solely of the characters (' and ')'. For each string, your task is to determine the length of the longest contiguous substring which is a balanced sequence of parentheses. A balanced sequence is defined such that every opening parenthesis has a corresponding closing parenthesis in the correct order.

For example, consider the string (()()). The entire string is balanced so its answer is 6. In contrast, for the string )(, there is no balanced substring, so the answer is 0.

The solution involves scanning each string using a stack-based approach to efficiently compute the length of the longest valid (balanced) substring.

Note: If necessary, you can express any mathematical equations using LaTeX. For example, the balanced condition can be conceptually represented as $\exists\, k: \, s[0..k]$ is balanced.

inputFormat

The input is read from standard input and has the following format:

n
s₁
s₂
...
sₙ

Here, n (where 0 ≤ n ≤ 10⁵) is the number of test strings, and each sᵢ is a non-empty string consisting only of the characters (' and ')'.

outputFormat

For each input string, output a single line containing the length of its longest balanced parentheses substring.

If there are no balanced substrings, output 0 for that test case.

## sample

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

6
4
6

</p>