Cho một chuỗi gồm các ngoặc vuông và ngoặc tròn, có thể thực hiện thay đổi dấu ngoặc bằng các thao tác sau:

1. Đổi hướng của ngoặc từ mở thành đóng hoặc ngược lại nhưng không thay đổi tính chất của ngoặc, thao tác này có chi phí là 0.

   Ví dụ: có thể đổi ( thành ) và ) thành ( ; có thể đổi [ thành ] và ] thành [.

2. Đổi bất kì ngoặc vuông thành ngoặc tròn mà không thay đổi hướng, thao tác này có chi phí là 1.

   Ví dụ: có thể đổi [ thành ( nhưng không được ( thành [ ; tương tự, có thể đổi ] thành ) nhưng không được ) thành ].

Các thao tác này có thể được thực hiện với bất kì thứ tự nào cũng như không giới hạn số lần thực hiện.

Cho một chuỗi S có độ dài N và Q câu hỏi có dạng "l r" (1 \leq l < r \leq N). Với mỗi đoạn S[l .. r] hãy cho biết chi phí thấp nhất để sửa thành một dãy ngoặc hợp lệ.

Một dãy ngoặc được coi là hợp lệ nếu thoả mãn những quy tắc sau:

• Dãy rỗng là một dãy ngoặc hợp lệ.
• Nếu "s" là một chuỗi ngoặc đúng, thì "(s)" và "[s]" là một chuỗi ngoặc hợp lệ.
• Nếu "s" và "t" là hai chuỗi ngoặc hợp lệ, thì "st" là một chuỗi ngoặc hợp lệ.

• Dòng thứ nhất chứa số nguyên T (1 \leq T \leq 100) - số lượng test.
• Dòng thứ 2 chứa 2 số nguyên N, Q (2 \leq N \leq 10^6), (1 \leq Q \leq 2 \times 10^5).
• Dòng thứ 3 chứa một chuỗi S có độ dài N có ít nhất 2 kí tự (S[i] \in {(, ), [, ]} ).
• Q dòng tiếp theo mỗi dòng chứa 2 số nguyên l, r (1 \leq l < r \leq N), luôn đảm bảo rằng S[l .. r] có độ dài là chẵn.

Biết rằng, tổng độ dài của N ở tất cả các bộ kiểm thử (testcase) không vượt quá 10^6, tổng độ dài của Q ở tất cả các test không vượt quá 2 \times 10^5.

Với mỗi câu hỏi, yêu cầu in ra một dòng chứa một số nguyên x (x \geq 0) có chi phí thấp nhất để chỉnh sửa dãy ngoặc S[l .. r] thành một dãy ngoặc hợp lệ.

• Subtask 1 (30% số test): N, Q \leq 10^3.
• Subtask 2 (70% số test): Không ràng buộc gì thêm.

Giải thích ví dụ:

• Ví dụ 1: Các dấu ngoặc có cùng tính chất, việc thay đổi thành đóng hoặc mở không mất chi phí, nên chi phí là 0.
• Ví dụ 2:
  • Ở câu hỏi thứ 1, yêu cầu thay đổi với cả chuỗi, S có thể chuyển đổi thành ([([][][])()]) với chi phí là 0.
  • Ở câu hỏi thứ 2, yêu cầu thay đổi (]]], có thể được chuyển thành ([]) với chi phí là 1.
  • Ở câu hỏi thứ 3, yêu cầu thay đổi ([(], có thể được chuyển thành ()() với chi phí là 2.