题目描述

给定一个长度为n且仅包含小写字母的字符串$S=S_1S_2...S_n$，你需要对q次提问作出回答。每次提问包含一个范围L和R，你需要计算在L到R范围内，有多少次小写字母连续出现了两次。

输入格式

第一行输入两个整数n,q,分别表示字符串的长度和提问的次数。 第二行输入一个字符串S； 接下来q行，每行包含一个L和R，表示查询的范围

输出格式

输出q行，每行一个整数为连续出现两次的小写字母的次数。

11 4
mississippi
3 9
4 10
4 6
7 7

2
2
0
0

样例解释：
第一次：$S_3S_4...S_9$=ssissip,有两处分别为$S_3S_4$=ss,$S_6S_7$=ss;
第二次：$S_4S_5...S_{10}$=sissipp,有两处分别为$S_6S_7$=ss,$S_9S_{10}$=pp;
第三次：$S_4S_5S_6$=sis,不存在;
第四次：$S_7$=s,不存在;

5 1
aaaaa
1 5

4

数据规模

%60的数据：
$1 \le n, q \le 3×10^3$
$1 \le L, R \le n$

%100的数据：

$1 \le n, q \le 3×10^5$
$1 \le L, R \le n$