Longest Valid Parentheses Substring

Given a string s consisting only of the characters (' and '), your task is to find the length of the longest valid (well-formed) parentheses substring.

A valid parentheses substring is defined by the following rules:
( S \rightarrow \epsilon ) (empty string is valid),
( S \rightarrow (S) ), and
( S \rightarrow SS ).

For example, for the string (())()()), the longest valid substring is (())()() with length (8).

inputFormat

The input starts with an integer T representing the number of test cases. Each of the next T lines contains a string s consisting solely of the characters '(' and ')'.

Input is given via standard input (stdin).

outputFormat

For each test case, output a single integer on a new line representing the length of the longest valid parentheses substring. The output should be sent to standard output (stdout).## sample

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

8
6
0