【题目描述】

最近小明家里购置了一个新的智能锁，该锁每天都会随机生成一个字符串，这个字符串中会出现 这三种字符。由于字符串是随机生成的，难免会出现回文的情况。小明不希望出现回文的情况，更极端地，他不希望字符串中有长度超过1的回文子串出现。因此，在得到一个字符串后，他会选择手动地修改某一些字母来避免回文的出现。 现在的问题是，对于给定的字符串，至少需要修改几个字母才能避免回文出现。注意，修改字母时依然只能在a,b,c中作选择。

【输入格式】

第一行输入两个数n和m，表示字符串长度为n，共有m次询问。 第二行输入一个长度为n的字符串 s。 接下来输入m行，每行输入两个数了l,r 表示询问在区间 [l,r] 中至少需要修改几个字母才能避免当前区间出现回文。

【输出格式】

输出m行，每行一个数表示最少需要修改的次数。

【样例】

输入：
5 4
ababc
1 3
2 5
1 5
3 3
输出：
1
1
2
0