暂无测试数据。

Background

Description

闲着无聊的YGH秒掉上面两道题之后，开始思考有趣的回文串问题了。
他面前就有一个漂浮着的字符串。显然YGH是会manacher的，于是他随手求出了这个字符串的回文子串个数。但是他不满足于这个问题，他打算搞出一个数据结构，能够快速求出这个字符串下标为[l,r]的子串的回文子串个数(相同的回文子串需重复计数)。但是这实在是太简单啦，他打算考考辣鸡YYR，可是辣鸡至极的YYR完全没有思路。
于是，YGH扬长而去，在衣袖带起的一小片尘土之中，沉思的YYR依旧在那里。

Format

Input

第一行为一个字符串S。
第二行一个整数T，表示询问次数。
接下来T行，每行两个整数l、r，表示查询字符串S下标为[l,r]的子串的答案。

Output

输出T行，每行一个整数表示这个询问的答案。

Sample

Input

ababaab
2
1 3
3 7

Output

4
8

Limitation

对于20％的数据，保证 |S| , T<=500
对于40％的数据，保证 |S| , T <=5000
对于100％的数据，保证 |S| <=5000 , T<=100000
1s, 256000KiB for each test case.

Hint

Source

CDQZ TEST