Descripción

Se te da una secuencia de paréntesis \(s\) de longitud \(n\) , donde \(n\) es par (divisible por dos). La cadena \(s\) consta de \(\frac{n}{2}\) paréntesis de apertura '(' y \(\frac{n}{2}\) paréntesis de cierre ')'.

En un movimiento, puedes elegir exactamente un paréntesis y moverlo al principio o al final de la cadena (es decir, eliges un índice \(i\) , eliminas el \(i\)-ésimo carácter de \(s\) y lo insertas antes o después de todos los caracteres restantes de \(s\)).

Tu tarea es encontrar el número mínimo de movimientos necesarios para obtener una secuencia de paréntesis regular a partir de \(s\). Se garantiza que la respuesta siempre existe bajo las restricciones dadas.

Recuerda que la secuencia de paréntesis regular es:

• "()" es una secuencia de paréntesis regular;
• si \(s\) es una secuencia de paréntesis regular, entonces "(" + \(s\) + ")" es una secuencia de paréntesis regular;
• si \(s\) y \(t\) son secuencias de paréntesis regulares, entonces \(s\) + \(t\) es una secuencia de paréntesis regular.

Por ejemplo, "()()", "(())()", "(())" y "()" son secuencias de paréntesis regulares, pero ")(", "()(" y ")))" no lo son.

Debes responder \(t\) casos de prueba independientes.

Entrada

La primera línea de la entrada contiene un entero \(t\) \((1 \leq t \leq 2000)\) — el número de casos de prueba. Luego siguen \(t\) casos de prueba.

La primera línea del caso de prueba contiene un entero \(n\) \((2 \leq n \leq 50)\) — la longitud de \(s\) . Se garantiza que \(n\) es par. La segunda línea del caso de prueba contiene la cadena \(s\) que consiste en \(\frac{n}{2}\) paréntesis de apertura y \(\frac{n}{2}\) paréntesis de cierre.

Salida

Para cada caso de prueba, imprime la respuesta — el número mínimo de movimientos requeridos para obtener la secuencia de paréntesis regular de \(s\). Se garantiza que la respuesta siempre existe bajo las restricciones dadas.

Ejemplo

Entrada

4
2
)(
4
()()
8
())()()(
10
)))((((())

Salida

1
0
1
3

Nota

En el primer caso de prueba del ejemplo, basta con mover el primer paréntesis al final de la cadena.

En el tercer caso de prueba del ejemplo, basta con mover el último paréntesis al principio de la cadena.

En el cuarto caso de prueba del ejemplo, podemos elegir los tres últimos paréntesis de apertura, moverlos al principio de la cadena y obtener "((()))(())".