Bob and Alice are constantly sending notes to each other during school lessons. As they sit on opposite sides of the classroom, the notes have to be handed over via several of their classmates.
One of those classmates is Mike. He is bored and wants to read the notes. Unfortunately for him, Bob and Alice are encrypting the messages, and he was unable to crack their code.
Then, one day Mike got a lucky break: Bob dropped a paper with decrypted words from one of Alice’s messages. The words were not in their proper order, but this still helped Mike to find the encryption method. Afterwards, he could easily read all their messages.
Problem specification
Alice and Bob have a very simple encryption method: the substitution cipher, using just the lowercase letters of the English alphabet. The key to the cipher is some permutation of letters – a string that contains each of the 26 letters exactly once. For example, one such permutation is ebmhcdfgijklnoapqrswtuvxzy.
To encode a message, simply replace the i-th letter of the alphabet by the i-th letter of the key, for all i. For example, if we use the above key to encode a message, all ‘a’s will be encoded as ‘e’s, all ‘b’s as ‘b’s, all ‘c’s as ‘m’s, and so on. The word “beef” would then be encoded as “bccd”.
You will be given a list of original words, and a list of the same words after they have been encrypted. The words in the second list are not necessarily in the same order as the words in the first list.
Your task is to produce any key that encodes the first set of words into the second set of words.
Input specification
The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.
Each test case starts with an integer n – the number of words in each list. Each of the following n lines contains one original word. Afterwards there are another n lines with the encrypted words. All words use lowercase English letters only. In the easy data set n ≤ 30, in the hard data set n ≤ 10000. No word has more than 30 characters.
Output specification
For each test case, output a single line containing a permutation of the 26 lowercase letters.
You may assume that for each test case at least one valid permutation exists. If there are multiple valid solutions, you may output any of them.
Example
In this case, the original words are dogg and cat. Clearly, the encrypted form of dogg is haff and the encrypted form of cat is mew. This tells us that any permutation of the form e.mh..f.......a....w...... will be a good encryption key. The example output contains one such permutation.