题目描述

你有一个由 $n$ 个字符串 $a_1, a_2, \ldots, a_n$ 组成的数组 $a$，每个字符串均仅包含小写英文字母，并且有一个空字符串 $s$。

在第 $i$ 步（$1 \le i \le n$）时，你可以选择以下两种操作之一：

• 将 $a_i$ 添加到 $s$ 的开头，或者
• 将 $a_i$ 添加到 $s$ 的末尾。

例如，如果在第 $i$ 步之前 $s = \mathtt{aba}$ 且 $a_i = \mathtt{bba}$，则第 $i$ 步后 $s$ 可能为 $\mathtt{ababba}$ 或 $\mathtt{bbaaba}$。

你需要求出在经过 $n$ 步操作后，可以得到的字典序最小的字符串 $s$。

如果两个长度相同的字符串 $a$ 和 $b$，第一个不同的位置处，$a$ 的字母比 $b$ 的字母在字母表中更靠前，则称 $a$ 的字典序小于 $b$。

输入格式

每个测试点包含多组测试数据。第一行为测试用例数 $t$（$1 \le t \le 500$）。接下来的每组测试数据描述如下：

第一行为一个整数 $n$（$1 \le n \le 1000$）——数组 $a$ 的大小。第二行为 $n$ 个字符串 $a_1, a_2, \ldots, a_n$（$1 \le |a_i| \le 4000$），每个字符串由小写英文字母组成。

保证所有测试用例中 $n$ 之和不超过 $1000$，输入中所有字符串的总长度不超过 $4000$。

输出格式

对于每组测试数据，输出经过 $n$ 步操作后可以得到的字典序最小的字符串 $s$。

说明/提示

以第一个测试用例为例，构造字典序最小字符串 $s$ 的一种可能方式如下：

1. 第一步，无论加到开头还是末尾，$s = \mathtt{amir}$，因为初始时 $s$ 为空。
2. 第二步，将 $a_2 = \mathtt{rima}$ 加到 $s$ 的末尾，此时 $s = \mathtt{amirrima}$。
3. 第三步，将 $a_3 = \mathtt{amin}$ 加到 $s$ 的开头，此时 $s = \mathtt{aminamirrima}$。
4. 最后一步，将 $a_4 = \mathtt{nima}$ 加到末尾，所以最终 $s = \mathtt{aminamirrimanima}$。

可以证明，这个结果是可以获得的字典序最小的字符串。

由 ChatGPT 5 翻译

样例

3
4
amir rima amin nima
1
codeforces
3
a ab abc

aminamirrimanima
codeforces
aababc