Yuki は、回文の括弧列は平衡な括弧列にはなれないことに気付き、回文平衡括弧列を定義する別の方法を考えました。
Yuki は回文の括弧列を次の規則で定義します。
空文字列は回文の括弧列です。
(と)は回文の括弧列です。括弧列 $s$ が回文の括弧列ならば、$(s($ と $)s)$ も回文の括弧列です。
Yuki は平衡な括弧列を次の規則で定義します。
空文字列は平衡な括弧列です。
括弧列 $s$ が平衡な括弧列ならば、$(s)$ も平衡な括弧列です。
括弧列 $s$ と $t$ がともに平衡な括弧列ならば、$st$（2 つの括弧列を連結したもの）も平衡な括弧列です。
括弧列 $s=s_1\ldots s_n$ について、Yuki は次の条件が成り立つとき、かつそのときに限り、$s$ を回文平衡括弧列と定義します。
$s_2\ldots s_{n-1}$ は回文の括弧列です。
$s_1\ldots s_n$ は平衡な括弧列です。
特に、空文字列と () も回文平衡括弧列です。
例えば、(())() と ()()(()()) は回文平衡括弧列ですが、((())) と ()()(()) はそうではありません。
今、Yuki は長さ $n$ の括弧列 $s$ を持っており、回文平衡括弧列である $s$ の最長の部分列*を求めたいと考えています。しかし Yuki はその方法を知らないので、そのような最長の部分列の長さを求めてあげてください。
*：列 $a$ が列 $b$ の部分列であるのは、$b$ から 0 個以上の要素を削除して $a$ を得られるとき、かつそのときに限ります。特に、空の列はどの列の部分列でもあります。
入力
この問題には複数のテストケースがあります。
最初の行には、テストケース数を表す正整数 $t$（$1\le t\le5000$）が与えられます。
各テストケースについて：
最初の行には正整数 $n$（$1\le n\le5000$）が与えられます。
2 行目には長さ $n$ の括弧列 $s$（$s_i\in\{\texttt{(},\texttt{)}\}$）が与えられます。
すべてのテストケースにわたる $n$ の総和は $10^4$ 以下であることが保証されます。
出力
各テストケースについて、条件を満たす最長の部分列の長さを表す整数を 1 行に出力してください。
入出力例
入力 1
3 5 (()(( 7 )))(((( 8 ())(()()
出力 1
2 0 6
注記
最初のテストケースについて：
- 条件を満たす最長の部分列は $s_1s_3=\texttt{()}$ と $s_2s_3=\texttt{()}$ なので、答えは 2 です。
2 番目のテストケースについて：
- 条件を満たす最長の部分列は空文字列なので、答えは 0 です。
3 番目のテストケースについて：
- 条件を満たす最長の部分列は $s_1s_2s_4s_5s_6s_8=\texttt{()(())}$ なので、答えは 6 です。