/*
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;
}