Subsubstrings

You are given a string of length ~n~, and you need to answer ~q~ queries.

• What is the size of the largest substring containing the same character, within the interval ~[a,b]~

i.e. Given the string "aaabbbb" and the interval ~[2,7]~, the largest substring containing the same character would be "bbbb" and have size 4.

Input

This first line contains the integers ~n~ and ~q~.

The second line contains the string.

The following ~q~ lines contain integers ~a~ and ~b~.

Output

For each query, output a line containing the answer.

Containts

• ~1\le n \le 10^5~
• ~1 \le q \le 10^4~
• ~1 \le a \le b \le n~

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