题目背景

题目描述

回归天空是一件庄重的事情，所以卓司决定让大家分批次进行，给每个人给了一个小写字母'a'->'z'作为编号

一个区间的人如果满足他们的编号重排之后可以成为一个回文串，则他们可以一起回归天空，即这个区间可以回归天空

由于卓司是一个喜欢妄想的人，他妄想了m个区间，每次他想知道每个区间中有多少个子区间可以回归天空

因为世界末日要来了，所以卓司的信徒很多

输入格式

第一行两个数n,m

之后一行一个长为n的字符串，代表每个人的编号

之后m行每行两个数l,r代表每次卓司妄想的区间

输出格式

m行，每行一个数表示答案

样例 #1

样例输入 #1

6 6
zzqzzq
1 6
2 4
3 4
2 3
4 5
1 1

样例输出 #1

16
4
2
2
3
1

样例 #2

样例输入 #2

6 6
aaabbb
1 2
2 3
3 4
4 5
5 6
1 6

样例输出 #2

3
3
2
3
3
17

样例 #3

样例输入 #3

4 1
yuno
1 4

样例输出 #3

4

提示

对于100%的数据，n,m<=60000