Sascha

Sascha is a three-year-old child who sometimes pronounces some letters as other letters that are easier for her. The same letter may be pronounced correctly in one position and replaced in another, so the replacement behavior cannot be treated as one consistent rule for the whole word.

You are given a dictionary of valid words. Among the dictionary words with the same length as the word Sascha pronounced, find the word that needs the fewest position-by-position letter substitutions to become the pronounced word. One substitution changes the letter at one position into another letter.

If several dictionary words are equally likely, choose the one that appears earliest in the dictionary.

The first line contains the number of test cases n. (0 < n <= 10000)

Each test case is given in this order.

• One line containing the word as Sascha pronounced it
• One line containing the number of dictionary words w (0 < w <= 10000)
• w lines, each containing one dictionary word

All words contain only lowercase English letters and have length at most 128. Within one test case, every dictionary word has the same length as the word Sascha pronounced.

For each test case, output one line containing the word Sascha most likely meant. If several words are possible, output the dictionary word that appeared first in the input.