Yuki descubrió que una secuencia palindrómica de paréntesis no puede ser una secuencia equilibrada de paréntesis, así que diseñó otra forma de definir una secuencia palindrómica equilibrada de paréntesis.

Yuki define una secuencia palindrómica de paréntesis según las siguientes reglas:

• La cadena vacía es una secuencia palindrómica de paréntesis.

• ( y ) son secuencias palindrómicas de paréntesis.

• Si una secuencia de paréntesis $s$ es palindrómica, entonces $(s($ y $)s)$ también son secuencias palindrómicas de paréntesis.

Yuki define una secuencia equilibrada de paréntesis según las siguientes reglas:

• La cadena vacía es una secuencia equilibrada de paréntesis.

• Si una secuencia de paréntesis $s$ es equilibrada, entonces $(s)$ también es una secuencia equilibrada de paréntesis.

• Si las secuencias de paréntesis $s$ y $t$ son ambas equilibradas, entonces $st$ (la concatenación de ambas secuencias) es una secuencia equilibrada de paréntesis.

Para una secuencia de paréntesis $s=s_1\ldots s_n$, Yuki define $s$ como una secuencia palindrómica equilibrada de paréntesis si y solo si:

• $s_2\ldots s_{n-1}$ es una secuencia palindrómica de paréntesis.

• $s_1\ldots s_n$ es una secuencia equilibrada de paréntesis.

En particular, la cadena vacía y () también son secuencias palindrómicas equilibradas de paréntesis.

Por ejemplo, (())() y ()()(()()) son secuencias palindrómicas equilibradas de paréntesis, mientras que ((())) y ()()(()) no lo son.

Ahora Yuki tiene una secuencia de paréntesis $s$ de longitud $n$ y quiere encontrar la subsecuencia* más larga de $s$ que sea una secuencia palindrómica equilibrada de paréntesis. Sin embargo, Yuki no sabe cómo hacerlo, por lo que debes ayudarla a encontrar la longitud de dicha subsecuencia más larga.

*: Una secuencia $a$ es una subsecuencia de una secuencia $b$ si y solo si $a$ puede obtenerse eliminando cero o más elementos de $b$; en particular, la secuencia vacía es una subsecuencia de cualquier secuencia.

Entrada

Este problema contiene varios casos de prueba.

La primera línea contiene un entero positivo $t$ ($1\le t\le5000$), que representa el número de casos de prueba.

Para cada caso de prueba:

• La primera línea contiene un entero positivo $n$ ($1\le n\le5000$).

• La segunda línea contiene una secuencia de paréntesis $s$ de longitud $n$ ($s_i\in\{\texttt{(},\texttt{)}\}$).

Se garantiza que la suma de $n$ sobre todos los casos de prueba no supera $10^4$.

Salida

Para cada caso de prueba, imprime una línea con un entero que represente la longitud de la subsecuencia más larga que cumpla la condición.

Ejemplos

Entrada 1

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

Salida 1

2
0
6

Nota

Para el primer caso de prueba:

• Las subsecuencias más largas que cumplen la condición son $s_1s_3=\texttt{()}$ y $s_2s_3=\texttt{()}$, por lo que la respuesta es 2.

Para el segundo caso de prueba:

• La subsecuencia más larga que cumple la condición es la cadena vacía, por lo que la respuesta es 0.

Para el tercer caso de prueba:

• La subsecuencia más larga que cumple la condición es $s_1s_2s_4s_5s_6s_8=\texttt{()(())}$, por lo que la respuesta es 6.