故事背景
JYY 又重新切换到计算机科学家状态并幵始研宄回文串啦！不过呢，很长的回文串对脑袋不太够用的 JYY 来说有点棘手，所以请你帮忙。
问题描述
JYY 现在有一个由小写字母组成的字符串 $S$。我们用 $S[i,j]$ 表示 $S$ 中从第 $i$ 个字符到第 $j$ 个字符所组成的子串（字符串下标从1开始）。现在JYY有 $Q$ 个询问，其中第 $i$ 个询问 $(L_i,R_i)$ 需要统计满足如下条件的子串 $S[x,y]$ 的数量：
- $L_i \le x \le y \le R_i$。
- $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$。