CA喜欢字符串，尤其喜欢回文串。 有一天他得到一个字符串，他想知道子串中有多少回文子串，本质相同位置不同的算一种。
第一行 $T$，表示有 $T$ 组数据。 接下来 $T$ 组数据，每组数据第一行为一个字符串 $S$，保证 $S$ 只由小写字母构成。 第二行为一个整数 $Q$，表示询问次数。 接下来 $Q$ 行，每行两个整数 $l,r$，表示询问的子串为 $S[l,r]$。 $1 \le T \le 10,~1 \le length \le 1000,~1 \le Q \le 100000,~1 \le l \le r \le length$
对于每个数据，输出 $Q$ 行答案。
1 abba 2 1 2 1 3
2 3
第一组数据中第一次询问得到的回文串为"a","b"；第二次询问得到的回文串为"a","b","bb"，其中"b"出现了两次，但只记做一次。 你可能需要一个输出输入优化。