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.