1 #include<stdio.h>
  2 #include<string.h>
  3 #include<math.h>
  4 #include<iostream>
  5 #include<limits.h>
  6 #include<algorithm>
  7 #include<queue>
  8 #include<vector>
  9 #include<set>
 10 #include<stack>
 11 #include<string>
 12 #include<sstream>
 13 #include<map>
 14 #include<cctype>
 15 using namespace std;
 16 struct node
 17 {
 18     char s[31];
 19     int first,last;
 20 }a[1001];
 21 int n,degree_in[1001],degree_out[1001],order[1001],visited[1001];
 22 bool cmp(node a,node b)
 23 {
 24     return strcmp(a.s,b.s)<0;
 25 }
 26 int check()
 27 {
 28     int x1,x2,ans=0,i;
 29     x1=x2=0;
 30     for(i=0;i<26;++i)
 31     {
 32         if(abs(degree_in[i]-degree_out[i])>=2)
 33             return -1;
 34         else if(degree_in[i]-degree_out[i]==1)
 35             x1++;
 36         else if(degree_in[i]-degree_out[i]==-1)
 37         {
 38             x2++;
 39             ans=i;
 40         }
 41     }
 42         if(x1>1||x2>1) //当时三个度时，必定是 12 和21，相同的不能大于等于2，不然不能构成欧拉回路
 43             return -1;
 44         else if(x1==0)
 45         {
 46             for(i=0;i<26;++i)
 47                 if(degree_out[i])
 48                     return i; //找到一个就行
 49         }
 50         else
 51             return ans;
 52 }
 53 bool DFS(int st,int cnt)
 54 {
 55     int i;
 56     if(cnt==n)
 57         return 1;
 58     for(i=0;i<n;++i)
 59     {
 60         if(a[i].first<st||visited[i])
 61             continue;
 62         else if(a[i].first>st)
 63             return false;
 64         visited[i]=true;
 65         order[cnt]=i;
 66         if(DFS(a[i].last,cnt+1))
 67             return 1;
 68         visited[i]=false;//回溯判断是否形成欧拉路径
 69     }
 70     return false;
 71 }
 72 int main()
 73 {
 74     int t;
 75     scanf("%d",&t);
 76     while(t--)
 77     {
 78         for(int i=0;i<1001;i++)
 79         {
 80             degree_in[i]=degree_out[i]=visited[i]=0;    // 比 三个 memset 要快
 81         }
 82         scanf("%d",&n);
 83         for(int i=0;i<n;i++)
 84         {
 85             scanf("%s",a[i].s);
 86             int len=strlen(a[i].s);
 87             a[i].first=a[i].s[0]-'a';
 88             a[i].last=a[i].s[len-1]-'a';
 89             degree_out[a[i].s[0]-'a']++;
 90             degree_in[a[i].s[len-1]-'a']++;
 91         }
 92         int flag=check();
 93         if(flag==-1)
 94         {
 95             printf("***
");
 96             continue;
 97         }
 98         sort(a,a+n,cmp);
 99         if(!DFS(flag,0))
100         {
101             printf("***
");
102             continue;
103         }
104         printf("%s",a[order[0]].s);
105         for(int i=1;i<n;i++)
106             printf(".%s",a[order[i]].s);
107         printf("
");
108     }
109     return 0;
110 }