Counting Words with 'respect' Substring

Person A believes that a person has dignity when he is respected. Now, person A has spoken n sentences to person B. Each sentence is given as a string consisting solely of lowercase letters with no spaces. Although each sentence is formed by concatenating several words, its semantic meaning is still based on the individual words.

For a string \(s\) of length \(|s|\), we are given a segmentation sequence \(p_1, p_2, \dots, p_k\) satisfying \(1 \le p_1 \le p_2 \le \dots \le p_k < |s|\). This indicates that the sentence is divided into \(k+1\) words formed by the segments:

[ [1, p_1],\ [p_1+1, p_2],\ [p_2+1, p_3],\ \dots,\ [p_k+1, |s|] ]

If \(k = 0\), it means that the sentence itself is a single word.

For a given word, we say that a string \(y\) is a substring of \(x\) if and only if \(y\) can be obtained from \(x\) by deleting zero or more characters from the beginning and/or the end of \(x\). For example, uog is a substring of luogu, but ug is not.

Your task is: for each of the n sentences provided, count how many of its words contain the substring respect.

inputFormat

The first line of input contains a single integer n (1 \le n \le 1000), representing the number of sentences.

Then, for each sentence, there are two lines:

1. The first line contains the string s consisting of lowercase letters (1 \le |s| \le 10^5).
2. The second line starts with an integer k (0 \le k < |s|) followed by k integers \(p_1, p_2, \dots, p_k\) (separated by spaces) satisfying \(1 \le p_1 \le p_2 \le \dots \le p_k < |s|\), which denote the split positions.

Note: When k = 0, the sentence is considered as a single word.

outputFormat

For each sentence, output one line containing a single integer — the number of words that contain the substring respect.

sample

1
irespectyou
2 1 8

1