/*
Things to notice:
1. do not calculate useless values
2. do not use similar names
 
Things to check:
1. submit the correct file
2. time (it is log^2 or log)
3. memory
4. prove your naive thoughts 
5. long long
6. corner case like n=0,1,inf or n=m
7. check if there is a mistake in the ds or other tools you use
8. fileio in some oi-contest

9. module on time 
10. the number of a same divisor in a math problem
11. multi-information and queries for dp and ds problems
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pii pair<long long,long long>
#define mp make_pair
#define pb push_back
const int mod=998244353;
const int inf=0x3f3f3f3f;
const int INF=1e18;
int ctoi(char s)
{
	if('a'<=s&&s<='z') return s-'a';
	return 26+s-'A';
}
char itoc(int s)
{
	if(s<26) return 'a'+s;
	return 'A'+(s-26);
}
struct Edge
{
	int to,cap,nxt,w;
}g[20005];
int p[205],eid;
void ins(int u,int v,int cap,int w)
{
	g[eid].to=v,g[eid].cap=cap,g[eid].w=w,g[eid].nxt=p[u];
	p[u]=eid++;
}
void add(int u,int v,int cap,int w)
{
//	cout<<u<<" "<<v<<" "<<cap<<" "<<w<<endl;
	ins(u,v,cap,w),ins(v,u,0,-w);
}
int s,t,pre[205];
int dis[205];
int cur[205];
bool vis[205];
bool inq[205];
void init()
{
	eid=0;
	memset(g,0,sizeof(g));
	memset(p,-1,sizeof(p));
	memset(pre,0,sizeof(pre));
	memset(dis,0,sizeof(dis));
	memset(cur,0,sizeof(cur));
	memset(vis,0,sizeof(vis));
	memset(inq,0,sizeof(inq));
}
bool spfa()
{
	for(int i=0;i<=t;i++) inq[i]=0,pre[i]=-1,dis[i]=inf,cur[i]=p[i];
	dis[s]=0,inq[s]=1;
	queue <int> q;
	while(q.size()) q.pop();
	q.push(s);
	while(q.size())
	{
		int u=q.front();
		q.pop();
		inq[u]=0;
		for(int i=p[u];i!=-1;i=g[i].nxt) if(g[i].cap)
		{
			int v=g[i].to;
			if(dis[u]+g[i].w<dis[v])
			{
				dis[v]=dis[u]+g[i].w,pre[v]=i;
				if(!inq[v]) q.push(v),inq[v]=1;
			}
		}
	}
	return pre[t]!=-1;
}
int cst=0;
int dfs(int u,int fl)
{
	if(u==t) return fl;
	vis[u]=1;
	int ans=0;
	for(int i=cur[u];i!=-1&&ans<fl;i=g[i].nxt)
	{
		cur[u]=i;
		int v=g[i].to;
		if(!vis[v]&&g[i].cap&&dis[v]==dis[u]+g[i].w)
		{
			int x=dfs(v,min(fl-ans,g[i].cap));
			if(x) cst+=x*g[i].w,g[i].cap-=x,g[i^1].cap+=x,ans+=x;
		}
	}
	vis[u]=0;
	return ans;
}
pair<int,int> mcmf()
{
	int fl=0;
	while(spfa())
	{
		int x;
		while((x=dfs(s,inf))) fl+=x;
	}
	return mp(fl,cst);
}
int G[55][55];

int n,to[55];
void solve()
{
	memset(G,0,sizeof(G));
	vector <pii > v1,v2;
	init();
	cin>>n;
	for(int i=0;i<n*n;i++)
	{
		string str;
		cin>>str;
		if(str.size()==1) v1.pb(mp(-1,ctoi(str[0])));
		else v1.pb(mp(ctoi(str[0]),ctoi(str[1])));
	}
	for(int i=0;i<n;i++) for(int j=0;j<n;j++) 
	{
		int x=i*j;
		if(x<n) v2.pb(mp(-1,x));
		else v2.pb(mp(x/n,x%n));
	}
	sort(v1.begin(),v1.end()),sort(v2.begin(),v2.end());
	s=0,t=2*n+1;
	for(int i=0;i<v1.size();i++)
	{
		int j=i;
		while(j+1<v1.size()&&v1[j+1]==v1[j]) j++;
		for(int x=0;x<v2.size();x++)
		{
			int y=x;
			while(y+1<v2.size()&&v2[y+1]==v2[y]) y++;
			if(y-x==j-i)
			{
				int del=j-i+1;
				pii u=v1[i],v=v2[x];
				if((u.fi==-1&&v.fi==-1)||(u.fi!=-1&&v.fi!=-1))
				{
					if(u.fi!=-1) G[u.fi][v.fi]+=del;
					G[u.se][v.se]+=del;
				}
			}
			x=y;
		}
		i=j;
	}
	for(int i=0;i<n;i++) add(s,i+1,1,0),add(i+1+n,t,1,0);
	for(int i=0;i<n;i++) for(int j=0;j<n;j++) add(i+1,j+1+n,1,-G[i][j]);
	mcmf();
	for(int i=0;i<eid;i++)
	{
		int u=g[i].to,v=g[i^1].to;
		swap(u,v);
		if(!g[i].cap)
		{
			if(1<=u&&u<=n&&n+1<=v&&v<=n+n) to[v-n-1]=u-1;
		}
	}
	for(int i=0;i<n;i++) cout<<itoc(to[i]);
	cout<<"\n";
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int _=1;
	cin>>_;
	while(_--) solve();
	return 0;
}