Yuki phát hiện rằng một dãy ngoặc đối xứng không thể là một dãy ngoặc cân bằng, vì vậy cô đã nghĩ ra một cách khác để định nghĩa dãy ngoặc đối xứng cân bằng.

Yuki định nghĩa dãy ngoặc đối xứng theo các quy tắc sau:

• Xâu rỗng là một dãy ngoặc đối xứng.

• ( và ) là các dãy ngoặc đối xứng.

• Nếu dãy ngoặc $s$ là một dãy ngoặc đối xứng, thì $(s($ và $)s)$ cũng là các dãy ngoặc đối xứng.

Yuki định nghĩa dãy ngoặc cân bằng theo các quy tắc sau:

• Xâu rỗng là một dãy ngoặc cân bằng.

• Nếu dãy ngoặc $s$ là một dãy ngoặc cân bằng, thì $(s)$ cũng là một dãy ngoặc cân bằng.

• Nếu các dãy ngoặc $s$ và $t$ đều là các dãy ngoặc cân bằng, thì $st$ (phép nối hai dãy ngoặc đó) là một dãy ngoặc cân bằng.

Với dãy ngoặc $s=s_1\ldots s_n$, Yuki định nghĩa $s$ là một dãy ngoặc đối xứng cân bằng khi và chỉ khi:

• $s_2\ldots s_{n-1}$ là một dãy ngoặc đối xứng.

• $s_1\ldots s_n$ là một dãy ngoặc cân bằng.

Cụ thể, xâu rỗng và () cũng là các dãy ngoặc đối xứng cân bằng.

Ví dụ, (())() và ()()(()()) là các dãy ngoặc đối xứng cân bằng, còn ((())) và ()()(()) thì không.

Bây giờ, Yuki có một dãy ngoặc $s$ độ dài $n$ và muốn tìm dãy con* dài nhất của $s$ là một dãy ngoặc đối xứng cân bằng. Tuy nhiên, Yuki không biết cách làm, nên bạn cần giúp cô tìm độ dài của dãy con dài nhất như vậy.

*: Dãy $a$ là dãy con của dãy $b$ khi và chỉ khi có thể thu được $a$ bằng cách xóa không hoặc nhiều phần tử khỏi $b$; cụ thể, dãy rỗng là dãy con của mọi dãy.

Dữ liệu vào

Bài toán có nhiều bộ kiểm thử.

Dòng đầu tiên chứa một số nguyên dương $t$ ($1\le t\le5000$), biểu thị số bộ kiểm thử.

Với mỗi bộ kiểm thử:

• Dòng đầu tiên chứa một số nguyên dương $n$ ($1\le n\le5000$).

• Dòng thứ hai chứa một dãy ngoặc $s$ độ dài $n$ ($s_i\in\{\texttt{(},\texttt{)}\}$).

Đảm bảo rằng tổng $n$ trên tất cả các bộ kiểm thử không vượt quá $10^4$.

Dữ liệu ra

Với mỗi bộ kiểm thử, in một dòng chứa một số nguyên biểu thị độ dài của dãy con dài nhất thỏa mãn điều kiện.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

2
0
6

Ghi chú

Với bộ kiểm thử thứ nhất:

• Các dãy con dài nhất thỏa mãn điều kiện là $s_1s_3=\texttt{()}$ và $s_2s_3=\texttt{()}$, nên đáp án là 2.

Với bộ kiểm thử thứ hai:

• Dãy con dài nhất thỏa mãn điều kiện là xâu rỗng, nên đáp án là 0.

Với bộ kiểm thử thứ ba:

• Dãy con dài nhất thỏa mãn điều kiện là $s_1s_2s_4s_5s_6s_8=\texttt{()(())}$, nên đáp án là 6.