6851: 不要回文
[Creator : ]
Description
众所周知，回文串是字符串中一种较为优美的存在。回文串的优美之处在于对称之美，即一个回文串从左往右读和从右往左读的结果是一样的，例如 $a,aba,eeffee,arra$ 都是回文串。但也有一些人，不喜欢对称，喜欢那种别具一格、眼花缭乱的美。
小明就是这样的一个人，他杜绝自己的生活中出现回文形式的文字。最近小明家里购置了一个新的智能锁，该锁每天都会随机生成一个字符串，这个字符串中会出现 $a,b,c$ 这三种字符。由于字符串是随机生成的，难免会出现回文的情况。小明不希望出现回文的情况，更极端地，他不希望字符串中有长度超过1的回文子串出现。因此，在得到一个字符串后，他会选择手动地修改某一些字母来避免回文的出现。
现在的问题是，对于给定的字符串，至少需要修改几个字母才能避免回文出现。注意，修改字母时依然只能在 $a,b,c$ 中作选择。
小明就是这样的一个人，他杜绝自己的生活中出现回文形式的文字。最近小明家里购置了一个新的智能锁，该锁每天都会随机生成一个字符串，这个字符串中会出现 $a,b,c$ 这三种字符。由于字符串是随机生成的，难免会出现回文的情况。小明不希望出现回文的情况，更极端地，他不希望字符串中有长度超过1的回文子串出现。因此，在得到一个字符串后，他会选择手动地修改某一些字母来避免回文的出现。
现在的问题是，对于给定的字符串，至少需要修改几个字母才能避免回文出现。注意，修改字母时依然只能在 $a,b,c$ 中作选择。
Input
第一行输入两个数 $n,m$ ，表示字符串长度为 $n$，共有 $m$ 次询问。
第二行输入一个长度为 $n$ 的字符串 $s$。
接下来输入 $m$ 行，每行输入两个数 $l,r$ 表示询问在区间 $[l,r]$ 中至少需要修改几个字母才能避免当前区间出现回文。
第二行输入一个长度为 $n$ 的字符串 $s$。
接下来输入 $m$ 行，每行输入两个数 $l,r$ 表示询问在区间 $[l,r]$ 中至少需要修改几个字母才能避免当前区间出现回文。
Output
输出 $m$ 行，每行一个数表示最少需要修改的次数。
Constraints
$30\%$ 的数据，$1≤n,m≤10$
$100\%$ 的数据，$1≤n,m≤10^5$
$100\%$ 的数据，$1≤n,m≤10^5$
Sample 1 Input
5 4
ababc
1 3
2 5
1 5
3 3
Sample 1 Output
1
1
2
0
长度为 $5$ 的字符串，共有 $4$ 次询问。
询问①：区间 $[1,3]$，$aba$ 为回文串，可以修改为 $cba$，修改 $1$ 次。
询问②：区间 $[2,5]$，$babc$ 中 $bab$ 为回文子串，可以修改为 $cabc$，修改 $1$ 次。
询问③：区间 $[1,5]$，$ababc$ 中 $aba$ 和 $bab$ 都为回文子串，可以修改为 $bcabc$，修改 $2$ 次。
询问④：区间 $[3,3]$，$a$ 为回文串，但是长度为 $1$，因此不需要修改。