#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]++;
//                if(x)printf("%c%c ",n-1-x+'a',n-1-y+'a');
//                else printf("%c ",n-1-y+'a');
            }
        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[j][i]*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[j][i]*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[j][i]*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[j][i]*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;
}
/*

iqmonhckjrpgfedlba

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

2
18
a a a a a a a a a a a a a a a a a a a b c d e f g h i j k l m n o p q r a c e g i k m o q ba bc be bg bi bk bm bo bq a d g j m p ba bd bg bj bm bp ca cd cg cj cm cp a e i m q bc bg bk bo ca ce ci cm cq dc dg dk do a f k p bc bh bm br ce cj co db dg dl dq ed ei en a g m ba bg bm ca cg cm da dg dm ea eg em fa fg fm a h o bd bk br cg cn dc dj dq ef em fb fi fp ge gl a i q bg bo ce cm dc dk ea ei eq fg fo ge gm hc hk a j ba bj ca cj da dj ea ej fa fj ga gj ha hj ia ij a k bc bm ce co dg dq ei fa fk gc gm he ho ig iq ji a l be bp ci db dm ef eq fj gc gn hg hr ik jd jo kh a m bg ca cm dg ea em fg ga gm hg ia im jg ka km lg a n bi cd cq dl eg fb fo gj he hr im jh kc kp lk mf a o bk cg dc dq em fi ge ha ho ik jg kc kq lm mi ne a p bm cj dg ed fa fp gm hj ig jd ka kp lm mj ng od a q bo cm dk ei fg ge hc ia iq jo km lk mi ng oe pc a r bq cp do en fm gl hk ij ji kh lg mf ne od pc qb
18
r r r r r r r r r r r r r r r r r r r q p o n m l k j i h g f e d c b a r p n l j h f d b qr qp qn ql qj qh qf qd qb r o l i f c qr qo ql qi qf qc pr po pl pi pf pc r n j f b qp ql qh qd pr pn pj pf pb op ol oh od r m h c qp qk qf qa pn pi pd oq ol og ob no nj ne r l f qr ql qf pr pl pf or ol of nr nl nf mr ml mf r k d qo qh qa pl pe op oi ob nm nf mq mj mc ln lg r j b ql qd pn pf op oh nr nj nb ml md ln lf kp kh r i qr qi pr pi or oi nr ni mr mi lr li kr ki jr ji r h qp qf pn pd ol ob nj mr mh lp lf kn kd jl jb ij r g qn qc pj oq of nm nb mi lp le kl ka jh io id hk r f ql pr pf ol nr nf ml lr lf kl jr jf il hr hf gl r e qj po pb og nl mq md li kn ka jf ik hp hc gh fm r d qh pl op ob nf mj ln kr kd jh il hp hb gf fj en r c qf pi ol no mr mc lf ki jl io hr hc gf fi el do r b qd pf oh nj ml ln kp jr jb id hf gh fj el dn cp r a qb pc od ne mf lg kh ji ij hk gl fm en do cp bq

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