背景

在原题测试数据基础上，本题评测添加了额外数据。

题目描述

考虑 $n$ 个给定的非空字符串，记作 $s_1, s_2, \cdots, s_n$。现在对于每一个字符串，你需要为其选出一个对应的后缀，分别记作 $\text{suf}_1, \text{suf}_2, \cdots, \text{suf}_n$。对于每个字符串 $s_i$，其后缀 $\text{suf}_i$ 是一个非空子串，其右端点为整个字符串的末端。例如，字符串 “jiangsu” 的所有后缀为 “u”、“su”、“gsu”、“ngsu”、“angsu”、“iangsu” 以及它自身。

所有被选出的后缀可以拼接成一个长字符串 $T = \text{suf}_1 + \text{suf}_2 + \cdots + \text{suf}_n$。这里的加号表示字符串的连接，即将后一个字符串放在前一个的尾部。你对后缀的选取将决定 $T$ 的字典序。现在，你的任务是找出字典序最小的 $T$。

这里有一个关于字典序的提示：比较长度不同的字符串时，较短的字符串通常在末尾填充足够多的“空白”，该空白是一个特殊符号，视为比任何字母都要小。

输入格式

输入的第一行包含一个整数 $T$，表示测试数据的总组数。对于每组数据，第一行包含一个正整数 $n$。接下来的 $n$ 行每行包含一个全部由小写字母组成的字符串，依次对应 $s_1, s_2, \cdots, s_n$。输入中所有字符串的长度之和不超过 500000。

输出格式

对于每组测试数据，输出字典序最小的字符串 $T$。

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

baaac
aaabab
aab

提示

翻译由 DeepSeek V4 Pro 完成