题目描述

给定一个长度为 $N$ 的字符串 $S$，由字符 A，C，G和T组成。

回答以下 $Q$ 个查询:査询$i(1 <i≤ Q)$: 给岀整数 $l_i$ 和 $r_i(1 ≤l_i < r_i< N)$。考虑字符串 $S$ 中从索引$l_i$到索引$r_i$;(两者都包含) 的子串。

在这个子串中，有多少次子字符串 AC 出现?

注意事项

字符串 $T$ 的子串是通过从开头和末尾移除零个或多个字符获得的字符串。

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

输入

第一行一个整数表示字符串长度$N$和询问次数$Q$

第二行一个字符串$S$

接下来$Q$行，表示$Q$次询问

输出

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

8 3
ACACTACG
3 7
2 3
1 8

2
0
3

样例解释

查询 1:字符串 $S$ 中从索引3到索引7的子串是 ACTAC。在这个子串中，AC 作为子字符串出现了两次。

查询 2:字符串 $S$ 中从索引 2到索引3的子串是 CA。在这个子串中，AC 作为子字符串出现了零次。

查询 3:字符串 $S$中从索引1到索引8的子串是 ACACTACG。在这个子串中，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$