Background

As soon as Scape walked into the computer lab, everyone solving problems looked at him and laughed. Someone shouted, "Scape, you must have been crushed by the standard score again!" He did not answer; he said, "Run two programs, check the score sheet," and then he copied out two programs. They deliberately shouted again, "How did you get WA on both the Euler circuit and inversions?" ...

Problem Description

Scape knows that the story above is just an accident in his OI career. To prove himself, he decides to teach you four methods to compute $\text{Border}$.

Given a lowercase-letter string $S$, there are $q$ queries. Each query gives $l, r$, and asks for the $\text{Border}$ of $s_{l\ldots r}$.

$\text{Border}$: For a given string $s$, the largest $i$ such that $s_{1\ldots i} = s_{|s|-i+1\ldots |s|}$. Here $|s|$ is the length of $s$.

Input Format

The first line contains a string $S$.

The second line contains an integer $q$ denoting the number of queries.

Each of the next $q$ lines contains two integers $l, r$ denoting a query.

Output Format

For each query, output the answer.

abbabbaa
3
1 8
1 7
2 7

1
4
3

Hint

• For $30\%$ of the testdata, $n, q \le 1000$.
• For $50\%$ of the testdata, $n, q \le 2\times 10^4$.
• For another $30\%$ of the testdata, the answer is at least half of $r - l + 1$.
• For $100\%$ of the testdata, $n, q \le 2\times 10^5$.

Translated by ChatGPT 5