Longest Palindromic Substring

2 secs 1024 MB
SSRS

問題文


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

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

制約


  • は整数
  • は英小文字のみからなる
  • の長さは

入力


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

出力


行出力せよ。

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

サンプル


入力1
7
abbabba
7
1 3
2 5
3 5
1 4
4 7
2 6
1 7
出力1
2
3
3
4
4
5
7
入力2
1
a
1
1 1
出力2
1

提出


Go (1.14)