You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

在魔法世界中，你是一名资深的列车调度员。车站里不仅停放着普通的列车，还有 $n$ 节特殊的“符文车厢”。每节车厢上都刻有一个由小写英文字母组成的字符串 $a_i$。

这些车厢必须按照输入的顺序（从 $a_1$ 到 $a_n$）依次驶入轨道进行编组。编组规则如下：

1. 第一节车厢 $a_1$ 直接进入轨道，成为当前的列车。
2. 对于后续的每一节车厢 $a_i$ ($2 \le i \le n$)，你可以选择将它挂在当前列车的最前端（车头），或者挂在当前列车的最后端（车尾）。

你的目标是：当所有 $n$ 节车厢都编组完成后，整个列车上字符连接形成的字符串，在字典序上是所有可能情况中最小的。

请输出这个最小的字符串。

输入格式

每个测试点包含多组数据。第一行包含一个整数 $t$ ($1 \le t \le 500$)，表示测试数据的组数。

对于每组数据：

• 第一行包含一个整数 $n$ ($1 \le n \le 1000$)，表示车厢的数量。
• 第二行包含 $n$ 个字符串 $a_1, a_2, \ldots, a_n$，表示按顺序到达的车厢上的符文。

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

输出格式

对于每组测试数据，输出一行，表示编组完成后字典序最小的字符串。

输入输出样例 #1

输入 #1

2
4
amir rima amin nima
3
a ab abc

输出 #1

aminamirrimanima
aababc