問題文

$N$ 文字の英小文字のみからなる文字列 $S$ があります。$Q$ 個のクエリが与えられるので、処理してください。

各クエリでは、整数 $L_i, R_i (1 \leq L_i \leq R_i \leq N)$ が与えられるので、$S$ の $L_i$ 文字目から $R_i$ 文字目まで (両端含む) からなる部分文字列を $T_i$ としたとき、$T_i$ の部分文字列で回文であるものの長さの最大値を求めてください。

制約

• $N, Q, L_i, R_i$ は整数
• $S$ は英小文字のみからなる
• $S$ の長さは $N$
• $1 \leq N \leq 200000$
• $1 \leq Q \leq 200000$
• $1 \leq L_i \leq R_i \leq N \ (1 \leq i \leq Q)$

入力

入力は以下の形式で標準入力から与えられます。

$N$

$S$

$Q$

$L_1 \ R_1$

$L_2 \ R_2$

$\vdots$

$L_Q \ R_Q$

出力

$Q$ 行出力せよ。

$i$ 行目には、$i$ 番目のクエリに対する答えを出力せよ。

サンプル

7
abbabba
7
1 3
2 5
3 5
1 4
4 7
2 6
1 7

2
3
3
4
4
5
7

1
a
1
1 1

1