問題文

ある日ukuさんは自分の名前が奇数長の回文になっていることに気がついた。

うくさんは長さ N の文字列 S を持っている。

うくさんは Q 個の連続な部分文字列 S[L_i:R_i] について、最長の奇数長回文の長さを求めたくなった。

めんどくさがりやなうくさんに代わって、それを求めるプログラムを作成せよ。

(15:24追記) 求める奇数長回文も連続である必要があります。

制約

• 1 \leq N \leq 10^5
• 1 \leq Q \leq 10^5
• S は小文字アルファベットのみからなる長さ N の文字列である
• 1 \leq L_i \leq R_i \leq N

入力例 1

10 3
ukunichiaa
1 10
1 3
9 10

出力例 1

3
3
1

求めるのは奇数長の回文の長さなので、”aa”は条件を満たさないことに注意してください。

入力例 2

9 3
ababcbaba
1 5
1 7
1 9

出力例 2

3
5
9