【模板】失配树

给定一个字符串 $s$，定义它的 **$k$ 前缀** $\mathit{pre}_k$ 为字符串 $s_{1\dots k}$，**$k$ 后缀** $\mathit{suf}_k$ 为字符串 $s_{|s|-k+1\dots |s|}$，其中 $1 \le k \le |s|$。 定义 $\bold{Border}(s)$ 为**对于 $i \in [1, |s|)$，满足 $\mathit{pre}_i = \mathit{suf}_i$** 的字符串 $\mathit{pre}_i$ 的集合。$\bold{Border}(s)$ 中的每个元素都称之为字符串 $s$ 的 $\operatorname{border}$。 有 $m$ 组询问，每组询问给定 $p,q$，求 $s$ 的 **$\boldsymbol{p}$ 前缀** 和 **$\boldsymbol{q}$ 前缀** 的 **最长公共 $\operatorname{border}$** 的长度。

第一行一个字符串 $s$。 第二行一个整数 $m$。 接下来 $m$ 行，每行两个整数 $p,q$。

对于每组询问，一行一个整数，表示答案。若不存在公共 $\operatorname{border}$，请输出 $0$。

aaaabbabbaa
5
2 4
7 10
3 4
1 2
4 11

1
1
2
0
2

zzaaccaazzccaacczz
3
2 18
10 18
3 5

1
2
0

样例 $2$ 说明： 对于第一个询问，$2$ 前缀和 $18$ 前缀分别是 ``zz`` 和 ``zzaaccaazzccaacczz``，由于 ``zz`` 只有一个 $\operatorname{border}$，即 ``z``，故最长公共 $\operatorname{border}$ 长度为 $1$。 --- 对于 $16\%$ 的数据，$s$ 中的字符全部相等。 对于 $100\%$ 的数据，$1\leq p,q \le |s|\leq 10^6$，$1 \leq m \leq 10^5$，$s_i \in [\texttt{a}, \texttt{z}]$。