题目描述

您将得到一个长度为 $N$ 的字符串 $S$，它由 A，C，G 和 T 组成。回答以下 $Q$ 个问题：

问题 $i\ (1\leq i\leq Q)$：你将获得整数 $l_i$ and $r_i$ $(1\leq l_i < r_i \leq  N)$。考虑 $S$ 的子字符串，从索引 $l_i$ 开始到索引 $r_i$（包括两端）。在此字符串中，AC 作为子串出现了多少次？

输入格式

第一行两个整数 $N, Q$。

第二行是一个长度为 $N$ 的字符串 $S$。

接下来 $Q$ 行，每行两个整数 $l_i, r_i$。

输出格式

$Q$ 行，第 $i$ 行表示第 $i$ 个询问的答案。

8 3
ACACTACG
3 7
2 3
1 8

2
0
3