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?

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.

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.

Sample Input 1 | Sample Output 1 |
---|---|

aabacab 5 1 7 1 4 3 7 2 5 5 7 |
11 6 7 5 3 |