All you have to do is to count the number of palindromic substrings of a substring of a given
string. A palindrome is a string which on reading from left to right or right to left is same. Ex aba
,abcba , abba , d , g , sssssss etc.


A substring is a string that totally within a given string. Ex harsh has substrings
h,a,r,s,h,ha,ar,rs,sh,har,ars,rsh,hars,arsh,harsh.



Input :

First line contains a string. Second line contains q. No. of queries.Next q lines contain two
integers a and b.

Output :

Output q lines containing single number corresponding to the total number of palindromic substrings of the substring ranging from index a to b both inclusive.



Sample Input:

abacaba

4

24

15

33

03


Sample Output:

4

7

1

5