[HackerEarth] 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 - P14932

P14932 [HackerEarth] 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

提高

题目描述

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.

SAMPLE INPUT
ababa
3
0 3
2 4
1 3

SAMPLE OUTPUT
2
0
1

输入格式

见题面

输出格式

见题面

样例输入

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
100
3
1
18
16
14
12
10
8
6
4
2
0
17
15
13
11
9
7
5
3
1
18
16
14
12
10
8
6
4
2
0
17
15
13
11
9
7
5
3
1
18
16
14
12
10
8
6
4
2
0
17
15
13
11
9
7
5
3
1
18
16
14
12
10
8
6
4
2
0
17
15
13
11
9
7
5
3
1
18
16
14
12
10
8
6
4
2
0
17
15
13
11
9
7
5
3
1
18
16
14

样例输出

题目信息

时间限制	2000 ms
内存限制	256 MB
难度	提高
提交数	0
通过数	0
通过率	0.0%

登录后 AI 解题查看题解登录后提交