Catenyms

Time limit1sMemory limit128 MB

Summary

Find the lexicographically smallest ordering of dictionary words where each word's last letter equals the next word's first letter, using every word once.

Level: Hard8 of 10
Topics: Graph, DFS, Combinatorics, Sorting
Solved: No attempts yet

Problem

A catenym is a pair of words separated by a period such that the last letter of the first word is the same as the first letter of the second. For example, the following are all catenyms:

dog.gopher
gopher.rat
rat.tiger
aloha.aloha
arachnid.dog

A compound catenym is a sequence of three or more words separated by periods such that each adjacent pair of words forms a catenym. For example,

aloha.aloha.arachnid.dog.gopher.rat.tiger

Given a dictionary of lowercase words, find a compound catenym that uses each of the words exactly once. If several such compound catenyms exist, output the lexicographically smallest one; if none exists, report that there is no solution.

Input

The first line contains $t$ , the number of test cases. Each test case begins with an integer $n$ ( $3 \le n \le 1000$ ), the number of words in the dictionary. Then follow $n$ distinct dictionary words, one per line; each word is a string of $1$ to $20$ lowercase letters.

Output

For each test case, output a single line containing the lexicographically smallest compound catenym that uses each dictionary word exactly once. If no such compound catenym exists, output *** instead.

Examples3

Example 1

Input

2
6
aloha
arachnid
dog
gopher
rat
tiger
3
oak
maple
elm

Expected output

aloha.arachnid.dog.gopher.rat.tiger
***

Example 2
Input
```
1
3
ab
bc
cd
```
Expected output
```
ab.bc.cd
```
Example 3
Input
```
1
4
ab
ba
ac
ca
```
Expected output
```
ab.ba.ac.ca
```