Đếm Cặp AC Trên Đoạn

Cho một chuỗi $S$ gồm các ký tự $A,C,G,T$. Bạn cần trả lời nhiều truy vấn trên các đoạn con của chuỗi.

Với truy vấn $[l,r]$, hãy đếm số chỉ số $i$ thỏa mãn đồng thời:

• $l\le i<r$;
• $S_i=A$ và $S_{i+1}=C$.

Nói cách khác, một lần xuất hiện của chuỗi hai ký tự AC chỉ được tính khi cả hai ký tự của nó đều nằm hoàn toàn trong đoạn từ $l$ đến $r$.

Input

• Dòng đầu chứa hai số nguyên $n$ và $q$.
• Dòng thứ hai chứa chuỗi $S$ có độ dài $n$.
• Mỗi trong $q$ dòng tiếp theo chứa hai số nguyên $l$ và $r$.

Output

• Với mỗi truy vấn, in số lần xuất hiện của AC trong đoạn tương ứng trên một dòng.

Constraints

• $2\le n\le 10^5$.
• $1\le q\le 10^5$.
• $|S|=n$ và mỗi ký tự thuộc tập {A, C, G, T}.
• $1\le l<r\le n$.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n,q\le 2000$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

10 5
AACACGACCT
1 10
2 5
3 7
5 8
8 10

3
2
1
1
0