Sub Sub Strings

You are given a string $s$ of length $n$, and must answer $q$ queries.

Each query gives a range $[a, b]$ and asks for the length of the longest contiguous substring inside $s_a s_{a + 1} \ldots s_b$ that consists of only one repeated character.

For example, given the string aaabbbb and the interval $[2, 7]$, the longest such substring is bbbb, which has length $4$.

Positions are 1-indexed.

Input

The first line contains the integers $n$ and $q$.

The second line contains the string $s$.

Each of the next $q$ lines contains two integers $a$ and $b$.

Output

For each query, output a line containing the answer.

Constraints

• $1 \le n \le 10^5$
• $1 \le q \le 10^4$
• $1 \le a \le b \le n$
• $s$ consists only of lowercase English letters.

Example 1

20 10
aaaddddccccaaabbbccc
4 9
2 13
13 17
2 8
18 20
18 19
6 7
3 16
17 18
17 19

4
4
3
4
3
2
2
4
1
2