Problem Description

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$.

Input Format

The first line contains a string $s$.

The second line contains an integer $m$.

The next $m$ lines each contain two integers $p, q$.

Output Format

For each query, output one integer per line, representing the answer. If there is no common $\operatorname{border}$, output $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

Hint

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