问题描述

给定一个只由小写英文字母组成、长度为 $N$ 的字符串 $S = S_1 S_2 \ldots S_N$。

给出 $Q$ 个询问，每个询问由两个整数 $l_i, r_i$ 表示。要求在 $S$ 的第 $l_i$ 到第 $r_i$ 个字符组成的子串 $S_{l_i} S_{l_i+1} \ldots S_{r_i}$ 中，统计满足 $l_i \le p \le r_i - 1$ 且 $S_p = S_{p+1}$ 的整数 $p$ 的个数（即相邻相同字母的对数）。

输入格式

第一行包含两个整数 $N$ 和 $Q$。

第二行包含字符串 $S$。

接下来 $Q$ 行，每行包含两个整数 $l_i$ 和 $r_i$。

输出格式

$Q$ 行，每行一个整数，对应每个询问的答案。

样例输入 1

11 4
mississippi
3 9
4 10
4 6
7 7

样例输出 1

2
2
0
0

样例输入 2

5 1
aaaaa
1 5

样例输出 2

4

样例输入 3

6 2
abcdef
1 3
2 6

样例输出 3

0
0

评测数据规模

对于所有数据，保证 $1 \le N, Q \le 3 \times 10^5$，$1 \le l_i \le r_i \le N$。