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