A super secret folder is protected by all sorts of locks and passwords.
But you might be surprised that the last layer of protection consists of $$$n$$$ ordinary master passwords in the form of strings. The owner must have thought that no one could break all the previous layers of protection.
However, today, out of boredom, the owner wondered what is the shortest string that could serve as a master password instead of all $$$n$$$ passwords currently implemented. For a string to qualify as a single master password, it must contain all $$$n$$$ master passwords as continuous substrings in any order.
Find the shortest master password that could replace $$$n$$$ existing ones.
The first line contains an integer $$$t$$$ — the number of test cases ($$$1 \le t \le 30$$$). Following this are $$$t$$$ sets of input data, each set described by $$$n + 1$$$ lines.
The first line of the test case contains an integer $$$n$$$ — the number of master passwords ($$$1 \le n \le 17$$$).
In the next $$$n$$$ lines, the $$$i$$$-th line contains the string $$$s_i$$$ — the $$$i$$$-th master password ($$$1 \le |s_i| \le 5 \cdot 10^4$$$). The passwords consist of lowercase letters of the Latin alphabet (from 'a' to 'z').
It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$30$$$.
For each test case output the string of minimal length that contains all passwords as continuous substrings in any order in a separate line. If there are multiple possible answers, output any of them.
33abacabababasaba4xzyyyxxyyyxx5cabcdecdebcdecd
sababacaba yyyxxzy abcde
