Counting palindromes

The organizers wanted to hold a practice contest but had nothing prepared, so they took the two words that came to mind, palindrome and data structure, and built a problem out of them.

Seunghyun made a string $S$ that uses only lowercase letters. For integers $i$ and $j$ with $1 \le i \le j \le |S|$, let $S[i..j]$ be the substring formed by joining the $i$-th character of $S$, the $(i+1)$-th character, and so on up to the $j$-th character.

Each query is a pair of integers $a$ and $b$. For that query, count the palindromes that lie inside $S[a..b]$. In other words, count the pairs $(x, y)$ with $a \le x \le y \le b$ such that $S[x..y]$ is a palindrome. Two occurrences of the same substring at different starting positions count separately.

The first line contains the string $S$ that Seunghyun made. $S$ uses only the lowercase letters a through z, and its length satisfies $1 \le |S| \le 100\,000$.

The second line contains the number of queries $Q$ ($1 \le Q \le 300\,000$). Each of the next $Q$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i \le b_i \le |S|$).

For each query, print the number of palindromes inside $S[a_i..b_i]$ on its own line, in the order the queries are given.

A string $T = t_1 t_2 t_3 \cdots t_n$ is a palindrome when reading it from the front gives the same string as reading it from the back, that is, when $t_1 t_2 t_3 \cdots t_{n-1} t_n = t_n t_{n-1} \cdots t_3 t_2 t_1$ holds. A string of length 1 is always a palindrome.

$|S|$ is the length of the string $S$.