Юки палиндромды жақшалар тізбегі теңгерімді жақшалар тізбегі бола алмайтынын байқап, палиндромды теңгерімді жақшалар тізбегін анықтаудың басқа тәсілін ойлап тапты.

Юки палиндромды жақшалар тізбегін келесі ережелер бойынша анықтайды:

• Бос жол — палиндромды жақшалар тізбегі.

• ( және ) — палиндромды жақшалар тізбектері.

• Егер $s$ жақшалар тізбегі палиндромды жақшалар тізбегі болса, онда $(s($ және $)s)$ де палиндромды жақшалар тізбектері болады.

Юки теңгерімді жақшалар тізбегін келесі ережелер бойынша анықтайды:

• Бос жол — теңгерімді жақшалар тізбегі.

• Егер $s$ жақшалар тізбегі теңгерімді жақшалар тізбегі болса, онда $(s)$ де теңгерімді жақшалар тізбегі болады.

• Егер $s$ және $t$ жақшалар тізбектерінің екеуі де теңгерімді жақшалар тізбектері болса, онда $st$ (екі жақшалар тізбегінің конкатенациясы) да теңгерімді жақшалар тізбегі болады.

$s=s_1\ldots s_n$ жақшалар тізбегі үшін Юки $s$ тізбегін палиндромды теңгерімді жақшалар тізбегі деп атайды сонда және тек сонда ғана, егер:

• $s_2\ldots s_{n-1}$ палиндромды жақшалар тізбегі болса.

• $s_1\ldots s_n$ теңгерімді жақшалар тізбегі болса.

Атап айтқанда, бос жол мен () де палиндромды теңгерімді жақшалар тізбектері болып табылады.

Мысалы, (())() және ()()(()()) — палиндромды теңгерімді жақшалар тізбектері, ал ((())) және ()()(()) олай емес.

Енді Юкиде ұзындығы $n$ болатын $s$ жақшалар тізбегі бар және ол $s$ тізбегінің палиндромды теңгерімді жақшалар тізбегі болатын ең ұзын ішкі тізбегін* тапқысы келеді. Алайда Юки мұны қалай істеу керектігін білмейді, сондықтан сіз оған осындай ең ұзын ішкі тізбектің ұзындығын табуға көмектесуіңіз керек.

*: $a$ тізбегі $b$ тізбегінің ішкі тізбегі деп аталады сонда және тек сонда ғана, егер $a$ тізбегін $b$ тізбегінен нөл немесе одан көп элементті өшіру арқылы алуға болса; атап айтқанда, бос тізбек кез келген тізбектің ішкі тізбегі болып табылады.

Кіріс деректері

Бұл есеп бірнеше тест жиынтығынан тұрады.

Бірінші жолда тест жиынтықтарының санын білдіретін оң бүтін $t$ ($1\le t\le5000$) саны берілген.

Әрбір тест жиынтығы үшін:

• Бірінші жолда оң бүтін $n$ ($1\le n\le5000$) саны берілген.

• Екінші жолда ұзындығы $n$ болатын $s$ ($s_i\in\{\texttt{(},\texttt{)}\}$) жақшалар тізбегі берілген.

Барлық тест жиынтықтары бойынша $n$ сандарының қосындысы $10^4$-нен аспайтынына кепілдік беріледі.

Шығыс деректері

Әрбір тест жиынтығы үшін шартты қанағаттандыратын ең ұзын ішкі тізбектің ұзындығын білдіретін бүтін саннан тұратын бір жолды шығарыңыз.

Мысалдар

Кіріс 1

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

Шығыс 1

2
0
6

Ескертпе

Бірінші тест жиынтығы үшін:

• Шартты қанағаттандыратын ең ұзын ішкі тізбектер — $s_1s_3=\texttt{()}$ және $s_2s_3=\texttt{()}$, сондықтан жауап — 2.

Екінші тест жиынтығы үшін:

• Шартты қанағаттандыратын ең ұзын ішкі тізбек — бос жол, сондықтан жауап — 0.

Үшінші тест жиынтығы үшін:

• Шартты қанағаттандыратын ең ұзын ішкі тізбек — $s_1s_2s_4s_5s_6s_8=\texttt{()(())}$, сондықтан жауап — 6.