Repeat String Query

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

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

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

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

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

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

ababcdfababcdfxxxx
4
2 4
1 4
1 14
15 18

1
2
2
4

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