시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 1 1 1 100.000%

문제

Master Zhu has a string $S [1, \ldots, n]$. This string can contain only the first five lowercase English letters. Another peculiar property of $S$ is that the length of each palindrome substring in $S$ is less than $20$.

For a palindrome string $P [1, \ldots, k]$, its tail is the string $P [\lfloor k / 2 \rfloor + 1, \ldots, k]$. For example, the tail of the string "aba" is "ba", and the tail of the string "caac" is "ac".

Given $L$, $R$, and a string $T$, Master Zhu wants you to find the number of different palindrome substrings in $S [L, \ldots, R]$ such that $T$ is a prefix of their tails. Here, two substrings are considered different if their starting or ending positions in $S$ differ.

입력

The first line of input contains one integer $C$, the number of test cases ($1 \le C \le 50$).

The first line of each test case contains a string $S$ consisting only of the first five lowercase English letters ($1 \le |S| \le 10^5$, the length of each palindrome substring in $S$ is less than $20$).

The second line contains one integer $q$, the number of queries ($1 \le q \le 10^5$). Each of the next $q$ lines contains two integers $L$ and $R$ and a string $T$ consisting only of the first five lowercase English letters ($1 \le L \le R \le |S|$, $1 \le |T| \le 10$).

출력

For each query, print a single line with a single integer: the number of different palindrome substrings in $S [L, \ldots, R]$ such that $T$ is a prefix of their tails.

예제 입력 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