Master Zhu 有一个字符串 $S[1, \dots, n]$。该字符串仅包含前五个小写英文字母。$S$ 的另一个特殊性质是，其中每个回文子串的长度都小于 20。

对于一个回文串 $P[1, \dots, k]$，其尾部（tail）定义为字符串 $P[\lfloor k/2 \rfloor + 1, \dots, k]$。例如，“aba”的尾部是“ba”，“caac”的尾部是“ac”。

给定 $L$、$R$ 和一个字符串 $T$，Master Zhu 希望你找出 $S[L, \dots, R]$ 中有多少个不同的回文子串，使得 $T$ 是它们尾部的前缀。这里，如果两个子串在 $S$ 中的起始或结束位置不同，则它们被视为不同的子串。

输入格式

输入的第一行包含一个整数 $C$，表示测试用例的数量 ($1 \le C \le 50$)。

每个测试用例的第一行包含一个字符串 $S$，仅由前五个小写英文字母组成 ($1 \le |S| \le 10^5$，且 $S$ 中每个回文子串的长度均小于 20)。

第二行包含一个整数 $q$，表示查询的数量 ($1 \le q \le 10^5$)。接下来的 $q$ 行，每行包含两个整数 $L$ 和 $R$ 以及一个字符串 $T$，其中 $T$ 仅由前五个小写英文字母组成 ($1 \le L \le R \le |S|, 1 \le |T| \le 10$)。

输出格式

对于每个查询，输出一行，包含一个整数：表示 $S[L, \dots, R]$ 中满足 $T$ 是其尾部前缀的不同回文子串的数量。

样例

样例输入 1

1
bceaeeddee
5
5 8 e
3 5 e
1 2 a
5 9 d
5 9 de

样例输出 1

3
2
0
4
1