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

Input

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

Output

4
4
3
4
3
2
2
4
1
2