A8856 | Queries for Number of Palindromes

You've got a string $s=s_{1}s_{2}...\ s_{|s|}$ of length $|s|$ , consisting of lowercase English letters. There also are $q$ queries, each query is described by two integers $l_{i},r_{i}$ $(1<=l_{i}<=r_{i}<=|s|)$ . The answer to the query is the number of substrings of string $s[l_{i}...\ r_{i}]$ , which are palindromes.

String $s[l...\ r]=s_{l}s_{l+1}...\ s_{r}$ $(1<=l<=r<=|s|)$ is a substring of string $s=s_{1}s_{2}...\ s_{|s|}$ .

String $t$ is called a palindrome, if it reads the same from left to right and from right to left. Formally, if $t=t_{1}t_{2}...\ t_{|t|}=t_{|t|}t_{|t|-1}...\ t_{1}$ .

The first line contains string $s$ $(1<=|s|<=5000)$ . The second line contains a single integer $q$ $(1<=q<=10^{6})$ — the number of queries. Next $q$ lines contain the queries. The $i$ -th of these lines contains two space-separated integers $l_{i},r_{i}$ $(1<=l_{i}<=r_{i}<=|s|)$ — the description of the $i$ -th query.

It is guaranteed that the given string consists only of lowercase English letters.

Print $q$ integers — the answers to the queries. Print the answers in the order, in which the queries are given in the input. Separate the printed numbers by whitespaces.