Вам дан текст T и шаблон P. Вы хотите проверить, можно ли стереть некоторые буквы T так, чтобы из оставшихся символов получить P. Например, слово programming можно частично стереть, чтобы получить pong или program или roaming (но не map, так как буквы должны оставаться в том же порядке). Оба слова состоят только из маленьких букв английского алфавита.

Имеется лишь одна загвоздка: текст T кодируется системой уравнений. В уравнениях используются специальные символы (каждый символ обозначается словом из заглавных букв), каждый из которых кодирует какое-то слово в алфавите {a, ..., z}. Каждое уравнение имеет одну из следующих форм:

A = слово над алфавитом {a,...,z}

или

A = B + C

где A, B, C могут быть любыми символами, а символ + означает конкатенацию слов. Система является:

• недвусмысленной – для фиксированного символа A имеется в точности одно уравнение с A в левой части;
• ациклической – если Вы начинаете с любого символа A, делаете подстановки в соответствии с уравнениями, и никогда не сможете получить выражение, содержащее A снова.

Такая система всегда имеет единственное решение. Например, в системе:

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

символ START кодирует слово goodtimesbadtimes.

Имея одно слово P в качестве шаблона, систему уравнений и один конкретный начальный символ S этой системы, определите, присутствует ли шаблон P в слове, закодированном S.

Входные данные

Первая строка содержит количество тестов t. Описания тестов приведены ниже:

Каждый тест начинается со строки, содержащей одно целое число k (1 ≤ k ≤ 500) - количество уравнений. Следующие k строк содержат уравнения. Каждый из них имеет одну из двух форм, указанных в условии задачи, с пробелами, разделяющими слова, знаками плюс и знаками уравнений. Каждое слово (включая имена символов) имеет длину не менее одного и не более пяти символов.

Следующая строка содержит один специальный символ (слово заглавными буквами), а заключительная строка содержит непустое слово, содержащее не более 2000 строчных букв. Это начальный символ и шаблон для поиска соответственно.

Выходные данные

Для каждого теста выведите ответ в отдельной строке: YES если шаблон присутствует в заданном слове, и NO в противном случае.