Yuki a découvert qu'une séquence de parenthèses palindromique ne peut pas être une séquence de parenthèses équilibrée. Elle a donc conçu une autre façon de définir une séquence de parenthèses palindromique équilibrée.

Yuki définit une séquence de parenthèses palindromique selon les règles suivantes :

• La chaîne vide est une séquence de parenthèses palindromique.

• ( et ) sont des séquences de parenthèses palindromiques.

• Si une séquence de parenthèses $s$ est palindromique, alors $(s($ et $)s)$ sont aussi des séquences de parenthèses palindromiques.

Yuki définit une séquence de parenthèses équilibrée selon les règles suivantes :

• La chaîne vide est une séquence de parenthèses équilibrée.

• Si une séquence de parenthèses $s$ est équilibrée, alors $(s)$ est aussi une séquence de parenthèses équilibrée.

• Si les séquences de parenthèses $s$ et $t$ sont toutes deux équilibrées, alors $st$ (la concaténation des deux séquences de parenthèses) est une séquence de parenthèses équilibrée.

Pour une séquence de parenthèses $s=s_1\ldots s_n$, Yuki définit $s$ comme une séquence de parenthèses palindromique équilibrée si et seulement si :

• $s_2\ldots s_{n-1}$ est une séquence de parenthèses palindromique.

• $s_1\ldots s_n$ est une séquence de parenthèses équilibrée.

En particulier, la chaîne vide et () sont aussi des séquences de parenthèses palindromiques équilibrées.

Par exemple, (())() et ()()(()()) sont des séquences de parenthèses palindromiques équilibrées, tandis que ((())) et ()()(()) ne le sont pas.

Yuki a maintenant une séquence de parenthèses $s$ de longueur $n$ et souhaite trouver la plus longue sous-séquence* de $s$ qui soit une séquence de parenthèses palindromique équilibrée. Cependant, Yuki ne sait pas comment faire : vous devez donc l'aider à trouver la longueur d'une telle sous-séquence la plus longue.

• : Une séquence $a$ est une sous-séquence d'une séquence $b$ si et seulement si $a$ peut être obtenue en supprimant zéro ou plusieurs éléments de $b$ ; en particulier, la séquence vide est une sous-séquence de toute séquence.

Entrée

Ce problème contient plusieurs cas de test.

La première ligne contient un entier positif $t$ ($1\le t\le5000$), représentant le nombre de cas de test.

Pour chaque cas de test :

• La première ligne contient un entier positif $n$ ($1\le n\le5000$).

• La deuxième ligne contient une séquence de parenthèses $s$ de longueur $n$ ($s_i\in\{\texttt{(},\texttt{)}\}$).

Il est garanti que la somme des $n$ sur tous les cas de test ne dépasse pas $10^4$.

Sortie

Pour chaque cas de test, affichez une ligne contenant un entier représentant la longueur de la plus longue sous-séquence satisfaisant la condition.

Exemples

Entrée 1

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

Sortie 1

2
0
6

Remarque

Pour le premier cas de test :

• Les plus longues sous-séquences satisfaisant la condition sont $s_1s_3=\texttt{()}$ et $s_2s_3=\texttt{()}$, donc la réponse est 2.

Pour le deuxième cas de test :

• La plus longue sous-séquence satisfaisant la condition est la chaîne vide, donc la réponse est 0.

Pour le troisième cas de test :

• La plus longue sous-séquence satisfaisant la condition est $s_1s_2s_4s_5s_6s_8=\texttt{()(())}$, donc la réponse est 6.