Yuki hat entdeckt, dass eine palindromische Klammerfolge keine balancierte Klammerfolge sein kann. Deshalb hat sie eine andere Definition für eine palindromische balancierte Klammerfolge entwickelt.

Yuki definiert eine palindromische Klammerfolge nach den folgenden Regeln:

• Die leere Zeichenkette ist eine palindromische Klammerfolge.

• ( und ) sind palindromische Klammerfolgen.

• Ist eine Klammerfolge $s$ palindromisch, so sind auch $(s($ und $)s)$ palindromische Klammerfolgen.

Yuki definiert eine balancierte Klammerfolge nach den folgenden Regeln:

• Die leere Zeichenkette ist eine balancierte Klammerfolge.

• Ist eine Klammerfolge $s$ balanciert, so ist auch $(s)$ eine balancierte Klammerfolge.

• Sind die Klammerfolgen $s$ und $t$ beide balanciert, so ist $st$ (die Verkettung der beiden Klammerfolgen) eine balancierte Klammerfolge.

Für eine Klammerfolge $s=s_1\ldots s_n$ definiert Yuki $s$ genau dann als palindromische balancierte Klammerfolge, wenn:

• $s_2\ldots s_{n-1}$ eine palindromische Klammerfolge ist.

• $s_1\ldots s_n$ eine balancierte Klammerfolge ist.

Insbesondere sind auch die leere Zeichenkette und () palindromische balancierte Klammerfolgen.

Zum Beispiel sind (())() und ()()(()()) palindromische balancierte Klammerfolgen, während ((())) und ()()(()) es nicht sind.

Nun hat Yuki eine Klammerfolge $s$ der Länge $n$ und möchte die längste Teilfolge* von $s$ finden, die eine palindromische balancierte Klammerfolge ist. Yuki weiß jedoch nicht, wie das geht. Daher sollst du ihr helfen, die Länge einer solchen längsten Teilfolge zu bestimmen.

*: Eine Folge $a$ ist genau dann eine Teilfolge einer Folge $b$, wenn $a$ durch Löschen von null oder mehr Elementen aus $b$ gewonnen werden kann. Insbesondere ist die leere Folge eine Teilfolge jeder Folge.

Eingabe

Diese Aufgabe enthält mehrere Testfälle.

Die erste Zeile enthält eine positive ganze Zahl $t$ ($1\le t\le5000$), die die Anzahl der Testfälle angibt.

Für jeden Testfall:

• Die erste Zeile enthält eine positive ganze Zahl $n$ ($1\le n\le5000$).

• Die zweite Zeile enthält eine Klammerfolge $s$ der Länge $n$ ($s_i\in\{\texttt{(},\texttt{)}\}$).

Es ist garantiert, dass die Summe von $n$ über alle Testfälle $10^4$ nicht überschreitet.

Ausgabe

Gib für jeden Testfall eine Zeile mit einer ganzen Zahl aus, die die Länge der längsten Teilfolge angibt, welche die Bedingung erfüllt.

Beispiele

Eingabe 1

3
5
(()((
7
)))((((
8
())(()()

Ausgabe 1

2
0
6

Hinweis

Für den ersten Testfall:

• Die längsten Teilfolgen, die die Bedingung erfüllen, sind $s_1s_3=\texttt{()}$ und $s_2s_3=\texttt{()}$, also lautet die Antwort 2.

Für den zweiten Testfall:

• Die längste Teilfolge, die die Bedingung erfüllt, ist die leere Zeichenkette, also lautet die Antwort 0.

Für den dritten Testfall:

• Die längste Teilfolge, die die Bedingung erfüllt, ist $s_1s_2s_4s_5s_6s_8=\texttt{()(())}$, also lautet die Antwort 6.