P5829 [Template] Failure Tree.

Given a string $s$, define its **$k$-prefix** $\mathit{pre}_k$ as the substring $s_{1\dots k}$, and its **$k$-suffix** $\mathit{suf}_k$ as the substring $s_{|s|-k+1\dots |s|}$, where $1 \le k \le |s|$. Define $\bold{Border}(s)$ as the set of strings $\mathit{pre}_i$ that satisfy **for $i \in [1, |s|)$, $\mathit{pre}_i = \mathit{suf}_i$**. Each element in $\bold{Border}(s)$ is called a $\operatorname{border}$ of the string $s$. There are $m$ queries. Each query gives $p, q$. Find the length of the **longest common $\operatorname{border}$** of the **$\boldsymbol{p}$-prefix** and the **$\boldsymbol{q}$-prefix** of $s$.

The first line contains a string $s$. The second line contains an integer $m$. The next $m$ lines each contain two integers $p, q$.

For each query, output one integer per line, representing the answer. If there is no common $\operatorname{border}$, output $0$.

Explanation for Sample 2: For the first query, the $2$-prefix and the $18$-prefix are ``zz`` and ``zzaaccaazzccaacczz``. Since ``zz`` has only one $\operatorname{border}$, namely ``z``, the length of the longest common $\operatorname{border}$ is $1$. --- For $16\%$ of the testdata, all characters in $s$ are the same. For $100\%$ of the testdata, $1\leq p,q \le |s|\leq 10^6$, $1 \leq m \leq 10^5$, and $s_i \in [\texttt{a}, \texttt{z}]$. Constraints. Translated by ChatGPT 5