問題文

文字列 S が与えられます。 S[i:j] で S の i 文字目から j 文字目までを取り出した文字列を表すことにします。

文字列 T が次の条件を全て満たすとき、 T は良い文字列であると定義します。

• 1 \leq |T| \leq |S|
• S[i:i+|T|-1] = T を満たす整数 i はちょうど 1 つだけ存在する

例えば S が abcbabc のとき、 cb や abcb 、 abcbabc は良い文字列ですが、 abc や zyx は良い文字列ではありません。

Q 個のクエリが与えられるので処理してください。 i 番目のクエリでは 1 \leq L_i \leq R_i \leq |S| を満たす整数 L_i, R_i が与えられるので、次の問題の答えを出力してください。

• 2 つの整数 l, r であって、 1 \leq l \leq L_i と R_i \leq r \leq |S| を満たし、かつ S[l:r] が良い文字列であるようなものを考える。 r-l+1 の最小値はいくつか？

制約

• S は英小文字からなる
• 1 \leq |S| \leq 2 \cdot 10^5
• 1 \leq Q \leq 2 \cdot 10^5
• 1 \leq L_i \leq R_i \leq |S| \, (1 \leq i \leq Q)

入力例 1

abcbabc
5
2 3
2 5
1 7
4 4
6 6

出力例 1

3
4
7
2
3

1 番目のクエリでは、 l=2, r=4 とすると r-l+1=3 となり、これが最小です。 bc は良い文字列ではないので、 l=2, r=3 とすることはできません。

2 番目のクエリでは、 l=2, r=5 とすると r-l+1=4 となり、これが最小です。

3 番目のクエリでは、 l=1, r=7 とすると r-l+1=7 となり、これが最小です。一般に S そのものは良い文字列であることに注意してください。

入力例 2

yyxxzzyyxx
5
3 3
1 1
10 10
5 5
7 7

出力例 2

3
5
5
2
2

入力例 3

qprrrrrpprqrrppq
20
7 8
6 8
4 7
7 12
6 7
5 5
6 8
4 6
4 4
2 3
7 11
8 9
6 7
11 12
11 15
5 6
4 5
13 13
9 13
5 7

出力例 3

4
4
5
6
4
4
4
5
3
3
5
3
4
2
5
4
4
3
5
4

原案: Forested