Cho số nguyên dương \(n\),với \(n\) là số chẵn. Cho xâu \(s\) chỉ gồm ký tự \((\) và \()\) trong đó có đúng \(n/2\) dấu ngoặc mở và \(n/2\) dấu ngoặc đóng. Một xâu được gọi là dãy ngoặc đúng khi:

• Xâu rỗng là dãy ngoặc đúng.

• Nếu \(A\) là dãy ngoặc đúng thì \((A)\) là dãy ngoặc đúng.

• Nếu \(A\) và \(B\) là dãy ngoặc đúng thì \(AB\) cũng là dãy ngoặc đúng.

Một phép biến đổi trên xâu là chọn một ký tự trong xâu, di chuyển ký tự đó về cuối xâu, hoặc về đầu xâu.

Yêu cầu: Tính số phép biến đổi ít nhất để xâu \(s\) trở thành dãy ngoặc đúng.

Input

Dòng đầu tiên chứa số nguyên \(T (T≤1000)\) là số bộ test,với mỗi bộ test gồm 2 dòng:

• Dòng thứ nhất chứa số nguyên \(n(n≤1000).\)

• Dòng thứ hai chứa xâu \(s\).

Output

• Ghi trên T dòng, mỗi dòng là kết quả của test tương ứng.

Sample Input

2
2
)(
4
()()

Sample Output

1
0