Singing Game

Rifat and Shishir have decided to play a game. Rifat will sing a song which is a string of lowercase English letters and Shishir will have to answer some queries on that string.

In each query Rifat will give her $2$ integers $l, r$. Shishir will have to tell Rifat what will be the length of the substring starting from index $l$ to $r$ if each of the characters of the substring are repeated $k$ times. Here $k$ will be the index(1-based indexing) of the characters of the substring, if all the duplicate characters are removed from the substring.

For example, if the substring is “raaffi” then after removing the duplicate characters the substring will be “rafi”. So $k$ for letter ‘r’ will be 1, ‘a’ will be 2, ‘f’ will be 3 and ‘i’ will be 4. Hence the resulting string will be “raaaaffffffiiii”.

Input

The first line contains two integers $n$ and $q$ $(1 \leq n ,q\leq 10^5)$

The second line contains a string which contains $n$ lowercase English letters.

In the next $q$ lines there will be two integers $l$ and $r$ $(1 \leq l,r \leq n, l \leq r)$

Output

For each query print the length of the substing obtained by Shishir.

Sample

Input	Output
8 3 aaruusnn 1 3 3 6 5 8	4 8 9
In the first query, $k$ for letter ‘a’ will be $1$ and $k$ for letter ‘r’ will be $2$. So the final string will be “aarr”. Hence the output will be $4$