Problem M
Palindromes

Sam is starting a new company, and has just chosen its name. The name is a string $s=s_1{s}_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_1{s}_2\dots s_n$ consisting of $n$ lowercase letters ($1\le n\le 100000$). The second line contains an integer $m$ ($1\le m\le 100000$), denoting the number of customers. Then $m$ lines follow, each containing a pair of integers $\ell$ and $r$ ($1\le \ell \le r\le 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 \le i\le j\le 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