Migrated from Lutece 917 方老师的分身 IV

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

方老师的讲座越办越多，分身也就越来越多。方老师决定给分身取名字。方老师要求，分身的名字一定是可以玩接龙的。方老师要求所有名字能全部这样接起来，同时为了不发生混淆，方老师决定两个名字拼接起来后用.分隔。就比如一个名字是abcde如果另外有一个名字是efgh就可以把这两个名字接起来变成abcde.efgh，然后如果再有一个单词是hif就可以继续拼接成，abcde.efgh.hif。现在方老师想了一个名字，你来帮他判断这个名字是否满足方老师的条件，如果满足，输出字典序最小的拼接方法，否则输出***。

Input

第一行一个$t$，表示测试组数。

第二行一个$n$，表示分身数目（也就是名字数目）（$3\leq n\leq 1000$）

接下来$n$行，每行一个仅包含小写字母的字符串。字符串长度不超过$20$。

Output

输出字典序最小的拼接方法，或者输出***。

Samples

2
3
m
qogduojogfnjovyrkx
hqebeeyztnskbx
7
avmmzsaqy
yesjzorfjaolgnfivhgc
chjdwkb
bacwqnmzekhojj
jqtuxdsmz
zgxkaokehpfibt
tdseqibiigkhp

***
avmmzsaqy.yesjzorfjaolgnfivhgc.chjdwkb.bacwqnmzekhojj.jqtuxdsmz.zgxkaokehpfibt.tdseqibiigkhp

Resources

2014 UESTC Training for Graph Theory