Problem Statement

文字列 $S$ と， $m$ 個のクエリが与えられる． $i$ 番目のクエリは二つの文字列 $x_i,y_i$ で与えられる．

各クエリについて，文字列 $S$ の部分文字列であり， $x_i$ で始まり $y_i$ で終わるものの中で，最長の長さを答えよ．

文字列 $S$ について， $|S|$ は $S$ の長さを表す． また，文字列 $T$ が文字列 $S$ の部分文字列であるとは，ある整数 $i$ が存在して、 $1 \le j \le |T|$ に対して $T_j = S_{i+j}$ を満たすことを言う．ただし $T_j$ は $T$ の $j$ 番目の文字を表す．

Input

入力は以下の形式で与えられる．

$S$
$m$
$x_1$ $y_1$
$x_2$ $y_2$
:
:
$x_m$ $y_m$

• 1行目には，文字列 $S$ が与えられる．
• 2行目には，クエリの個数 $m$ が与えられる．
• 3行目からの $m$ 行のうち $i$ 行目には $i$ 番目のクエリ文字列 $x_i,y_i$ が空白区切りで与えられる．

Constraints

• $1 \le |S| \le 2 \times 10^5 $
• $1 \le m \le 10^5$
• $1 \le |x_i|,|y_i|$
• $\sum_{i=1}^m (|x_i|+|y_i|) \le 2 \times 10^5$
• $S$ 及び $x_i,y_i$ は，半角の英小文字のみからなる．

Output

以下の形式で最大の部分文字列の長さを答えよ．

$len_1$
$len_2$
:
:
$len_m$

1行目からの $m$ 行のうち $i$ 行目には， $i$ 番目のクエリについて，条件を満たす最長の部分文字列の長さ $len_i$ を出力せよ． そのような部分文字列がない場合，0を出力せよ．

Sample Input 1

abracadabra
5
ab a
a a
b c
ac ca
z z

Output for the Sample Input 1

11
11
4
3
0

文字列$S$として，abracadabraが与えられる．

• "ab"で始まり"a"で終わる部分文字列は，"abra"や"abraca","abracada","abracadabra"の4種類があるが，最長の部分文字列は"abracadabra"で，長さは11である．
• "a"で始まり"a"で終わる最長の部分文字列も同様に"abracadabra"で，長さは11である．
• "b"で始まり"c"で終わる最長の部分文字列は"brac"で，長さは4である．
• "ac"で始まり"ca"で終わる最長の部分文字列は"aca"で，長さは3である．
• "z"で始まり"z"で終わる部分文字列は存在しない．よって0を出力する．

Sample Input 2

howistheprogress
4
ist prog
s ss
how is
the progress

Output for the Sample Input 2

9
12
5
11

Sample Input 3

icpcsummertraining
9
mm m
icpc summer
train ing
summer mm
i c
i i
g g
train i
summer er

Output for the Sample Input 3

2
10
8
0
4
16
1
6
6