You are given a string S.
There are Q queries of the type -
i j - Print the total number of palindromic substrings in the string S[i]S[i+1]....S[j-1]S[j]

Constraints:

1<=Size of String S<=1000
1<=Q<=50000

Input:

First line contains S.
Next line contains Q(number of queries)
Next Q lines contain i and j

Note: String 'S' contains only small case alphabets and 'i' and 'j' are 0-indexed

Output:

Q lines should contain the answers to the corresponding queries

Sample Input:

abaaba
2
0 2
4 4

Sample Output:

4
1