### 问题描述 给定一个字符串 $s$，定义它的 **$k$ 前缀** $pre_k$ 为字符串 $s_{1\dots k}$，**$k$ 后缀** $suf_k$ 为字符串 $s_{|s|-k+1\dots |s|}$，其中 $1 \le k \le |s|$。 定义 $\bold{Border}(s)$ 为：**对于 $i \in [1, |s|)$，满足 $\text{pre}_i = \text{suf}_i$** 的字符串 $\text{pre}_i$ 的集合。$\bold{Border}(s)$ 中的每个元素都称之为字符串 $s$ 的 $\operatorname{border}$。 例如 $s=$`'aba'`，则符合要求的有 `a` 串，也就是 $\text{pre}_1=\text{suf}_1$。$\text{pre}_2=ab,\text{suf}_2=ba$，不符合要求。 现有 $m$ 组询问，每组询问给定 $p,q$，求 $s$ 的 **$\boldsymbol{p}$ 前缀** 和 **$\boldsymbol{q}$ 前缀** 的 **最长公共 $\text{border}$** 的长度。 ### 输入格式 输入的第一行为一个字符串 $s$。 输入的第二行为一个整数 $m$。 接下来 $m$ 行，每行两个整数 $p,q$。 ### 输出格式 对于每组询问，一行一个整数，表示答案。若不存在 **最长公共 $\text{border} $**，则输出 $0$。 ### 样例输入 ```text zzaaccaazzccaacczz 3 2 18 10 18 3 5 ``` ### 样例输出 ```text 1 2 0 ``` ### 说明 对于样例： $s$ 的 $p$ 前缀为 `zz`，$q$ 前缀为 `zzaaccaazzccaacczz`。 `zz` 的 $\text{border}$ 只有 `z`。`q` 的 $\text{border}$ 有 `z,zz`。因此最长公共 $\text{border}$ 长度为 $1$。 ### 评测数据规模 $1\le |s|\le 2\times 10^5,1\le p,q\le |s|,1\le m\le 10^5$。 数据保证 $s$ 均由小写英文字母构成。