Problem Description

Given a string \( s \), define its \( k \)-prefix \( \mathit{pre}_k \) as the substring \( s_{1\dots k} \) and \( 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 \) for \( i \in [1, |s|) \) that satisfy \( \mathit{pre}_i = \mathit{suf}_i \). Each element in \( \bold{Border}(s) \) is called a \( \operatorname{border} \) of string \( s \).

There are \( m \) queries, each query given \( p, q \), asking for the length of the longest common \( \operatorname{border} \) of the \( p \)-prefix and \( 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 a single integer representing the answer. If no common \( \operatorname{border} \) exists, output \( 0 \).

Sample Input and Output

Input Sample #1

aaaabbabbaa
5
2 4
7 10
3 4
1 2
4 11

Output Sample #1

1
1
2
0
2

Input Sample #2

zzaaccaazzccaacczz
3
2 18
10 18
3 5

Output Sample #2

1
2
0

Notes

For the first query in Sample 2, the \( 2 \)-prefix and \( 18 \)-prefix are "zz" and "zzaaccaazzccaacczz" respectively. Since "zz" has only one \( \operatorname{border} \), which is "z", the length of the longest common \( \operatorname{border} \) is \( 1 \).

For \( 16\% \) of the data, all characters in \( s \) are the same.

For \( 100\% \) of the data, \( 1 \leq p, q \le |s| \leq 10^6 \), \( 1 \leq m \leq 10^5 \), and \( s_i \in [\texttt{a}, \texttt{z}] \).

见题面 Input 部分

见题面 Output 部分