Yuki odkryła, że palindromiczny ciąg nawiasów nie może być zrównoważonym ciągiem nawiasów, więc opracowała inny sposób definiowania palindromicznego zrównoważonego ciągu nawiasów.

Yuki definiuje palindromiczny ciąg nawiasów według następujących reguł:

• Pusty napis jest palindromicznym ciągiem nawiasów.

• ( i ) są palindromicznymi ciągami nawiasów.

• Jeśli ciąg nawiasów $s$ jest palindromicznym ciągiem nawiasów, to $(s($ i $)s)$ również są palindromicznymi ciągami nawiasów.

Yuki definiuje zrównoważony ciąg nawiasów według następujących reguł:

• Pusty napis jest zrównoważonym ciągiem nawiasów.

• Jeśli ciąg nawiasów $s$ jest zrównoważonym ciągiem nawiasów, to $(s)$ również jest zrównoważonym ciągiem nawiasów.

• Jeśli ciągi nawiasów $s$ i $t$ są zrównoważonymi ciągami nawiasów, to $st$ (konkatenacja tych dwóch ciągów) również jest zrównoważonym ciągiem nawiasów.

Dla ciągu nawiasów $s=s_1\ldots s_n$ Yuki definiuje $s$ jako palindromiczny zrównoważony ciąg nawiasów wtedy i tylko wtedy, gdy:

• $s_2\ldots s_{n-1}$ jest palindromicznym ciągiem nawiasów.

• $s_1\ldots s_n$ jest zrównoważonym ciągiem nawiasów.

W szczególności pusty napis i () również są palindromicznymi zrównoważonymi ciągami nawiasów.

Na przykład (())() i ()()(()()) są palindromicznymi zrównoważonymi ciągami nawiasów, natomiast ((())) i ()()(()) nimi nie są.

Teraz Yuki ma ciąg nawiasów $s$ o długości $n$ i chce znaleźć najdłuższy podciąg* ciągu $s$, który jest palindromicznym zrównoważonym ciągiem nawiasów. Yuki nie wie jednak, jak to zrobić, więc musisz pomóc jej znaleźć długość takiego najdłuższego podciągu.

*: Ciąg $a$ jest podciągiem ciągu $b$ wtedy i tylko wtedy, gdy $a$ można otrzymać przez usunięcie z $b$ zera lub większej liczby elementów; w szczególności pusty ciąg jest podciągiem dowolnego ciągu.

Wejście

Zadanie zawiera wiele przypadków testowych.

Pierwszy wiersz zawiera dodatnią liczbę całkowitą $t$ ($1\le t\le5000$), oznaczającą liczbę przypadków testowych.

Dla każdego przypadku testowego:

• Pierwszy wiersz zawiera dodatnią liczbę całkowitą $n$ ($1\le n\le5000$).

• Drugi wiersz zawiera ciąg nawiasów $s$ o długości $n$ ($s_i\in\{\texttt{(},\texttt{)}\}$).

Gwarantuje się, że suma $n$ po wszystkich przypadkach testowych nie przekracza $10^4$.

Wyjście

Dla każdego przypadku testowego wypisz w osobnym wierszu liczbę całkowitą oznaczającą długość najdłuższego podciągu spełniającego warunek.

Przykład

Wejście 1

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

Wyjście 1

2
0
6

Uwagi

Dla pierwszego przypadku testowego:

• Najdłuższe podciągi spełniające warunek to $s_1s_3=\texttt{()}$ i $s_2s_3=\texttt{()}$, więc odpowiedź wynosi 2.

Dla drugiego przypadku testowego:

• Najdłuższym podciągiem spełniającym warunek jest pusty napis, więc odpowiedź wynosi 0.

Dla trzeciego przypadku testowego:

• Najdłuższym podciągiem spełniającym warunek jest $s_1s_2s_4s_5s_6s_8=\texttt{()(())}$, więc odpowiedź wynosi 6.