#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],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;
//		reverse(ans,ans+n);
		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();}