Yuki oppdaget at en palindromisk parentesfølge ikke kan være en balansert parentesfølge, så hun laget en annen måte å definere en palindromisk balansert parentesfølge på.

Yuki definerer en palindromisk parentesfølge etter følgende regler:

• Den tomme strengen er en palindromisk parentesfølge.

• ( og ) er palindromiske parentesfølger.

• Hvis en parentesfølge $s$ er en palindromisk parentesfølge, så er $(s($ og $)s)$ palindromiske parentesfølger.

Yuki definerer en balansert parentesfølge etter følgende regler:

• Den tomme strengen er en balansert parentesfølge.

• Hvis en parentesfølge $s$ er en balansert parentesfølge, så er $(s)$ en balansert parentesfølge.

• Hvis parentesfølgene $s$ og $t$ begge er balanserte parentesfølger, så er $st$ (konkateneringen av de to parentesfølgene) en balansert parentesfølge.

For en parentesfølge $s=s_1\ldots s_n$ definerer Yuki $s$ som en palindromisk balansert parentesfølge hvis og bare hvis:

• $s_2\ldots s_{n-1}$ er en palindromisk parentesfølge.

• $s_1\ldots s_n$ er en balansert parentesfølge.

Spesifikt er den tomme strengen og () også palindromiske balanserte parentesfølger.

For eksempel er (())() og ()()(()()) palindromiske balanserte parentesfølger, mens ((())) og ()()(()) ikke er det.

Nå har Yuki en parentesfølge $s$ av lengde $n$, og hun vil finne den lengste delfølgen* av $s$ som er en palindromisk balansert parentesfølge. Yuki vet imidlertid ikke hvordan hun skal gjøre dette, så du må hjelpe henne med å finne lengden på den lengste slike delfølgen.

*: En følge $a$ er en delfølge av følgen $b$ hvis og bare hvis $a$ kan oppnås ved å slette null eller flere elementer fra $b$; spesifikt er den tomme følgen en delfølge av enhver følge.

Inndata

Dette problemet inneholder flere testtilfeller.

Den første linjen inneholder et positivt heltall $t$ ($1\le t\le5000$), som representerer antall testtilfeller.

For hvert testtilfelle:

• Den første linjen inneholder et positivt heltall $n$ ($1\le n\le5000$).

• Den andre linjen inneholder en parentesfølge $s$ av lengde $n$ ($s_i\in\{\texttt{(},\texttt{)}\}$).

Det garanteres at summen av $n$ over alle testtilfeller ikke overstiger $10^4$.

Utdata

For hvert testtilfelle skal du skrive ut én enkelt linje som inneholder et heltall som representerer lengden på den lengste delfølgen som oppfyller betingelsen.

Eksempler

Inndata 1

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

Utdata 1

2
0
6

Merk

For det første testtilfellet:

• De lengste delfølgene som oppfyller betingelsen er $s_1s_3=\texttt{()}$ og $s_2s_3=\texttt{()}$, så svaret er 2.

For det andre testtilfellet:

• Den lengste delfølgen som oppfyller betingelsen er den tomme strengen, så svaret er 0.

For det tredje testtilfellet:

• Den lengste delfølgen som oppfyller betingelsen er $s_1s_2s_4s_5s_6s_8=\texttt{()(())}$, så svaret er 6.