Subsequence Clue Detection

In this problem, you are given a treasure string and several clue strings. A clue is considered a subsequence of the treasure if all characters of the clue appear in the treasure in the same order (not necessarily consecutively). For each test case, determine how many clues are subsequences of the treasure string.

More formally, given a string T (the treasure) and a string C (the clue), C is a subsequence of T if there exists a sequence of indices i1, i2, ..., ik in T such that T[i1]T[i2]...T[ik] = C and i1 < i2 < ... < ik. You need to output the count of clues that are subsequences for each test case.

inputFormat

The input is provided via standard input (stdin). The first line contains an integer T, representing the number of test cases. For each test case, the format is as follows:

• An integer N denoting the length of the treasure string.
• A line containing the treasure string.
• An integer K representing the number of clue strings.
• K subsequent lines each containing a clue string.

outputFormat

For each test case, output a single integer on a new line which is the count of clue strings that are subsequences of the treasure string.## sample

3
7
TREASURE
3
TRE
SURE
ASTR
6
GDVANC
4
GAC
DAN
DVN
GDN
8
BANANANA
4
BNA
NANA
AAAA
BNAZ

2
4
3