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.
First line contains a string. Second line contains q. No. of queries.Next q lines contain two integers a and b.
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.