有一种简单的密码通信协议。发送方传来一段长度为 N 的密文序列，序列中每个字符均取自 {\texttt{A},\ \texttt{C},\ \texttt{G},\ \texttt{T}} 四种信号符号之一。
密码研究员发现了一条规律：当密文中某位置 j 的符号为 \texttt{A}，且紧接着第 j+1 位的符号为 \texttt{C} 时，代表发生了一次密钥激活事件——这往往意味着一段重要信息的开始。
研究员对这段密文共提出了 Q 次区间查询。对于第 i 次查询，给定区间端点 l_i 和 r_i（1 \leq l_i < r_i \leq N），他希望快速得知：满足以下条件的位置 j 共有多少个？
l_i \leq j < r_i,\quad S[j] = \texttt{A},\quad S[j+1] = \texttt{C}
请帮研究员回答全部 Q 次查询。
输入共 Q + 2 行。
第一行包含两个正整数 N 和 Q，分别表示密文序列的长度与查询次数，以单个空格分隔。
第二行包含长度为 N 的字符串 S，表示密文序列，每个字符均属于 {\texttt{A},\ \texttt{C},\ \texttt{G},\ \texttt{T}}。
接下来 Q 行，第 i 行包含两个正整数 l_i 和 r_i，以单个空格分隔。
输出共 Q 行，第 i 行输出第 i 次查询的结果。
8 3 AACGACTA 1 8 3 6 1 3
2 1 1
6 3 GGTCCG 1 6 2 5 3 6
0 0 0
6 3 ACACAC 1 6 2 5 1 2
3 1 1
密文序列为 \texttt{AACGACTA}，下标从 1 起计。各相邻位置情况如下：
| 位置 j | S[j] | S[j+1] | 是否密钥激活 |
|---|---|---|---|
| 1 | \texttt{A} | \texttt{A} | 否 |
| 2 | \texttt{A} | \texttt{C} | 是 |
| 3 | \texttt{C} | \texttt{G} | 否 |
| 4 | \texttt{G} | \texttt{A} | 否 |
| 5 | \texttt{A} | \texttt{C} | 是 |
| 6 | \texttt{C} | \texttt{T} | 否 |
| 7 | \texttt{T} | \texttt{A} | 否 |
密文序列 \texttt{GGTCCG} 中，任意相邻两位均不构成 \texttt{AC} 组合，因此三次查询的答案均为 0。
对于所有测试数据，保证：
| 测试点编号 | N,Q | 特殊性质 |
|---|---|---|
| 1 | N=8,\ Q=3 | 无 |
| 2 | N=2,\ Q=1 | 无 |
| 3 \sim 4 | N=10^5,\ Q=10^5 | A |
| 5 \sim 10 | N\le 10^5,\ Q\le 10^5 | 无 |
特殊性质 A：字符串 S 由 AC 这个长度为 2 的串，连续重复 N/2 次得到。