Longest Valid Parentheses Substring

Given a string s consisting only of the characters (' and ')', determine the length of the longest valid (well-formed) parentheses substring.

A substring is valid if it can be parsed as a well-formed set of parentheses. Mathematically, if we denote a substring from index i to j (0-indexed) by s[i...j], then the answer is:

$$\max_{s[i...j]\ \text{is valid}} (j-i+1)$$

You are given multiple test cases. For each test case, output the length of the longest valid parentheses substring.

inputFormat

The first line contains an integer T representing the number of test cases. Each of the following T lines contains a string s consisting of the characters '(' and ')'. Note that the string can be empty.

outputFormat

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

## sample

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

4
4
0

</p>