题目描述

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

手，所以请你帮忙。JYY现在有一个由小写字母组成的字符串S。我们用S[i,j]表示S中从第i个字符到第j个字符所

组成的子串(字符串下标从1开始)。现在JYY有Q个询问，其中第i个询问(Li,Ri)需要统计满足如下条件的子串S[x,y

]的数量：

1、 Li ≤ x ≤ y ≤ Ri。

2、 S[x,y]是回文串。

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

输入格式

第一行包含一个字符串S;

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

接下来Q行，每行两个整数Li和Ri。

对于所有数据满足：1≤|S|≤10^5 & 1≤Q≤3*10^5 & 1≤Li≤Ri≤|S|

输出格式

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

样例

样例输入

abaa

4
1 2
1 3
1 4
3 4

样例输出

2
4
6
3