Maximum Balanced Substring

Problem Description:

Given a string composed solely of the characters '(' and ')', your task is to determine the length of the longest contiguous substring that forms a balanced sequence of parentheses. A substring is considered balanced if it contains an equal number of '(' and ')' characters and every prefix of the substring has no fewer ')' than '(' characters. In mathematical terms, for a balanced substring (s), the following conditions must hold:

[ \text{count}(s, '(') = \text{count}(s, ')') \quad\text{and}\quad \forall ; 1 \leq k \leq |s|, ; \text{count}(s[1..k], '(') \geq \text{count}(s[1..k], ')') ]

For example:

• For (s = "(()())"), the entire string is balanced and the answer is 6.
• For (s = ")()())"), the longest balanced substring is "()()" with length 4.
• For (s = "()((()))"), the entire string is balanced and the answer is 8.

The input will consist of multiple test cases. Your program should compute the length of the maximum balanced substring for each test case.

inputFormat

Input Format:

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

outputFormat

Output Format:

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

1
(()())

6