Một phòng thí nghiệm lưu một chuỗi DNA ~S~ có độ dài ~N~. Mỗi ký tự của chuỗi là một trong bốn chữ cái A, C, G, T. Một mẫu AC được ghi nhận khi hai ký tự A và C đứng liền nhau theo đúng thứ tự.

Có ~Q~ truy vấn. Với truy vấn thứ ~i~, chỉ xét đoạn liên tiếp từ vị trí ~l_i~ đến vị trí ~r_i~, kể cả hai đầu. Hãy đếm số lần mẫu AC xuất hiện hoàn toàn bên trong đoạn đó.

Input

• Dòng đầu gồm hai số nguyên ~N~ và ~Q~, lần lượt là độ dài chuỗi và số truy vấn.
• Dòng thứ hai chứa chuỗi ~S~ gồm đúng ~N~ ký tự thuộc tập A, C, G, T.
• Mỗi trong ~Q~ dòng tiếp theo gồm hai số nguyên ~l_i~ và ~r_i~, mô tả đoạn của truy vấn thứ ~i~.

Output

• Với mỗi truy vấn, in trên một dòng số lần AC xuất hiện hoàn toàn trong đoạn ~S[l_i..r_i]~.

Giới hạn

• ~2 ≤ N ≤ 10^5~.
• ~1 ≤ Q ≤ 10^5~.
• ~1 ≤ l_i < r_i ≤ N~.
• Mọi ký tự của ~S~ đều thuộc tập A, C, G, T.

Ví dụ

Input

8 3
ACACTACG
3 7
2 3
1 8

Output

2
0
3

Giải thích ví dụ

Đoạn từ vị trí 3 đến 7 là ACTAC, có hai mẫu AC. Đoạn từ vị trí 2 đến 3 là CA, không có mẫu nào. Toàn chuỗi ACACTACG có ba mẫu AC, bắt đầu tại các vị trí 1, 3 và 6.