问题描述

给定一个字符串 $S$ 和 $m$ 个查询。每个查询由两个字符串 $x_i$ 和 $y_i$ 组成。

对于每个查询，找出 $S$ 的子字符串中，以 $x_i$ 开头并以 $y_i$ 结尾的最长子串的长度。

关于字符串 $S$，$|S|$ 表示它的长度。而字符串 $T$ 是字符串 $S$ 的子串，如果存在整数 $i$，满足 $1 \le j \le |T|$ 且 $T_j = S_{i+j}$。其中 $T_j$ 表示 $T$ 的第 $j$ 个字符。

输入

输入以以下格式给出：

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

• 第一行是字符串 $S$。
• 第二行是查询的数量 $m$。
• 接下来的 $m$ 行中，第 $i$ 行是第 $i$ 个查询的字符串 $x_i$ 和 $y_i$，以空格分隔。

约束条件

• $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$ 仅由半角英文字母组成。

输出

以以下格式输出最长子字符串的长度。

$len_1$
$len_2$
:
:
$len_m$

其中，第 $i$ 行表示第 $i$ 个查询的最长子字符串长度 $len_i$。如果不存在满足条件的子字符串，则输出0。

示例输入 1

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

### 示例输出 1

```plain
11
11
4
3
0```

输入字符串 $S$ 是 "abracadabra"。

* 以 "ab" 开头并以 "a" 结尾的子字符串有 "abra"、"abraca"、"abracada"、"abracadabra" 四种，其中最长的是 "abracadabra"，长度为 11。
* 以 "a" 开头并以 "a" 结尾的最长子字符串同样是 "abracadabra"，长度为 11。
* 以 "b" 开头并以 "c" 结尾的最长子字符串是 "brac"，长度为 4。
* 以 "ac" 开头并以 "ca" 结尾的最长子字符串是 "aca"，长度为 3。
* 不存在以 "z" 开头并以 "z" 结尾的子字符串，因此输出 0。

---

### 示例输入 2

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

### 示例输出 2

```plain
9
12
5
11```

---

### 示例输入 3

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

### 示例输出 3

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