结果比较方式为全文比较（过滤行末空格及文末换行）。

题目描述

标语车间承接横幅制作。一条横幅的正文由主标语和接在它后面的候选标语组成。当前已经定稿的主标语记作 $s$，其长度记作 $n$；待接的候选标语共 $q$ 条，依次记作 $t_1, t_2, \dots, t_q$。排版时每条候选标语都只接在主标语 $s$ 的后面，候选标语之间不互相拼接。主标语与候选标语都只由小写英文字母组成。

版面上相邻的两段内容如果字符完全一致，可以只排一遍。具体地说，从主标语的末尾取 $k$ 个字符、从候选标语的开头取 $k$ 个字符，若这两段逐字符相同，则令它们恰好重合在同一段版面上，这段内容在横幅上只出现一次，候选标语余下的部分紧随其后。其中 $k$ 是非负整数，且不超过主标语长度与候选标语长度的较小者。叠合方向是固定的：只有主标语的末尾一段能与候选标语的开头一段叠合；把主标语的开头一段拿去对候选标语的末尾一段，不属于本车间的排版方式，不参与省料核算。

取 $k = 0$ 表示两段不叠合，候选标语原样接在主标语之后。叠合的长度越大，横幅越短、用纸越省，因此车间关心的是每条候选标语各能让叠合部分最长取到多少。

形式化地说，对每条候选标语 $t_j$，求最大的整数 $k$（$0 \le k \le \min(n, |t_j|)$），使得主标语 $s$ 末尾的 $k$ 个字符与候选标语 $t_j$ 开头的 $k$ 个字符逐字符相同；若不存在这样的 $k > 0$，答案为 $0$。

输入格式

从文件 splice.in 中读入数据。

第一行一个字符串 $s$。 第二行一个整数 $q$。 接下来 $q$ 行，每行一个字符串，依次为 $t_1, t_2, \dots, t_q$。

输出格式

输出到文件 splice.out 中。

共 $q$ 行，第 $j$ 行一个整数，表示候选标语 $t_j$ 能取到的最大叠合长度。

样例

abab
2
babx
ac

3
0

样例 1 解释

主标语是 abab。

• 候选标语 babx 长度为 $4$：先按 $k = 4$ 对一遍，主标语末尾四个字符是 abab，候选标语开头四个字符是 babx，第一处就对不上；退到 $k = 3$，主标语末尾三个字符是 bab，候选标语开头三个字符也是 bab，逐字符都对得上，再往上取已经不行，故最大叠合长度为 $3$。
• 候选标语 ac 长度为 $2$：按 $k = 2$ 对一遍，末尾 ab 与开头 ac 在第二处不同；退到 $k = 1$，末尾 b 与开头 a 也不同。大于 $0$ 的 $k$ 一概不成立，故答案为 $0$。

aabaab
3
aab
baabx
aabaabzz

3
4
6

样例 2 解释

主标语是 aabaab，长度为 $6$。

• 候选标语 aab：$k = 3$ 时主标语末尾三个字符是 aab，与候选标语的三个字符逐一相同；候选标语只有 $3$ 个字符，$k$ 不可能更大，故答案为 $3$。
• 候选标语 baabx：$k = 5$ 时末尾五个字符是 abaab，候选标语开头五个字符是 baabx，第一处就不同；$k = 4$ 时末尾四个字符是 baab，候选标语开头四个字符也是 baab，逐字符都对得上，故答案为 $4$。
• 候选标语 aabaabzz 比主标语长：$k = 6$ 时末尾六个字符是 aabaab，候选标语开头六个字符也是 aabaab；$k$ 不允许超过主标语长度 $6$，故答案为 $6$。

数据范围

对于所有测试数据，保证：

• $1 \le n \le 10^6$，其中 $n = |s|$；
• $1 \le q \le 10^5$；
• $\sum_{j=1}^{q} |t_j| \le 10^6$；
• $s$ 与所有 $t_j$ 只含小写英文字母。

各测试点的约束如下：

• 特殊性质 A：每条候选标语的长度都是 $1$。
• 特殊性质 B：每条候选标语都完整地出现在主标语中，即它是主标语中一段连续的字符。