String Transformations

The Avengers are looking for ways to encrypt their messages so they can hide information from their many opponents. Iron Man suggests the following approach.

You are given several string transformation rules. Each rule (a production) turns a single letter into two letters and is applied to the first occurrence of that letter in the current string. If the letter does not appear, the string is left unchanged. Once a rule produces a new string, that string becomes the target of the next rule, and this continues until no rules remain.

Each word is treated as an independent target string: every rule is applied, in the given order, to each word.

For example, applying the rule A → OA to the string CAT yields COAT, and applying it to DATA yields DOATA.

The first line contains the number of test cases $T$ ($T < 100$). Each test case consists of two lines.

• The first line lists the transformation rules as a sequence of lhs rhs pairs, where lhs is a single uppercase letter and rhs is two uppercase letters. Pairs are separated by whitespace.
• The second line contains the words to transform, separated by spaces.

All words consist of uppercase letters.

For each test case, print one line. The line starts with Transformed strings: , followed by the transformed words in their original order, with each word immediately followed by a single space.