题目描述

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

输入格式

第 $1$ 行，给出 $s$，$s$ 的长度小于 $5000$。

第 $2$ 行给出 $q$，其中 $1\leq q\leq 10^6$

第 $2$ 至 $2+q$ 行，给出每组询问的 $l$ 和 $r$

输出格式

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

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

1
7
3
4
2