Yuki uppgötvaði að samhverf svigaruna getur ekki verið jafnvægissvigaruna, svo hún hannaði aðra leið til að skilgreina samhverfa jafnvægissvigarunu.

Yuki skilgreinir samhverfa svigarunu samkvæmt eftirfarandi reglum:

• Tómi strengurinn er samhverf svigaruna.

• ( og ) eru samhverfar svigarunur.

• Ef svigaruna $s$ er samhverf svigaruna, þá eru $(s($ og $)s)$ samhverfar svigarunur.

Yuki skilgreinir jafnvægissvigarunu samkvæmt eftirfarandi reglum:

• Tómi strengurinn er jafnvægissvigaruna.

• Ef svigaruna $s$ er jafnvægissvigaruna, þá er $(s)$ jafnvægissvigaruna.

• Ef svigarunurnar $s$ og $t$ eru báðar jafnvægissvigarunur, þá er $st$ (samskeyting svigarunanna tveggja) jafnvægissvigaruna.

Fyrir svigarunu $s=s_1\ldots s_n$ skilgreinir Yuki $s$ sem samhverfa jafnvægissvigarunu ef og aðeins ef:

• $s_2\ldots s_{n-1}$ er samhverf svigaruna.

• $s_1\ldots s_n$ er jafnvægissvigaruna.

Sérstaklega eru tómi strengurinn og () einnig samhverfar jafnvægissvigarunur.

Til dæmis eru (())() og ()()(()()) samhverfar jafnvægissvigarunur, en ((())) og ()()(()) eru það ekki.

Nú er Yuki með svigarunu $s$ af lengd $n$ og hún vill finna lengstu hlutrunu* úr $s$ sem er samhverf jafnvægissvigaruna. Hins vegar veit Yuki ekki hvernig á að gera þetta, svo þú þarft að hjálpa henni að finna lengd lengstu slíkrar hlutrunu.

*: Runa $a$ er hlutruna úr runu $b$ ef og aðeins ef hægt er að fá $a$ með því að eyða núll eða fleiri stökum úr $b$; sérstaklega er tóma runan hlutruna úr hvaða runu sem er.

Inntak

Þetta verkefni inniheldur mörg prófunartilvik.

Fyrsta línan inniheldur jákvæða heiltölu $t$ ($1\le t\le5000$), sem táknar fjölda prófunartilvika.

Fyrir hvert prófunartilvik:

• Fyrsta línan inniheldur jákvæða heiltölu $n$ ($1\le n\le5000$).

• Önnur línan inniheldur svigarunu $s$ af lengd $n$ ($s_i\in\{\texttt{(},\texttt{)}\}$).

Tryggt er að summa $n$ yfir öll prófunartilvik fari ekki yfir $10^4$.

Úttak

Fyrir hvert prófunartilvik skal prenta út eina línu sem inniheldur heiltölu sem táknar lengd lengstu hlutrununnar sem uppfyllir skilyrðið.

Dæmi

Inntak 1

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

Úttak 1

2
0
6

Athugasemd

Fyrir fyrsta prófunartilvikið:

• Lengstu hlutrunurnar sem uppfylla skilyrðið eru $s_1s_3=\texttt{()}$ og $s_2s_3=\texttt{()}$, svo svarið er 2.

Fyrir annað prófunartilvikið:

• Lengsta hlutrunan sem uppfyllir skilyrðið er tómi strengurinn, svo svarið er 0.

Fyrir þriðja prófunartilvikið:

• Lengsta hlutrunan sem uppfyllir skilyrðið er $s_1s_2s_4s_5s_6s_8=\texttt{()(())}$, svo svarið er 6.