Tracy, "The Mother", has left a note for Ted. This note may be stashed somewhere in all the documents that Ted has. He knows that the note would be at least len characters long. Also, it should be present in one location itself, i.e. it isn't divided into chunks.

You are given a string s, denoting all the stashed up documents that Ted has. The note is naturally just a substring of this. So, as to estimate the gravity of the task in front of him, you, as his son with great programming skills; have decided to help out your father, Ted.

You need to write a program that handles several queries, each query has 2 space separated integers i and len.

Your task is to compute the number of palindromic substrings that begin from the index i and have length at least len.

Input Format:
The input file contains string s on the first line. The next line contains an integer q, denoting the number of queries to be processed. Each query is as described above.

Output Format:
The output file should contain the result of each query, on a new line.

Constraints:
0 < The length of string <= 10^5
0 < The number of queries <= 10^5
0 <= i, len <= 10^5
Use 0-based indexing.