Word Segmentation Problem

Given a string s and a list of words, determine whether s can be segmented into a sequence of one or more words present in the list. In other words, check if there exists a space‐separated sequence of dictionary words that equals s.

The segmentation follows the formula:

\( dp[i] = \bigvee_{0 \leq j < i} \Big( dp[j] \wedge \big( s[j:i] \in \text{word\_list} \big) \Big) \)

where \(dp[i]\) is true if the substring \(s[0:i]\) can be segmented. The base case is \(dp[0]=true\).

If the string can be segmented completely, output YES; otherwise, output NO.

inputFormat

The first line contains an integer T representing the number of test cases. Each test case is described as follows:

• The first line of each test case contains the string s. Note that s can be empty.
• The second line contains an integer N denoting the number of words in the dictionary.
• The following N lines each contain a single word.

All input is provided via standard input (stdin).

outputFormat

For each test case, output a single line containing YES if the string can be segmented into one or more dictionary words, or NO otherwise. The output should be sent to standard output (stdout).

## sample

3
applepenapple
2
apple
pen
catsandog
5
cats
dog
sand
and
cat
hello
1
hello

YES
NO
YES

</p>