Longest Balanced Substring

You are given a string S of length N consisting only of the characters (' and ')'. Your task is to find the length of the longest balanced substring in S.

A substring is said to be balanced if it forms a valid sequence of matched parentheses. In other words, if we define the balance of a string as the difference between the number of '(' and the number of ')', then a substring is balanced if:

\( balance = 0 \)

and for any prefix of the substring, the balance is never negative.

For example, given S = "(()())(())()" with N = 12, the entire string is balanced, so the answer is 12.

You are required to read input from stdin and output the result to stdout.

inputFormat

The first line of input contains an integer T, the number of test cases. Then for each test case:

• The first line contains an integer N, the length of the string.
• The second line contains the string S consisting only of characters '(' and ')'.

outputFormat

For each test case, output a single line containing the length of the longest balanced substring in S.

## sample

6
12
(()())(())()
6
((()))
7
())()()
10
(()())())(
4
)))(
4
()()

12
6
4
8
0
4

</p>