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

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

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

Input

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

S
m
x1 y1
x2 y2
:
xm ym

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

Constraints

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

Output

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

len1
len2
:
lenm

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