给定 $n$ 个非空字符串 $s_1, s_2, \dots, s_n$。对于每一个字符串，你需要选择一个对应的后缀，记为 $suf_1, suf_2, \dots, suf_n$。对于每个字符串 $s_i$，后缀 $suf_i$ 是一个右端点与原字符串右端点重合的非空子串。例如，字符串 “jiangsu” 的所有后缀为 “u”, “su”, “gsu”, “ngsu”, “angsu”, “iangsu” 以及它本身。

所有选定的后缀可以拼接成一个长字符串 $T = suf_1 + suf_2 + \dots + suf_n$。这里的加号表示字符串的拼接，即将后者接在前者之后。你对后缀的选择将决定 $T$ 的字典序。现在，你的任务是找到字典序最小的 $T$。

关于字典序的提示：在比较不同长度的字符串时，通常会在较短字符串的末尾补上足够的“空格”，这是一种被视为比所有字母都小的特殊符号。

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的总数。对于每个测试用例，第一行包含一个正整数 $n$。接下来的 $n$ 行，每行包含一个由小写字母组成的字符串，分别对应 $s_1, s_2, \dots, s_n$。输入中所有字符串的长度之和不超过 $500\,000$。

输出格式

对于每个测试用例，输出字典序最小的字符串 $T$。

样例

输入 1

3
3
bbb
aaa
ccc
3
aba
aab
bab
2
abababbaabbababba
abbabbabbbababbab

输出 1

baaac
aaabab
aab