Description

小X家住在一条东西向的大街上。在他们家的东面，自东向西依次分布着n幢相似的房屋，编号为1到n,可以用一个长度为n的字符串表示这n幢房屋的颜色。

小X的父亲经常喝醉酒，每次醉酒后他都会稀里糊涂地走到第Ai幢房屋前，然后坚信他现在第Bi幢房屋前。虽然他喝醉了，但是他依然能分清每幢房屋的颜色，并且掏出地图进行比较，只有房屋颜色和地图上一致时，他才会继续向西走。当他发现自己的错误或者不能前进时，就会停下来。现在，小X记录下了每次的数据Ai和Bi，他希望知道父亲最多走过多少幢相同颜色的房屋。

Input Format

第一行两个数n和m，表示n幢房屋和m次询问。

第二行一个长度为n的字符串，仅包含大写字母。

接下来m行，每行两个数Ai和Bi。

Output Format

m行，每个一个数，表示小X的父亲父亲最多走过多少幢相同颜色的房屋。

Sample

【输入样例】

10 6
AABBCCAABB
1 7
7 1
3 4
4 9
2 5
5 5

【输出样例】

4
4
1
1
0
6

Hint

对于60%的数据，n,m≤100。

对于80%的数据，n≤1000。

对于100%的数据，n,m≤100000,Ai,Bi≤n。