MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }}); blockquote { font-family: Menlo, Monaco, "Courier New", monospace; color: #333333; display: block; padding: 8.5px; margin: 0 0 9px; font-size: 12px; line-height: 18px; background-color: #f5f5f5; border: 1px solid #ccc; border: 1px solid rgba(0, 0, 0, 0.15); -webkit-border-radius: 4px; -moz-border-radius: 4px; border-radius: 4px; white-space: pre; white-space: pre-wrap; word-break: break-all; word-wrap: break-word; }

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

```plain
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

```plain
howistheprogress
4
ist prog
s ss
how is
the progress```

### Output for the Sample Input 2

```plain
9
12
5
11```

* * *

### Sample Input 3

```plain
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

```plain
2
10
8
0
4
16
1
6
6```

* * *