Bạn cho trước một dãy ngoặc độ dài n, trong đó n là chẵn gồm n/2 ký tự mở ngoặc và n/2 ký tự đóng ngoặc.

Trong một lần di chuyển, bạn có thể chọn chính xác một dấu ngoặc và di chuyển nó đến đầu chuỗi hoặc đến cuối chuỗi (tức là bạn chọn một số chỉ mục i, loại bỏ ký tự thứ i của s và chèn nó vào trước hoặc sau khi tất cả còn lại. ký tự của s).

Nhiệm vụ của bạn là tìm số lần di chuyển tối thiểu cần thiết để có được chuỗi dấu ngoặc đúng từ s. Có thể chứng minh rằng câu trả lời luôn tồn tại dưới các ràng buộc đã cho.

Nhắc lại chuỗi dấu ngoặc đúng là:

• "()" là chuỗi dấu ngoặc đúng;
• nếu s là chuỗi ngoặc đúng thì "(" + s + ")" là chuỗi ngoặc đúng;
• nếu s và t là chuỗi ngoặc đúng thì s + t là chuỗi ngoặc đúng.

Ví dụ: "() ()", "(()) ()", "(())" và "()" là các chuỗi dấu ngoặc đúng, nhưng ") (", "() (" và ")) )" không.

INPUT: MRACKETS.INP

• Dòng đầu tiên chứa số nguyên dương t (1 ≤ t ≤ 1000) – số lượng test thử:
  • Dòng đầu tiên của test thử chứa số n (chẵn và 2 ≤ n ≤ 1000) – độ dài dãy ngoặc
  • Dòng tiếp theo là dãy ngoặc, trong đó n/2 mở ngoặc và n/2 đóng ngoặc

OUTPUT: MRACKETS.OUT

• Đối với mỗi trường hợp kiểm tra, in câu trả lời - số lần di chuyển tối thiểu cần thiết để có được chuỗi dấu ngoặc đúng từ s. Có thể chứng minh rằng câu trả lời luôn tồn tại dưới các ràng buộc đã cho.