题目描述

给定长度为$N$的纯小写字母字符串$S$，处理$Q$次区间询问。每次询问给定区间$[l_i, r_i]$，要求统计该子串中存在多少对相邻且相同的字符。形式化定义为：求满足$s_p = s_{p+1}$且$l_i \leq p < r_i$的整数$p$的数量。

输入格式

第一行包含两个整数$N$和$Q$，分别表示字符串长度和询问次数
第二行输入字符串$S$
接下来$Q$行，每行两个整数$l_i$和$r_i$表示询问区间

输出格式

输出$Q$行，每行对应一个询问的答案

样例

11 4
mississippi
3 9
4 10
4 6
7 7

2
2
0
0

5 1
aaaaa
1 5

4

说明/提示

样例 1 解释

对于第一个查询，$s_3s_4\cdots s_9=ssissip$，有两个地方连续出现两次相同的小写英文字母：$s_3s_4=ss$，$s_6s_7=ss$

对于第二个查询，$s_4s_5\cdots s_{10}=sissipp$，有两个地方连续出现两次相同的小写英文字母：$s_9s_{10}=pp$，$s_6s_7=ss$

第三个查询 $s_4s_5s_6=sis$，连续出现两次相同小写英文字母的地方为零。

第四个查询 $s_7=s$，连续出现两次相同小写英文字母的地方为零。

样例 2 解释

$s_1s_2\cdots s_5=aaaaa$。有 $4$ 个地方连续出现两次相同的小写字母：$s_1s_2=aa,s_2s_3=aa,s_3s_4=aa,s_4s_5=aa$

数据范围

对于 $70\%$ 的数据，$1\le N,Q\le 50$。

对于 $100\%$ 的数据，$1\le N,Q\le 3\times 10^5,|S|=N$，且 $S$ 仅由小写字母组成，并且保证 $1\le l_i \le r_i \le N$。