题目描述

给定长度为 $N$ 的字符串 $S$，其中包含字符 A、C、G 和 T。回答以下 $Q$ 个查询：

• 第 $i$ 个查询（$1 \leq i \leq Q$）：给定整数 $l_i$ 和 $r_i$（$1 \leq l_i < r_i \leq N$），考虑从索引 $l_i$ 开始到索引 $r_i$ 结束（包括两者）的子串。在该子串中，AC 作为一个子串出现多少次？

注释

字符串 $T$ 的子串是通过从 $T$ 的开头和结尾删除零个或多个字符而得到的字符串。

例如，ATCODER 的子串包括 TCO、AT、CODER、ATCODER 和（空字符串），但不包括 AC。

约束条件

• $2 \leq N \leq 10^5$
• $1 \leq Q \leq 10^5$
• $S$ 是长度为 $N$ 的字符串。
• $S$ 中每个字符都是 A、C、G 或 T。
• $1 \leq l_i < r_i \leq N$

输入

从标准输入读取数据，具体格式如下：

$N$ $Q$ $S$ $l_1$ $r_1$ ： $l_Q$ $r_Q$

输出

打印出 $Q$ 行。第 $i$ 行应包含第 $i$ 个查询的答案。

示例输入 1

8 3
ACACTACG
3 7
2 3
1 8

示例输出 1

2
0
3

• 第 $1$ 个查询：从索引 $3$ 开始到索引 $7$ 结束的子串为 ACTAC。在该子串中，AC 作为一个子串出现了两次。
• 第 $2$ 个查询：从索引 $2$ 开始到索引 $3$ 结束的子串为 CA。在该子串中，AC 作为一个子串没有出现。
• 第 $3$ 个查询：从索引 $1$ 开始到索引 $8$ 结束的子串为 ACACTACG。在该子串中，AC 作为一个子串出现了三次。