You are given a 1-indexed string $S$ of length $N$ that consists of lowercase English alphabets. You are required to provide the answer to queries based on the properties of this string.

You are also provided $Q$ queries. In each query, you are provided two integers $L$ and $R$. Your task is to determine the minimum number of string elements that must be deleted in the substring of $S$. This number must be in the range of $L$ to $R$ including the values of $L$ and $R$. Each distinct character that is obtained in the provided range must occur an equal number of times.

For example, consider string $abcdab$ . Here, the characters that are available in the string are $a,\ b,\ c,\ and\ d$. If one occurrence of $a$ and $b$ is deleted from the string, then one of the possible string is $abcd$. Each character available in the range is occurring for an equal number of times. Therefore, the minimum number of allowed deletions is two.

Now, you are required to equalize the count of characters that occur in the range and not of characters that do not occur in the provided range. You are allowed to delete all occurrences of a character so that it no longer occurs in the range at all.

Input format

• First line: Two space-separated integers $N\ and\ Q$
• Next line: String $S$
• Next $Q$ lines: Two space-separated integers $L\ and\ R$ that denote the parameters of the $i^{th}$ query

Output format

Print the answer to each query in a new line.

Constraints

$1 \le N, Q \le 10^5$

$1 \le L \le R \le N$