故事背景

JYY 又重新切换到计算机科学家状态并幵始研宄回文串啦！不过呢，很长的回文串对脑袋不太够用的 JYY 来说有点棘手，所以请你帮忙。

问题描述

JYY 现在有一个由小写字母组成的字符串 $S$。我们用 $S[i,j]$ 表示 $S$ 中从第 $i$ 个字符到第 $j$ 个字符所组成的子串（字符串下标从1开始）。现在JYY有 $Q$ 个询问，其中第 $i$ 个询问 $(L_i,R_i)$ 需要统计满足如下条件的子串 $S[x,y]$ 的数量：

1. $L_i \le x \le y \le R_i$。
2. $S[x,y]$ 是回文串。

请你帮助 JYY 计算这 $Q$ 个询问的答案。

输入格式

输入文件的第一行包含一个字符串 $S$;

第二行包含一个正整数 $Q$;

接下来 $Q$ 行，每行两个整数 $L_i$ 和 $R_i$。

输出格式

输出包含 $Q$ 行每行个一个整数，第 $i$ 行的整数为第 $i$ 个询问的答案。

样例数据

样例 1 输入

abaa
4
1 2
1 3
1 4
3 4

样例 1 输出

2
4
6
3

子任务

对于 $10\%$ 的数据满足 $N,Q \le 50$；

对于 $40\%$ 的数据满足 $N \le 10^5$，$\sum_i (R_i - L_i + 1) \le 10^7$；

对于额外 $20\%$ 的数据满足对于任意 $i$，都有 $L_i = 1$ 或者 $R_i = N$；

对于 $100\%$ 的数据满足 $1 \le N \le 10^5$，$1 \le Q \le 3 \cdot 10^5$，$1 \le L_i \le R_i \le N$。