题目描述

Catenym（链式词对）是指由点号 . 分隔的两个单词，且前一个单词的最后一个字母与后一个单词的最后一个字母相同。例如，以下是几个 catenym：

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

Compound Catenym（复合链式词）是指由三个或更多单词组成的序列，用点号 . 分隔，且每一对相邻单词都构成一个 catenym。例如：

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

给定一个由小写字母组成的词典，你需要找到一个复合链式词，使得该序列包含词典中的每个单词恰好一次。

输入格式

• 第一行输入包含 $t$，表示测试用例的数量。
• 每个测试用例的第一行包含一个整数 $3 \leq n \leq 1000$，表示词典中的单词数量。
• 接下来的 $n$ 行，每行包含一个唯一的词典单词，每个单词由 $1$ 到 $20$ 个小写字母组成。

输出格式

对于每个测试用例，输出一行，给出字典序最小的复合链式词，使得该序列包含每个词典单词恰好一次。如果无解，则输出 ***。

示例输入 1

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

示例输出 1

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