#1313 · SỬA CHUỖI

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ệ.