对回文说不

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

如果一个字符串不含长度至少为 $2$ 的回文子串，就称它是美丽字符串。

一次操作可以把字符串中的任意一个字符改为 a、b、c 中的任意一个。一个字符串的代价是 把它变成美丽字符串所需的最少操作次数。

给定一个只含 a、b、c 的字符串 $s$，回答 $m$ 个询问。每个询问给出 $l,r$，求子串 $s_l s_{l+1}\cdots s_r$ 的代价。

输入格式

第一行包含两个整数 $n,m$，分别表示字符串长度和询问数。

第二行包含长度为 $n$ 的字符串 $s$。

接下来 $m$ 行，每行包含两个整数 $l,r$。

输出格式

对每个询问输出一行一个整数，表示对应子串的代价。

样例输入 1

5 4
baacb
1 3
1 5
4 5
2 3

样例输出 1

1
2
0
1

数据范围

$1\le n,m\le2\cdot10^5$，$s$ 只含字符 a、b、c，$1\le l\le r\le n$。