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