Taco Redistribution Problem

You are given t test cases. In each test case, there are n friends; each friend brings items represented by a non‐empty string (each character is an item). Your task is to redistribute exactly one item (character) to each friend so that no friend receives any item that was originally from their own collection. In other words, for the i^th friend with initial string \(S_i\), you must choose one letter \(c\) from the overall pool of distinct items such that \(c \notin S_i\).

If such a redistribution is possible, print one valid assignment as n letters separated by a single space on one line. If it is impossible, output an empty line.

Note: It is guaranteed that if the total number of distinct items is less than n, then a redistribution is impossible.

inputFormat

The input is read from standard input (stdin) and has the following format:

 t
 n
 S1
 S2
 ...
 Sn
 ...

Where:

• t is the number of test cases.
• For each test case, the first line contains an integer n (the number of friends).
• The next n lines each contain a non-empty string Si representing the items of the i^th friend.

outputFormat

For each test case, output one line:

• If a valid redistribution exists, print n letters (separated by a single space) representing the redistributed items, such that the letter assigned to the i^th friend is not contained in Si.
• If no valid redistribution exists, print an empty line.

The output is written to standard output (stdout).

## sample

4
3
abc
def
ghi
3
a
b
c
2
a
a
2
a
b

d b a
b c a
b a

</p>