Mikhail's Problem

You are given a string $s$ and several queries. For the $i$-th query, calculate the number of different palindromic substrings of $s\[l\_i .. r\_i]$. A substring is called palindromic if it reads the same from right to left as from left to right. Two substrings are considered different if they differ as strings.

The first line contains a non-empty string $s$ consisting of lowercase English letters. The length of the string does not exceed $10^5$ characters.

The second line contains an integer $q$, the number of queries ($1 \leq q \leq 10^5$). Next $q$ lines contain queries. Each of these lines contains integers $l\_i$ and $r\_i$ separated by a space ($1 \leq l\_i \leq r\_i \leq |s|$).

Output $q$ lines. The $i$-th line must contain one integer: the answer to the $i$-th query.