Border Calculation on Substrings

Scape knew that the story earlier was just an accident in his OI career. To prove himself, he decided to teach you the four methods to calculate \(\text{Border}\).

Given a string \(S\) consisting of lowercase letters, you are given \(q\) queries. Each query provides two integers \(l\) and \(r\), and you are required to compute the \(\text{Border}\) of the substring \(s_{l \ldots r}\).

The \(\text{Border}\) of a string \(s\) is defined as the longest proper prefix which is also a suffix. Formally, it is the largest integer \(i\) such that \[ s_{1\ldots i} = s_{|s|-i+1\ldots |s|}, \] where \(|s|\) denotes the length of \(s\). If no such non-empty border exists, the answer is 0.

inputFormat

The input consists of:

1. A single line containing a string \(S\) of lowercase letters.
2. A single line containing an integer \(q\), the number of queries.
3. \(q\) lines, each containing two integers \(l\) and \(r\) (1-indexed), representing a query on the substring \(s_{l \ldots r}\).

outputFormat

For each query, output a single line containing the length of the longest proper border of the substring.

sample

aba
2
1 3
1 2

1
0