Yuki upptäckte att en palindromisk parentesföljd inte kan vara en balanserad parentesföljd, så hon utformade ett annat sätt att definiera en palindromisk balanserad parentesföljd.

Yuki definierar en palindromisk parentesföljd enligt följande regler:

• Den tomma strängen är en palindromisk parentesföljd.

• ( och ) är palindromiska parentesföljder.

• Om en parentesföljd $s$ är en palindromisk parentesföljd, så är $(s($ och $)s)$ palindromiska parentesföljder.

Yuki definierar en balanserad parentesföljd enligt följande regler:

• Den tomma strängen är en balanserad parentesföljd.

• Om en parentesföljd $s$ är en balanserad parentesföljd, så är $(s)$ en balanserad parentesföljd.

• Om parentesföljderna $s$ och $t$ båda är balanserade parentesföljder, så är $st$ (konkateneringen av de två parentesföljderna) en balanserad parentesföljd.

För en parentesföljd $s=s_1\ldots s_n$ definierar Yuki $s$ som en palindromisk balanserad parentesföljd om och endast om:

• $s_2\ldots s_{n-1}$ är en palindromisk parentesföljd.

• $s_1\ldots s_n$ är en balanserad parentesföljd.

Specifikt är den tomma strängen och () också palindromiska balanserade parentesföljder.

Till exempel är (())() och ()()(()()) palindromiska balanserade parentesföljder, medan ((())) och ()()(()) inte är det.

Nu har Yuki en parentesföljd $s$ av längd $n$, och hon vill hitta den längsta delföljden* av $s$ som är en palindromisk balanserad parentesföljd. Yuki vet dock inte hur man gör detta, så du måste hjälpa henne att hitta längden på den längsta sådana delföljden.

*: En följd $a$ är en delföljd av följden $b$ om och endast om $a$ kan erhållas genom att ta bort noll eller fler element från $b$; specifikt är den tomma följden en delföljd av varje följd.

Indata

Detta problem innehåller flera testfall.

Den första raden innehåller ett positivt heltal $t$ ($1\le t\le5000$), som representerar antalet testfall.

För varje testfall:

• Den första raden innehåller ett positivt heltal $n$ ($1\le n\le5000$).

• Den andra raden innehåller en parentesföljd $s$ av längd $n$ ($s_i\in\{\texttt{(},\texttt{)}\}$).

Det garanteras att summan av $n$ över alla testfall inte överstiger $10^4$.

Utdata

För varje testfall, skriv ut en enda rad som innehåller ett heltal som representerar längden på den längsta delföljden som uppfyller villkoret.

Exempel

Indata 1

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

Utdata 1

2
0
6

Notering

För det första testfallet:

• De längsta delföljderna som uppfyller villkoret är $s_1s_3=\texttt{()}$ och $s_2s_3=\texttt{()}$, så svaret är 2.

För det andra testfallet:

• Den längsta delföljden som uppfyller villkoret är den tomma strängen, så svaret är 0.

För det tredje testfallet:

• Den längsta delföljden som uppfyller villkoret är $s_1s_2s_4s_5s_6s_8=\texttt{()(())}$, så svaret är 6.