Jimmy loves playing with strings. He thinks string $\mbox{A}$ is similar to string $\mbox{B}$ if the following conditions are satisfied:

Both strings have the same length (i.e., $A=a_{0}a_{1}\ldots a_{n-1}$ and $B=b_0b_1\ldots b_{n-1}$).
For each valid pair of indices, $(i,j)$, in the strings, $[a_i=a_j$ and $b_i=b_j]$ or $[a_i\neq a_j$ and $b_i\neq b_j]$.

For example, string $a="adba"$ and $b="bcgb''$ are similar as for $i=0,j=3$, $a[0]==a[3]$ and $b[0]==b[3]$ and for all other $i,j$ pairs $a[i]\neq a[j]$ as well as $b[i]\neq b[j]$.

He has a string, $\mbox{S}$, of size $n$ and gives you $\textit{q}$ queries to answer where each query is in the form of a pair of integers $(l_i,r_i)$. For each substring $S[l_i,r_i]$, find the number of substrings $S[x,y]$ where substring $S[l_i,r_i]$ is similar to substring $S[x,y]$ and print this number on a new line.

Note: Substring $S[x,y]$ is the contiguous sequence of characters from index $\boldsymbol{x}$ to index $y$. For example, if $S=$ abcdefgh, then $S[3,6]=$ cdef.

Input Format

The first line contains two space-separated integers describing the respective values of $n$ and $\textit{q}$.

The second line contains string $\mbox{S}$.

Each line $\boldsymbol{i}$ of the $\textit{q}$ subsequent lines contains two space-separated integers describing the respective values of $l_i$ and $r_i$ for query $\boldsymbol{i}$.

Constraints

$1\leq n,q\leq5\times10^4$
$1\leq L_i\leq R_i\leq n$
$s_i\in\{a,b,c,d,e,f,g,h,i,j\}$

Output Format

For each query, print the number of similar substrings on a new line.

Sample Input
8 4
giggabaj
1 1
1 2
1 3
2 4

Sample Output
8
6
2
1

Explanation

We perform the following sequence of queries:

Strings with length $1$ are all similar, so our answer is $8$.
gi, ig, ga, ab, ba, and aj are similar, so our answer is $6$.
gig and aba are similar, so our answer is $2$.
igg has no similar string, so our answer is $1$.

见题面

见题面