Description

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

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

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

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

Input Format

第一行，两个数 $n,m$。

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

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

Output Format

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

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

16
4
2
2
3
1

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

3
3
2
3
3
17

4 1
yuno
1 4

4

Hint

对于 $10\%$ 的数据，$n,m\le 100$。

对于 $30\%$ 的数据，$n,m \le 2000$。

对于 $100\%$ 的数据，$n,m\le 60000$。

字符集大小有梯度。

在大家回归天空之后，彩名露出了阴冷的笑容。