Yuki descobriu que uma sequência palindrómica de parênteses não pode ser uma sequência equilibrada de parênteses, pelo que criou outra forma de definir uma sequência palindrómica equilibrada de parênteses.

Yuki define uma sequência palindrómica de parênteses segundo as seguintes regras:

• A cadeia vazia é uma sequência palindrómica de parênteses.

• ( e ) são sequências palindrómicas de parênteses.

• Se uma sequência de parênteses $s$ for palindrómica, então $(s($ e $)s)$ também são sequências palindrómicas de parênteses.

Yuki define uma sequência equilibrada de parênteses segundo as seguintes regras:

• A cadeia vazia é uma sequência equilibrada de parênteses.

• Se uma sequência de parênteses $s$ for equilibrada, então $(s)$ também é uma sequência equilibrada de parênteses.

• Se as sequências de parênteses $s$ e $t$ forem ambas equilibradas, então $st$ (a concatenação das duas sequências) é uma sequência equilibrada de parênteses.

Para uma sequência de parênteses $s=s_1\ldots s_n$, Yuki define $s$ como uma sequência palindrómica equilibrada de parênteses se e só se:

• $s_2\ldots s_{n-1}$ é uma sequência palindrómica de parênteses.

• $s_1\ldots s_n$ é uma sequência equilibrada de parênteses.

Em particular, a cadeia vazia e () também são sequências palindrómicas equilibradas de parênteses.

Por exemplo, (())() e ()()(()()) são sequências palindrómicas equilibradas de parênteses, enquanto ((())) e ()()(()) não são.

Agora, Yuki tem uma sequência de parênteses $s$ de comprimento $n$ e quer encontrar a subsequência* mais longa de $s$ que seja uma sequência palindrómica equilibrada de parênteses. Porém, Yuki não sabe como o fazer, pelo que tens de a ajudar a encontrar o comprimento dessa subsequência mais longa.

*: Uma sequência $a$ é uma subsequência da sequência $b$ se e só se $a$ puder ser obtida eliminando zero ou mais elementos de $b$; em particular, a sequência vazia é uma subsequência de qualquer sequência.

Entrada

Este problema contém vários casos de teste.

A primeira linha contém um inteiro positivo $t$ ($1\le t\le5000$), que representa o número de casos de teste.

Para cada caso de teste:

• A primeira linha contém um inteiro positivo $n$ ($1\le n\le5000$).

• A segunda linha contém uma sequência de parênteses $s$ de comprimento $n$ ($s_i\in\{\texttt{(},\texttt{)}\}$).

É garantido que a soma de $n$ em todos os casos de teste não excede $10^4$.

Saída

Para cada caso de teste, escreve uma linha com um inteiro que representa o comprimento da subsequência mais longa que satisfaz a condição.

Exemplos

Entrada 1

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

Saída 1

2
0
6

Nota

Para o primeiro caso de teste:

• As subsequências mais longas que satisfazem a condição são $s_1s_3=\texttt{()}$ e $s_2s_3=\texttt{()}$, pelo que a resposta é 2.

Para o segundo caso de teste:

• A subsequência mais longa que satisfaz a condição é a cadeia vazia, pelo que a resposta é 0.

Para o terceiro caso de teste:

• A subsequência mais longa que satisfaz a condição é $s_1s_2s_4s_5s_6s_8=\texttt{()(())}$, pelo que a resposta é 6.