题目描述

题目给定一个仅由小写字母组成的字符串 $s$，下标从 $1$ 开始。

有 $Q$ 次询问，每组询问给定两个数 $l$ 和 $r$，表示询问 $s_l \sim s_r$ 这段区间中包含了多少个回文串。注意单独一个字符也算回文串。

输入格式

第一行一个字符串 $s$，保证 $|s| \le 5000$；
第二行一个正整数 $Q$，保证 $1 \le Q \le 10^6$；
接下来 $Q$ 行，每行两个正整数 $l$ 和 $r$，描述一组询问。

输出格式

针对 $Q$ 组询问，分别输出对应的答案。

输入输出样例 #1

输入 #1

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

输出 #1

1
7
3
4
2

说明/提示

考虑第一个测试用例中的第四个查询。字符串 s[4...6] = "aba"。它的回文子串包括："a"、"b"、"a"、"aba"。

Consider the fourth query in the first test case. String $ s[4...\ 6] $ = «aba». Its palindrome substrings are: «a», «b», «a», «aba».

测试点1-5：小规模数据（n ≤ 50，Q ≤ 40），测试基本功能

测试点6-10：中等规模数据（n ≤ 500，Q ≤ 1000），测试算法效率

测试点11-15：较大规模数据（n ≤ 2000，Q ≤ 5000），测试算法优化

测试点16-20：大规模和最大规模数据（n ≤ 5000，Q ≤ 1e6），测试极限性能