Problem J
Palindromes

Sam is starting a new company, and has just chosen its name. The name is a string $s = s_1s_2\dots s_ n$ of length $n$. The name is so long that customers won’t remember the full name. Rather, each customer is going to remember only a substring $t$ of the full name, and different customers may remember different substrings.

Sam is curious how memorable the substring $t$ will be to a customer. Sam believes that the more palindromes $t$ contains, the more memorable it is. Recall that a string $w$ is a palindrome if $w$ reads the same forwards and backwards (for example, the strings radar and level are palindromes, while the string ever is not). After all, customers are sensitive to symmetries in the substring $t$ that he or she remembers, and palindromes are full of symmetries. As such, Sam wants to find out the number of substrings $w$ of $t$ such that $w$ is a palindrome.

The challenge is that Sam’s company will have tons of customers. It is difficult for Sam to know how memorable his company name is to all these customers. Can you help Sam?

Input

The first line of input contains a string $s = s_1s_2 \dots s_ n$ consisting of $n$ lowercase letters ($1 \leq n \leq 100\, 000$). The second line contains an integer $m$ ($1 \leq m \leq 100\, 000$), denoting the number of customers. Then $m$ lines follow, each containing a pair of integers $\ell $ and $r$ ($1 \leq \ell \leq r \leq n$), indicating that a customer remembers precisely the substring $s_\ell s_{\ell +1} \dots s_ r$ between the $\ell $th and $r$th characters inclusive.

Output

For each customer, output a line containing an integer that indicates how memorable the company name is to the customer. More specifically, if this customer remembers the substring $s_\ell s_{\ell +1} \dots s_ r$, output the number of pairs of indices $(i,j)$ such that $\ell \leq i \leq j \leq r$ and $s_ i s_{i+1} \dots s_ j$ is a palindrome.

aabacab
5
1 7
1 4
3 7
2 5
5 7

11
6
7
5
3