题目描述

一个字符串是好的，当且仅当其从左往右读和从右往左读是一样的。

婷婷有一个小写字母构成的字符串，每次他会取出这个字符串的一个子串，他想考考你这个子串有多少个子串是好的。

输入格式

第一行给定小写字母构成的字符串 $S$。

第二行给定一个正整数 $q$，表示询问个数。

之后 $q$ 行，每行给定 $l,r$，表示询问 $S[l:r]$ 有多少个子串是好的。

输出格式

输出 $q$ 行，每行一个整数，表示答案。

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

1
7
3
4
2

说明与提示

样例解释

以第四组询问为例，$aba$ 的好的子序列有 $a,b,a,aba$。

对于 $30\%$ 的数据，$1 \leq |S|,q \leq 100$。

对于 $100\%$ 的数据，$1 \leq |S| \leq 5000,1 \leq q \leq 10^6$。