Repeat String Query

2 secs 1024 MB
bayashiko

問題文


文字列 が与えられるので、 個のクエリに答えてください。 個目のクエリは以下の通りです。

  • 文字目から 文字目までの連続部分文字列を とする。次の条件を満たす正整数 の最大値を求めよ。

  条件 ある文字列 が存在し、 個繋げたものが と等しい。

  

制約


  • は英小文字からなる
  • は整数   

入力


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






  

出力


答えを 行出力してください。 行目には、 番目のクエリに対する答えを出力してください。

  

入力例1


ababcdfababcdfxxxx
4
2 4
1 4
1 14
15 18

出力例1


1
2
2
4

"bab" に対する答えは です。
"abab""ab" 個繋げたものなので、"abab" に対する答えは です。
"ababcdfababcdf""ababcdf" 個繋げたものなので、"ababcdfababcdf" に対する答えは です。
"xxxx""x" 個繋げたものなので、"xxxx" に対する答えは です。"xx" 個繋げたものでもありますが、条件を満たす のうち最大値を答えることに注意してください。

Submit


Go (1.14)