Problem Background

Once upon a time, there was a glorious kingdom, and Little A was the king within it. He believed that people should live with dignity, and today he intends to bestow dignity upon his subjects.

Problem Description

Little A believes that when a person is respected, he possesses dignity.

Now, Little A has spoken $n$ sentences to Little B, each sentence being a string without spaces and consisting entirely of lowercase letters.

Each sentence is composed of several words. Although we have directly concatenated these words into a string, the semantics of the sentence still relate to the words themselves. For a string $s$, we will provide a partition sequence $p_1, p_2, \dots, p_k$ satisfying $1 \leq p_1 \leq p_2 \leq \dots \leq p_k < |s|$, and we consider that in the sentence $s$, the segments $[1, p_1], [p_1+1, p_2], [p_2+1, p_3], \dots, [p_k + 1, |s|]$ form $k+1$ words. Specifically, if $k=0$, it means the sentence itself is a single word.

For example, for the string $\texttt{irespectyou}$, if the given sequence $p$ is $1, 8$, then the string consists of the words $\texttt{i}$, $\texttt{respect}$, and $\texttt{you}$; if the sequence $p$ is $2, 5, 7$, then the string consists of the words $\texttt{ir}$, $\texttt{esp}$, $\texttt{ec}$, and $\texttt{tyou}$.

For a string $x$, we say that a string $y$ is a substring of $x$ if and only if the string obtained by removing several (possibly zero) characters from the beginning and end of $x$ is equal to $y$. For example, $\texttt{uog}$ is a substring of $\texttt{luogu}$, but $\texttt{ug}$ is not a substring of $\texttt{luogu}$.

Now, given these $n$ sentences, for each sentence, you need to determine how many words in the sentence contain the substring $\texttt{respect}$.

Input Format

The first line is an integer $n$, representing the number of sentences.

The next $3n$ lines, grouped in threes, represent a sentence spoken by Little A to Little B:
- The first line of each group is a string $s$ representing the sentence.
- The second line of each group is an integer $k$ representing the length of the partition sequence.
- The third line of each group is $k$ integers $p_1, p_2, \dots, p_k$ representing the partition sequence.

Note that if $k=0$, there is still an empty line on the third line of each group's data.

Output Format

Output $n$ lines.

For each sentence, output a line containing an integer representing the number of words that contain the substring $\texttt{respect}$.

Sample Input and Output

Sample Input #1

2
irespectyou
2
1 8
herespectsyou
2
2 10

Sample Output #1

1
1

Sample Input #2

1
respect
0

Sample Output #2

1

Notes

Data Size and Constraints

• For $30\%$ of the data, the length of the partitioned substrings $\leq 7$.
• For $60\%$ of the data, there is no word that is not $\texttt{respect}$ and contains $\texttt{respect}$ as a substring.
• For $100\%$ of the data, $1 \leq n \leq 10^3$, $1 \leq p_1 \leq p_2 \leq \dots \leq p_k < |s|$, $k \geq 0$, the input strings contain only lowercase English letters, and the length of the strings does not exceed $10^3$.

见题面 Input 部分

见题面 Output 部分