题目描述

给你一个字符串s由小写字母组成，有q组询问，每组询问给你两个数，l和r，问在字符串区间l到r的字串中，包含多少回文串。

输入格式

第$1$行，给出s，s的长度小于$5000$ 第$2$行给出$q(1<=q<=10^6)$ 第$2$至$2+q$行 给出每组询问的l和r

输出格式

输出每组询问所问的数量。

样例 #1

样例输入 #1

caaaba
5
1 1
1 4
2 3
4 6
4 5

样例输出 #1

1
7
3
4
2