P3604 美好的每一天

时间限制 $\texttt{3s}$，空间限制 $\texttt{158.2MB}$. 素晴らしき日々 我们的情人，不过是随便借个名字，用幻想吹出来的肥皂泡，把信拿去吧，你可以使假戏成真。我本来是无病呻吟，漫无目的的吐露爱情---现在这些漂泊不定的鸟儿有地方栖息了，你可以从信里看出来。拿去吧---由于不是出自真心，话就说得格外动听，拿去吧，就这么办吧…… 由于世界会在 $7$ 月 $20$ 日完结，作为救世主，间宫卓司要在 $19$ 日让所有人回归天空。 现在已经是 $19$ 日傍晚，大家集合在 C 栋的天台上，一共 $n$ 个人。 在他们面前，便是终之空，那终结的天空。 

回归天空是一件庄重的事情，所以卓司决定让大家分批次进行，给每个人给了一个小写字母 $\texttt{a}\sim\texttt{z}$ 作为编号。 一个区间的人如果满足他们的**编号重排之后可以成为一个回文串**，则他们可以一起回归天空，即这个区间可以回归天空。 由于卓司是一个喜欢妄想的人，他妄想了 $m$ 个区间，每次他想知道每个区间中有多少个子区间可以回归天空。 因为世界末日要来了，所以卓司的信徒很多。 

第一行，两个数 $n,m$。 之后一行，一个长为 $n$ 的字符串，代表每个人的编号。 之后 $m$ 行，每行两个数 $l,r$，代表每次卓司妄想的区间。

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

对于 $10\%$ 的数据，$n,m\le 100$。 对于 $30\%$ 的数据，$n,m \le 2000$。 对于 $100\%$ 的数据，$n,m\le 60000$。 **字符集大小有梯度**。 在大家回归天空之后，彩名露出了阴冷的笑容。