J. Secret Folder
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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$$$.

Output

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.

Example
Input
3
3
abacaba
baba
saba
4
xzy
yyxx
yyy
xx
5
c
abcde
cde
bcde
cd
Output
sababacaba
yyyxxzy
abcde