Maximize Valid Word Formation

In the land of Teyvat, adventurers participate in a puzzling game where the objective is to extract as many valid words as possible from a given string. You are provided with a dictionary of words. A word is considered valid if it appears exactly once in the dictionary. From a provided string s, you may remove one occurrence of a valid word (if found as a contiguous substring) and continue doing so until no more valid words can be found. Each removal permanently deletes that part of the string so that its letters cannot be re‐used. Your task is to compute the maximum number of valid words that can be extracted from s for each test case.

Note: The removal must be performed on contiguous substrings. If multiple valid words are found, a greedy strategy (i.e. removing the first detected one) is used, which is sufficient for this problem.

The problem can be formally described with the following relation:

[ \text{result} = \max { \text{number of valid words removed from } s } ]

inputFormat

The input is read from stdin and has the following format:

T
n
word1 word2 ... wordn
s
... (repeated for T test cases)

Where:

• T is an integer denoting the number of test cases.
• For each test case, the first line contains an integer n representing the number of words in the dictionary.
• The next line contains n words separated by spaces.
• The following line contains the string s from which words will be removed.

outputFormat

For each test case, print a single integer on a separate line representing the maximum number of valid words that can be formed (i.e. removed) from s using the aforementioned rules. The output is printed to stdout.

## sample

5
5
apple fruit orange carrot mango
applefruitorange
5
apple fruit orange carrot mango
bananaapple
3
apple fruit banana
xyz
4
apple fruit orange carrot
applequickfruit
3
apple orange apple
appleorangeapple

3
1
0
2
1

</p>