车库

时间限制：1.5 秒
内存限制：256 MB
输入：标准输入
输出：标准输出

题目描述

众所周知，瑞克的车库——他的高科技人工智能助手，能够执行相当复杂的任务。当然，要获得此类系统的控制权限相当困难——必须绕过所有安全层。

但也许你会感到惊讶，最后一层安全保护是 $n$ 个普通的主密码，每个密码是一个字符串，其中第 $i$ 个密码用于访问车库中第 $i$ 个服务的控制权。瑞克并不太在意这种深层级别的安全性，因为除了他之外，还有谁能破解之前所有安全层呢？

但今天他闲来无事，想知道作为车库所有功能的主密码，最短的字符串应该是什么？要作为一个统一的主密码，该字符串必须包含所有 $n$ 个主密码作为连续子串，顺序任意。

当然，瑞克已经成功找到了最短的统一主密码，但你能更快地找到它吗？

输入格式

第一行包含一个整数 $t$ —— 瑞克思考安全问题的现实世界数量（$1 \le t \le 30$）。接下来是 $t$ 组输入数据，每组输入数据由 $n + 1$ 行组成。

每组输入数据的第一行包含一个整数 $n$ —— 车库中有主密码的设备数量（$1 \le n \le 17$）。

接下来的 $n$ 行中，第 $i$ 行包含一个字符串 $s_i$ —— 车库第 $i$ 个服务的主密码（$1 \le |s_i| \le 5 \cdot 10^4$）。密码由小写拉丁字母组成，从 a 到 z。

保证所有输入数据中 $n$ 的总和不超过 $30$。

输出格式

输出一行，即答案——一个长度最小的字符串，包含所有密码作为连续子串（顺序任意）。如果有多个可能的答案，输出任意一个。

示例

输入

3
3
abacaba
baba
saba
4
xzy
yyxx
yyy
xx
5
c
abcde
cde
bcde
cd

输出

sababacaba
yyyxxzy
abcde