Yuki ha scoperto che una sequenza di parentesi palindroma non può essere una sequenza di parentesi bilanciata, quindi ha ideato un altro modo per definire una sequenza di parentesi palindroma e bilanciata.

Yuki definisce una sequenza di parentesi palindroma secondo le seguenti regole:

• La stringa vuota è una sequenza di parentesi palindroma.

• ( e ) sono sequenze di parentesi palindrome.

• Se una sequenza di parentesi $s$ è una sequenza di parentesi palindroma, allora $(s($ e $)s)$ sono sequenze di parentesi palindrome.

Yuki definisce una sequenza di parentesi bilanciata secondo le seguenti regole:

• La stringa vuota è una sequenza di parentesi bilanciata.

• Se una sequenza di parentesi $s$ è una sequenza di parentesi bilanciata, allora $(s)$ è una sequenza di parentesi bilanciata.

• Se le sequenze di parentesi $s$ e $t$ sono entrambe sequenze di parentesi bilanciate, allora $st$ (la concatenazione delle due sequenze di parentesi) è una sequenza di parentesi bilanciata.

Per una sequenza di parentesi $s=s_1\ldots s_n$, Yuki definisce $s$ come una sequenza di parentesi palindroma e bilanciata se e solo se:

• $s_2\ldots s_{n-1}$ è una sequenza di parentesi palindroma.

• $s_1\ldots s_n$ è una sequenza di parentesi bilanciata.

In particolare, anche la stringa vuota e () sono sequenze di parentesi palindrome e bilanciate.

Ad esempio, (())() e ()()(()()) sono sequenze di parentesi palindrome e bilanciate, mentre ((())) e ()()(()) non lo sono.

Ora, Yuki ha una sequenza di parentesi $s$ di lunghezza $n$ e vuole trovare la più lunga sottosequenza* di $s$ che sia una sequenza di parentesi palindroma e bilanciata. Tuttavia, Yuki non sa come fare, quindi devi aiutarla a trovare la lunghezza della più lunga sottosequenza di questo tipo.

*: Una sequenza $a$ è una sottosequenza della sequenza $b$ se e solo se $a$ può essere ottenuta eliminando zero o più elementi da $b$; in particolare, la sequenza vuota è una sottosequenza di qualsiasi sequenza.

Input

Questo problema contiene più casi di test.

La prima riga contiene un intero positivo $t$ ($1\le t\le5000$), che rappresenta il numero di casi di test.

Per ciascun caso di test:

• La prima riga contiene un intero positivo $n$ ($1\le n\le5000$).

• La seconda riga contiene una sequenza di parentesi $s$ di lunghezza $n$ ($s_i\in\{\texttt{(},\texttt{)}\}$).

È garantito che la somma di $n$ su tutti i casi di test non supera $10^4$.

Output

Per ciascun caso di test, stampa una singola riga contenente un intero che rappresenta la lunghezza della più lunga sottosequenza che soddisfa la condizione.

Esempi

Input 1

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

Output 1

2
0
6

Note

Per il primo caso di test:

• Le sottosequenze più lunghe che soddisfano la condizione sono $s_1s_3=\texttt{()}$ e $s_2s_3=\texttt{()}$, quindi la risposta è 2.

Per il secondo caso di test:

• La sottosequenza più lunga che soddisfa la condizione è la stringa vuota, quindi la risposta è 0.

Per il terzo caso di test:

• La sottosequenza più lunga che soddisfa la condizione è $s_1s_2s_4s_5s_6s_8=\texttt{()(())}$, quindi la risposta è 6.