#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
#include<map>
#include<cstring>
#define maxn 200005
#define dec deccccc

using namespace std;

vector<int> g;

int cnt1[60], cnt2[60], k, cntg[256], ans[256], enc[256], dec[256], das[256], cnt3[60], cnt4[60];

struct node {
	int a, b;
	bool operator<(node y)const {
		return a == y.a ? b < y.b : a < y.a;
	}
};
map<node, int> mp;
struct node2 {
	vector<int> g;
	void print() {
		for(int i : g) {
			if(i) cout << i;
		}cout << endl;
	}
	node2(int siz = 0) {
		g.clear();
		g.resize(siz);
	}
	bool operator<(node2 b)const {
		if(g.size() != b.g.size()) return g.size() < b.g.size();
		for(int i = 0; i < g.size(); i++) {
			if(g[i] != b.g[i]) return g[i] < b.g[i];
		}
		return false;
	}
	bool operator==(node2 b)const {
		return !(*this < b || b < *this);
	}
} nd[64];
map<node2, int> mpn;
map<int, int> cnt;

string s[3005];

void work() {
	mp.clear(); cnt.clear(); mpn.clear();
	memset(ans, 0xff, sizeof(ans)); memset(cntg, 0, sizeof(cntg));
	memset(cnt3, 0, sizeof(cnt3)); memset(cnt4, 0, sizeof(cnt4));
	memset(das, 0xff, sizeof(das));
	cin >> k;
	for(int i = 0; i < k; i++) {
		if(i < 26) dec[i + 97] = i, enc[i] = i + 97;
		else dec[i - 26 + 65] = i, enc[i] = i - 26 + 65;
	}
	memset(cnt1, 0, sizeof(cnt1)); memset(cnt2, 0, sizeof(cnt2));
	for(int i = 0; i < k; i++) {
		for(int j = 0; j < k; j++) {
			cnt1[i * j / k]++, cnt2[i * j % k]++;
		}
	}
	for(int i = 0; i < k; i++) {
		if(mp[(node){cnt1[i], cnt2[i]}]) mp[(node){cnt1[i], cnt2[i]}] = -1;
		else mp[(node){cnt1[i], cnt2[i]}] = i + 1;
	}
	for(int i = 0; i < k * k; i++) {
		cin >> s[i];
		for(int j = 0; j < s[i].size(); j++) s[i][j] = dec[s[i][j]];
		if(s[i].size() == 1) cntg[s[i][0]]++;
	}
	for(int i = 0; i < k; i++) {
		if(cntg[i] == k * 2 - 1) ans[i] = 0, das[0] = i;
	} 
	for(int i = 0; i < k * k; i++) {
		if(s[i].size() ^ 2) s[i] = " " + s[i], s[i][0] = das[0];
		cnt3[s[i][0]]++, cnt4[s[i][1]]++;
	}
	for(int i = 0; i < k; i++) {
		//cout << i << " 34 " << cnt3[i] << ' ' << cnt4[i] << endl;
		if(~mp[(node){cnt3[i], cnt4[i]}] && !~ans[i]) {
			ans[i] = mp[(node){cnt3[i], cnt4[i]}] - 1, das[ans[i]] = i;
			//cout << ans[i] << ' ' << i << endl;
			//cout << i << ' ' << ans[i] << endl;
		}
	}
	//cout << "#" << endl;
	for(int i = 0; i < k; i++) nd[i] = node2(128);
	for(int i = 0; i < k; i++) {
		for(int j = 0; j < k; j++) {
			if(~das[i * j % k] && !~das[i * j / k]) nd[i * j / k].g[i * j % k + 64]++;
			if(~das[i * j / k] && !~das[i * j % k]) nd[i * j % k].g[i * j / k]++;
		}
	}//cout << endl;
	for(int i = 0; i < k; i++) {
		if(!~das[i]) {
			mpn[nd[i]] = i;
			///nd[i].print();
		}
	}
	//cout << endl;
	for(int i = 0; i < k; i++) nd[i] = node2(128);
	for(int i = 0; i < k * k; i++) {
		if(~ans[s[i][0]]) s[i][0] = ans[s[i][0]] | 128;
		if(~ans[s[i][1]]) s[i][1] = ans[s[i][1]] | 128;
		if((s[i][1] & 128) && !(s[i][0] & 128)) nd[s[i][0] & 127].g[(s[i][1] & 127) + 64]++;
		if((s[i][0] & 128) && !(s[i][1] & 128)) nd[s[i][1] & 127].g[s[i][0] & 127]++;
	}//cout << "#" << endl;
	for(int i = 0; i < k; i++) {
		if(!~ans[i]) {
			//nd[i].print();
			ans[i] = mpn[nd[i]]; das[ans[i]] = i;
		}
	}
	for(int i = 0; i < k; i++) cout << (char)(enc[das[i]]); cout << '\n';
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	int _; cin >> _; while(_--) work();
}