#include<bits/stdc++.h>

#define fi first
#define se second
#define pb push_back

typedef long long ll;
#define int ll

using namespace std;

void boris(int n)
{
    vector<array<int, 3> > cnt(n);
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
    {
        cnt[i*j%n][1]++;
        if (i*j >= n)
            cnt[i*j/n][0]++;
        else
            cnt[i*j%n][2]++;
    }

    set<array<int, 3> > st(cnt.begin(), cnt.end());
    sort(cnt.begin(), cnt.end());
    int ok = 0;
    for (int i=0; i<n; i++)
    {
        bool cur = true;
        if (i>0 && cnt[i] == cnt[i-1])
            cur = false;
        if (i<n-1 && cnt[i] == cnt[i+1])
            cur = false;
        ok += cur;
    }
    cout<<ok<<"/"<<n<<" "<<n-ok<<"\n";
}

vector<int> solve(int n, vector<pair<int, int> > v)
{
    vector<array<int, 3> > cnt(n);
    vector<array<int, 3> > vcnt(n);
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
    {
        cnt[i*j%n][1]++;
        if (i*j >= n)
            cnt[i*j/n][0]++;
        else
            cnt[i*j%n][2]++;

        int x = v[i*n+j].fi;
        int y = v[i*n+j].se;
        vcnt[y][1]++;
        if (x == -1)
            vcnt[y][2]++;
        else
            vcnt[x][0]++;
    }

    map<array<int, 3>, pair<int, int> > mp;
    for (int i=0; i<n; i++)
    {
        mp[cnt[i]].fi++;
        mp[cnt[i]].se=i;
    }
//    for (int i=0; i<n; i++)
//    {
//        cout<<i<<" -> "<<cnt[i][0]<<" "<<cnt[i][1]<<" "<<cnt[i][2]<<"\n";
//    }
//    for (int i=0; i<n; i++)
//    {
//        cout<<i<<" -> "<<vcnt[i][0]<<" "<<vcnt[i][1]<<" "<<vcnt[i][2]<<"\n";
//    }

    vector<int> perm;
    for (int i=0; i<n; i++)
        if (mp[cnt[i]].fi > 1)
            perm.pb(i);
    vector<int> perm0 = perm;
    vector<int> correct;
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
            correct.pb(i*j);
    sort(correct.begin(), correct.end());
//    cout<<perm.size()<<endl;
    while (true)
    {
        vector<int> all(n);
        int c0 = 0;
        for (int i=0; i<n; i++)
        {
//            cout<<i<<" -> "<<mp.count(vcnt[i])<<" ";
            if (mp[vcnt[i]].fi > 1)
            {
                all[i] = perm[c0++];
            }
            else
            {
                all[i] = mp[vcnt[i]].se;
            }
        }
//        cout<<endl;
//        for (int i=0; i<n; i++)
//            cout<<all[i]<<" ";
//        cout<<endl;
//        exit(0);

        vector<int> my;
        for (auto pa : v)
        {
            int x = pa.fi;
            int y = pa.se;
            if (x == -1)
                my.pb(all[y]);
            else
                my.pb(all[x]*n + all[y]);
        }
//        cout<<my.size()<<endl;
//        for (int i=0; i<n*n; i++)
//            cout<<my[i]<<" ";
//        cout<<endl;
//        exit(0);

        sort(my.begin(), my.end());
        if (my == correct)
            return all;

        if (!next_permutation(perm.begin(), perm.end()))
            break;
    }
    return vector<int>(n, 0);
}

int digit(char c)
{
    if (c <= 'Z')
        return 26+c-'A';
    else
        return c-'a';
}
char symbol(int c)
{
    if (c < 26)
        return 'a'+c;
    else
        return 'A'+c-26;
}

void solver()
{
    int n;
    cin>>n;
    vector<pair<int, int> > v;
    for (int i=0; i<n*n; i++)
    {
        string s;
//        int x = i%n * (i/n);
//        if (x >= n)
//            s += symbol(x/n);
//        s += symbol(x%n);
//        cout<<s<<endl;

        cin>>s;
        if (s.size() > 1)
            v.pb({digit(s[0]), digit(s[1])});
        else
            v.pb({-1, digit(s[0])});
    }

    vector<int> res = solve(n, v);
    vector<char> ans(n);
    for (int i=0; i<n; i++)
        ans[res[i]] = symbol(i);
    for (int i=0; i<n; i++)
        cout<<ans[i];
    cout<<"\n";
}


main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
//    for (int i=2; i<=52; i++)
//        boris(i);

    int t;
    cin>>t;
    for (int i=0; i<t; i++)
    {
        solver();
    }
}