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 ababba or 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$.

Input

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$.

Output

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

Note

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 aminamirrimanima.

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

Samples

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

aminamirrimanima
codeforces
aababc