CF2180B.Ashmal

You have an array $a$ of $n$ strings $a_{1}, a_{2}, \ldots, a_{n}$, each consisting of lowercase English letters, and an empty string $s$.

In the $i$-th ($1 \le i \le n$) step, you should do one of the following:

• add $a_{i}$ to the beginning of $s$, or
• add $a_{i}$ to the end of $s$.

For example, if before the $i$-th step $s = \mathtt{aba}$ and $a_{i} = \mathtt{bba}$, after the $i$-th step, $s$ will be equal to $\mathtt{ababba}$ or $\mathtt{bbaaba}$.

What's the lexicographically smallest string $s$ you can reach after $n$ steps?

A string $a$ is lexicographically smaller than a string $b$ of the same length, if and only if the following holds:

• in the first position where $a$ and $b$ differ, the string $a$ has a letter that appears earlier in the alphabet than the corresponding letter in $b$.

你有一个由 $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$ 中对应位置的字母。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 1000$) — size of array $a$. The next line contains $n$ strings $a_{1}, a_{2}, \ldots, a_{n}$ ($1 \le |a_i| \le 4000$), each consisting of lowercase English letters.

It is guaranteed that the sum of $n$ over all test cases does not exceed $1000$, and the total length of all strings in the input (over all test cases) does not exceed $4000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, print the lexicographically minimum string $s$ you can reach after $n$ steps.

对于每个测试用例，输出经过 $n$ 步后所能到达的字典序最小的字符串 $s$。

In the first test case, one possible way to construct the lexicographically minimum string $s$ is as follows:

1. After the first step, $s = \mathtt{amir}$ regardless of whether we add it to the beginning or the end, since $s$ was initially empty.
2. In the second step, we add $a_2 = \mathtt{rima}$ to the end of $s$. Now $s = \mathtt{amirrima}$.
3. In the third step, we add $a_3 = \mathtt{amin}$ to the beginning of $s$. Now $s = \mathtt{aminamirrima}$.
4. In the last step, we add $a_4 = \mathtt{nima}$ to the end of $s$. Therefore, the final value of $s$ is $\mathtt{aminamirrimanima}$.

It can be proven that this resulting string is indeed the lexicographically smallest string obtainable after all steps.

在第一个测试用例中，构造字典序最小的字符串 $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$ 的末尾。因此，$s$ 的最终值为 $\mathtt{aminamirrimanima}$。

可以证明，该结果字符串确实是所有操作完成后所能得到的字典序最小的字符串。