题目描述

给定一个字符串 $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}]$。