Repeat String Query

問題文

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

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

　　条件 $:$ ある文字列 $T$ が存在し、 $T$ を $k$ 個繋げたものが $S'$ と等しい。

制約

• $1\leq |S| \leq 3000$
• $1\leq Q \leq 500000$
• $1\leq l_i \leq r_i \leq |S|$
• $S$ は英小文字からなる
• $Q,l_i,r_i$ は整数 　　

入力

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

出力

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

入力例1

ababcdfababcdfxxxx
4
2 4
1 4
1 14
15 18

出力例1

1
2
2
4

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