Problem M: 1333

Problem

長さ$N$の文字列$S$が与えられる。 以下のクエリを$Q$回処理せよ。

クエリ
$S[L: R]$を$S$の$L$文字目から$R$文字目まで（両端を含む）からなる文字列とする。
$ S[L: R] $を適当な文字列$A,B,C,X$を用いて$AXBXCX(1 \leq |A|,|B|,|C|,|X|)$ と表すことを考え、そのような$X$の中で最長のものの長さを出力する。
ただし、そのような$X$が存在しない場合は代わりに0を出力する。

Input

入力は以下の形式で与えられる。

$N$ $Q$
$S$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_Q$ $R_Q$

$N,Q,L,R$はすべて整数で与えられる。
1行目に$N$, $Q$が空白区切りで与えられる。
2行目に文字列$S$が与えられる。
2+$i(1\leq i \leq Q)$行目に$L_i$, $R_i$が空白区切りで与えられる。これらは$i$番目のクエリにおける$L,R$を表す。

Constraints

入力は以下の条件を満たす。

Output

各クエリについて、最長の$X$の長さを一行に出力せよ。

Sample Input 1

12 3
itisansansan
1 12
5 12
6 7

Sample Output 1

2
1
0

一つ目のクエリにおいて、$A=itis, B=s, C=s, X=an$とおくと、$S[1:12]=AXBXCX$となる。

Sample Input 2

20 2
sensanbyakusanjuusan
1 20
1 14

Sample Output 2

3
1

Sample Input 3

21 6
aaaabaaaabaaaaaaaaaab
1 21
10 21
10 18
4 16
11 21
1 6

Sample Output 3

4
0
2
2
0
1