Thanh tích điện cân bằng

Cho một dãy gồm $n$ thanh tích điện, đánh số từ $1$ đến $n$. Thanh thứ $i$ mang điện tích $a_i$ bằng $+1$ (ký hiệu là dấu +) hoặc $-1$ (ký hiệu là dấu -).

Với một đoạn thanh liên tiếp, ta định nghĩa tổng đan dấu của đoạn đó là tổng các điện tích, trong đó thanh đầu tiên của đoạn lấy dấu cộng, thanh thứ hai lấy dấu trừ, thanh thứ ba lấy dấu cộng, và cứ thế xen kẽ. Nghĩa là với đoạn gồm các thanh có điện tích $b_1,b_2,b_3,\dots ,b_k$ (theo thứ tự), tổng đan dấu là:

$$b_1-b_2+b_3-b_4+\dots =\sum _{j=1}^k(-1{)}^{j-1}{b}_j.$$

Đoạn được gọi là cân bằng nếu tổng đan dấu của nó bằng $0$. Một đoạn rỗng (không còn thanh nào) cũng được coi là cân bằng.

Có $q$ truy vấn. Mỗi truy vấn cho hai số $l$ và $r$: xét đoạn gồm các thanh từ vị trí $l$ đến $r$. Bạn được phép bỏ đi một số thanh bất kỳ trong đoạn này (các thanh còn lại giữ nguyên thứ tự và việc tính tổng đan dấu được làm lại từ đầu trên các thanh còn lại). Hãy tìm số thanh ít nhất cần bỏ để đoạn còn lại trở nên cân bằng.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ — số bộ dữ liệu.
• Với mỗi bộ:
  • Dòng đầu chứa hai số nguyên $n$ và $q$.
  • Dòng thứ hai chứa xâu $s$ độ dài $n$ gồm các ký tự + và -, mô tả điện tích các thanh.
  • $q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $l$ và $r$ mô tả một truy vấn.

Dữ liệu ra

Với mỗi truy vấn, in ra trên một dòng số thanh ít nhất cần bỏ.

Ràng buộc

• $1\le t\le {10}^3$
• $1\le n,q\le 3·{10}^5$
• $1\le l\le r\le n$
• Tổng $n$ trên tất cả các bộ không vượt quá $3·{10}^5$.
• Tổng $q$ trên tất cả các bộ không vượt quá $3·{10}^5$.

Ví dụ