E :: Word equations

Time Limit: 7 Seconds    Memory Limit: 131072 KB

You are given a text T and a pattern P. You want to check if you can erase some of the letters of T so that the remaining symbols produce exactly P. For example, the word programming can be partially erased to obtain pong or program or roaming (but not map, as the letters must remain in the same order). Both words consist of small letters of the English alphabet only.

There is just one catch: the text T is encoded by a system of equations. The equations use special symbols (every symbol is denoted by a word in capital letters), each of them encoding some word over the alphabet {a, . . . , z}. Each equation is of one of the following forms:

A = a word over {a, . . . , z}
or
A = B + C

where A, B, C can be any special symbols, and the + sign denotes the concatenation of words. The system is:

  • unambiguous – for a fixed symbol A, there is exactly one equation with A on the left-hand side, and
  • acyclic – if you start from any symbol A and make substitutions according to the equations (right-hand side for left-hand side), you can never obtain an expression containing A again.

Such a system always has a unique solution. For example, in the system:

  • START = FIRST + SECND
  • FIRST = D + E
  • SECND = F + E
  • D = good
  • E = times
  • F = bad

the symbol START encodes the word goodtimesbadtimes.

Given a single word P as the pattern, a system of equations, and one particular starting symbol S of this system, determine whether the pattern P is present in the word encoded by S.

Input

The first line of the input contains the number of test cases T. The descriptions of the test cases follow:

Each test case starts with a line containing a single integer k (1 <= k <= 500)—the number of equations. The next k lines contain equations. Each of them has one of the two forms given in the problem statement, with spaces separating words, plus signs, and equation signs. Each word (including symbol names) is at least one and at most five characters long.

The next line contains a single special symbol (a word in capital letters), while the final line contains a non-empty word of at most 2 000 lowercase letters. These are the starting symbol and the pattern to find, respectively.

Output

Print the answers to the test cases in the order in which they appear in the input. For each test case print the answer in a separate line: YES if the pattern appears in the given encoded word, and NO otherwise.

Sample Input

1
6
START = FIRST + SECND
FIRST = D + E
SECND = F + E
D = good
E = times
F = bad
START
debate

Sample Output

YES
Submit

Source: Central European Regional Contest 2012