A palindrome is defined as a string $t = t_1 t_2 \dots t_n$ that satisfies the following property: $t_i = t_{n-i+1}$ for $1 \le i \le n$

Given a string $s$ and $q$ queries. For each query, you are given two integers $l_i, r_i$. Can you answer the length of the longest palindromic substring of $s[l_i, r_i]$?

Input

The first line contains a string $s$. The second line contains an integer $q$, representing the number of queries. The next $q$ lines each contain two integers $l_i, r_i$, representing a query for the length of the longest palindromic substring of $s[l_i, r_i]$.

Output

For each query, output an integer representing the length of the longest palindromic substring of $s[l_i, r_i]$.

Examples

Input 1

aaacbdccccadaadabbdbadcbcbbadcadb
6
5 22
1 18
15 33
1 33
8 12
15 27

Output 1

6
6
3
6
3
3

Constraints

For 10% of the data, $n \le 300, q \le 300$. For 30% of the data, $n \le 5000, q \le 5000$. For 70% of the data, $n \le 5 \times 10^4, q \le 5 \times 10^4$. For 100% of the data, $n \le 5 \times 10^5, q \le 5 \times 10^5$.