Yuki обнаружила, что палиндромная скобочная последовательность не может быть правильной скобочной последовательностью, поэтому придумала другой способ определить палиндромную правильную скобочную последовательность.

Yuki определяет палиндромную скобочную последовательность по следующим правилам:

• Пустая строка является палиндромной скобочной последовательностью.

• ( и ) являются палиндромными скобочными последовательностями.

• Если скобочная последовательность $s$ является палиндромной, то $(s($ и $)s)$ также являются палиндромными скобочными последовательностями.

Yuki определяет правильную скобочную последовательность по следующим правилам:

• Пустая строка является правильной скобочной последовательностью.

• Если скобочная последовательность $s$ является правильной, то $(s)$ также является правильной скобочной последовательностью.

• Если скобочные последовательности $s$ и $t$ обе являются правильными, то $st$ (конкатенация этих двух скобочных последовательностей) является правильной скобочной последовательностью.

Для скобочной последовательности $s=s_1\ldots s_n$ Yuki определяет $s$ как палиндромную правильную скобочную последовательность тогда и только тогда, когда:

• $s_2\ldots s_{n-1}$ является палиндромной скобочной последовательностью.

• $s_1\ldots s_n$ является правильной скобочной последовательностью.

В частности, пустая строка и () также являются палиндромными правильными скобочными последовательностями.

Например, (())() и ()()(()()) являются палиндромными правильными скобочными последовательностями, а ((())) и ()()(()) — нет.

Теперь у Yuki есть скобочная последовательность $s$ длины $n$, и она хочет найти самую длинную подпоследовательность* $s$, являющуюся палиндромной правильной скобочной последовательностью. Однако Yuki не знает, как это сделать, поэтому вам нужно помочь ей найти длину такой самой длинной подпоследовательности.

*: Последовательность $a$ является подпоследовательностью последовательности $b$ тогда и только тогда, когда $a$ можно получить удалением нуля или более элементов из $b$; в частности, пустая последовательность является подпоследовательностью любой последовательности.

Входные данные

Задача содержит несколько тестовых случаев.

Первая строка содержит положительное целое число $t$ ($1\le t\le5000$), обозначающее количество тестовых случаев.

Для каждого тестового случая:

• Первая строка содержит положительное целое число $n$ ($1\le n\le5000$).

• Вторая строка содержит скобочную последовательность $s$ длины $n$ ($s_i\in\{\texttt{(},\texttt{)}\}$).

Гарантируется, что сумма $n$ по всем тестовым случаям не превышает $10^4$.

Выходные данные

Для каждого тестового случая выведите в отдельной строке целое число — длину самой длинной подпоследовательности, удовлетворяющей условию.

Примеры

Входные данные 1

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

Выходные данные 1

2
0
6

Примечание

Для первого тестового случая:

• Самые длинные подпоследовательности, удовлетворяющие условию, — $s_1s_3=\texttt{()}$ и $s_2s_3=\texttt{()}$, поэтому ответ равен 2.

Для второго тестового случая:

• Самая длинная подпоследовательность, удовлетворяющая условию, — пустая строка, поэтому ответ равен 0.

Для третьего тестового случая:

• Самая длинная подпоследовательность, удовлетворяющая условию, — $s_1s_2s_4s_5s_6s_8=\texttt{()(())}$, поэтому ответ равен 6.