Background

JYY has returned to his state as a computer scientist and has started researching palindromic strings! However, very long palindromic strings are a bit tricky for JYY's brain, so he needs your help.

JYY has a string $S$ consisting of lowercase letters. We denote $S[i,j]$ as the substring of $S$ from the $i$-th character to the $j$-th character (using 1-based indexing). JYY has $Q$ queries, where the $i$-th query $(L_i, R_i)$ requires counting the number of substrings $S[x,y]$ that satisfy the following conditions:

1. $L_i \le x \le y \le R_i$.
2. $S[x,y]$ is a palindrome.

Please help JYY calculate the answers for these $Q$ queries.

Input

The first line of the input contains a string $S$.

The second line contains a positive integer $Q$.

The next $Q$ lines each contain two integers $L_i$ and $R_i$.

Output

The output contains $Q$ lines, each with a single integer, where the integer on the $i$-th line is the answer to the $i$-th query.

Examples

Input 1

abaa
4
1 2
1 3
1 4
3 4

Output 1

2
4
6
3

Subtasks

For $10\%$ of the data, $N, Q \le 50$.

For $40\%$ of the data, $N \le 10^5$ and $\sum_i (R_i - L_i + 1) \le 10^7$.

For an additional $20\%$ of the data, for any $i$, either $L_i = 1$ or $R_i = N$.

For $100\%$ of the data, $1 \le N \le 10^5$, $1 \le Q \le 3 \cdot 10^5$, and $1 \le L_i \le R_i \le N$.