#include<bits/stdc++.h>
namespace FRTMLV{
#define ll long long 
#define LD long double
#define i7 __int128
#define re return
#define con continue
using namespace std;
template<class T>inline bool ckmin(T &a,T b){re b<a?a=b,1:0;}
template<class T>inline bool ckmax(T &a,T b){re a<b?a=b,1:0;}
const int N=55;
inline int rd(){
    int d=1,k=0;char c=getchar();
    while(!(c>='0' and c<='9' or c=='-'))c=getchar();if(c=='-')d=-1,c=getchar();
    while(c>='0' and c<='9')k=(k<<3)+(k<<1)+(c^48),c=getchar();
    return d*k;
}
const int mod=998244353;
int n,to[200],a[N],s0[N*N][2];
char s[N*N][3],ch[N],b[N],ans[N];
//ll hs[N*N][N],hs1[N*N][N];
ll hs[N][N],hs1[N][N];
int c[N],c0[N][N];
int c1[N],c10[N][N];


int K;
void dac(int l,int r,int KK){
    if(l>=r)re;
    K=KK;
    sort(b+l,b+r+1,[](char x,char y){re hs[K][to[x]]<hs[K][to[y]];});
    sort(a+l,a+r+1,[](int x,int y){re hs1[K][x]<hs1[K][y];});
    ll nw=-1;
    int la=l-1;
    for(int i=l;i<=r;i++){
        if(i==r||(hs[K][to[b[i]]]!=hs[K][to[b[i+1]]])&&(hs1[K][a[i]]!=hs1[K][a[i+1]])){
            dac(la+1,i,KK+1);
            la=i;
        }
    }
}
signed main(){
//    freopen("data.in","r",stdin);
    int T=rd();
    for(int i=0;i<26;i++)to[i+'a']=i,ch[i]='a'+i,to[i+'A']=i+26,ch[i+26]='A'+i;
    while(T--){
        n=rd();
        memset(c0,0,sizeof c0),memset(c,0,sizeof c);
        memset(c10,0,sizeof c10),memset(c1,0,sizeof c1);
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++){
                int x=i*j/n,y=i*j%n;
                if(x)c10[x][y]++;
                else c1[y]++;
            }
        for(int i=n*n-1;i>=0;i--){
            scanf("%s",s[i]);
            if(s[i][1])++c0[to[s[i][0]]][to[s[i][1]]];
            else ++c[to[s[i][0]]];
        }
        for(int i=0;i<n;i++){
            hs[0][i]=c[i]*c[i];
            for(int j=0;j<n;j++)hs[0][i]+=c0[i][j]*c0[i][j]*1;
            for(int j=0;j<n;j++)hs[0][i]+=c0[j][i]*c0[i][j]*2;
            
            hs1[0][i]=c1[i]*c1[i];
            for(int j=0;j<n;j++)hs1[0][i]+=c10[i][j]*c10[i][j]*1;
            for(int j=0;j<n;j++)hs1[0][i]+=c10[j][i]*c10[i][j]*2;
        }
        for(int k=1;k<=50;k++){
            for(int i=0;i<n;i++){
                hs[k][i]=c[i]*c[i];
                for(int j=0;j<n;j++)hs[k][i]+=hs[k-1][j]*c0[i][j]*c0[i][j]*1;
                for(int j=0;j<n;j++)hs[k][i]+=hs[k-1][j]*c0[j][i]*c0[i][j]*2;
                hs[k][i]%=mod;
                
                hs1[k][i]=c1[i]*c1[i];
                for(int j=0;j<n;j++)hs1[k][i]+=hs1[k-1][j]*c10[i][j]*c10[i][j]*1;
                for(int j=0;j<n;j++)hs1[k][i]+=hs1[k-1][j]*c10[j][i]*c10[i][j]*2;
                hs1[k][i]%=mod;
            }
        }
        for(int i=0;i<n;i++)a[i]=i,b[i]=ch[i];
        dac(0,n-1,0);
        for(int i=0;i<n;i++)ans[a[i]]=b[i];
        ans[n]=0;
        printf("%s\n",ans);
    } 
    re 0;
}
/*
2
3
a b a b b b b c cc
4
d d d d d c b a d b cd cb d a cb bc

*/
}signed main(){re FRTMLV::main();}