Yuki huomasi, ettei palindrominen sulkulauseke voi olla tasapainoinen sulkulauseke, joten hän suunnitteli toisen tavan määritellä palindrominen tasapainoinen sulkulauseke.
Yuki määrittelee palindromisen sulkulausekkeen seuraavien sääntöjen mukaisesti:
Tyhjä merkkijono on palindrominen sulkulauseke.
(ja)ovat palindromisia sulkulausekkeita.Jos sulkulauseke $s$ on palindrominen sulkulauseke, niin $(s($ ja $)s)$ ovat palindromisia sulkulausekkeita.
Yuki määrittelee tasapainoisen sulkulausekkeen seuraavien sääntöjen mukaisesti:
Tyhjä merkkijono on tasapainoinen sulkulauseke.
Jos sulkulauseke $s$ on tasapainoinen sulkulauseke, niin $(s)$ on tasapainoinen sulkulauseke.
Jos sulkulausekkeet $s$ ja $t$ ovat molemmat tasapainoisia sulkulausekkeita, niin $st$ (kahden sulkulausekkeen yhdistelmä) on tasapainoinen sulkulauseke.
Sulkulausekkeelle $s=s_1\ldots s_n$ Yuki määrittelee lausekkeen $s$ palindromiseksi tasapainoiseksi sulkulausekkeeksi jos ja vain jos:
$s_2\ldots s_{n-1}$ on palindrominen sulkulauseke.
$s_1\ldots s_n$ on tasapainoinen sulkulauseke.
Erityisesti tyhjä merkkijono ja () ovat myös palindromisia tasapainoisia sulkulausekkeita.
Esimerkiksi (())() ja ()()(()()) ovat palindromisia tasapainoisia sulkulausekkeita, kun taas ((())) ja ()()(()) eivät ole.
Nyt Yukilla on pituutta $n$ oleva sulkulauseke $s$, ja hän haluaa löytää lausekkeen $s$ pisimmän alijonon*, joka on palindrominen tasapainoinen sulkulauseke. Yuki ei kuitenkaan tiedä, miten tämä tehdään, joten sinun tulee auttaa häntä löytämään pisimmän tällaisen alijonon pituus.
*: Jono $a$ on jonon $b$ alijono jos ja vain jos $a$ voidaan saada poistamalla nolla tai useampia alkioita jonosta $b$; erityisesti tyhjä jono on minkä tahansa jonon alijono.
Syöte
Tässä tehtävässä on useita testitapauksia.
Ensimmäinen rivi sisältää positiivisen kokonaisluvun $t$ ($1\le t\le5000$), joka ilmoittaa testitapausten määrän.
Jokaiselle testitapaukselle:
Ensimmäinen rivi sisältää positiivisen kokonaisluvun $n$ ($1\le n\le5000$).
Toinen rivi sisältää pituutta $n$ olevan sulkulausekkeen $s$ ($s_i\in\{\texttt{(},\texttt{)}\}$).
On taattu, että lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $10^4$.
Tuloste
Tulosta jokaiselle testitapaukselle yksi rivi, joka sisältää kokonaisluvun: ehdon täyttävän pisimmän alijonon pituuden.
Esimerkit
Syöte 1
3 5 (()(( 7 )))(((( 8 ())(()()
Tuloste 1
2 0 6
Huomautus
Ensimmäisessä testitapauksessa:
- Pisimmät ehdon täyttävät alijonot ovat $s_1s_3=\texttt{()}$ ja $s_2s_3=\texttt{()}$, joten vastaus on 2.
Toisessa testitapauksessa:
- Pisin ehdon täyttävä alijono on tyhjä merkkijono, joten vastaus on 0.
Kolmannessa testitapauksessa:
- Pisin ehdon täyttävä alijono on $s_1s_2s_4s_5s_6s_8=\texttt{()(())}$, joten vastaus on 6.