// #pragma GCC optimize(2)

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define lep(i, a, b) for(int i = (a); i >= (b); i--)
#define x first 
#define y second

using namespace std;

using ll=long long;
using pii=pair<ll,ll>;
using ld=long double;
typedef pair<ll, ll> PLL;
constexpr ll N=1e6+10,mod=1e8-3,INF=1e18;
constexpr ld inf=1e18,eps=1e-5;
ll n, m, a[100][100], vis[100][100]; 
pair<int, int> f[N];

int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
void dfs(int x, int y, int u)
{
    f[u] = {x, y}; vis[x][y] = 1;
    if(u == n * n)
    {
        rep(i, 1, u) cout << a[f[i].x][f[i].y] << " \n"[i == u];
        return;
    }
    
    PLL d1 = {-1, -1}; PLL d2 = {-1, -1};
    rep(k, 0, 3)
    {
        int xx = x + dx[k], yy = y + dy[k];
        if(xx < 1 || yy < 1 || xx > n || yy > n || vis[xx][yy]) continue;
        if(a[xx][yy] < a[x][y])
        {
            if(d1.x == -1 || a[d1.x][d1.y] < a[xx][yy]) d1 = {xx, yy};
        }
        else
        {
            if(d2.x == -1 || a[d2.x][d2.y] < a[xx][yy]) d2 = {xx, yy};
        }
    }

    if(d1.x != -1) dfs(d1.x, d1.y, u + 1); else dfs(d2.x, d2.y, u + 1);
}

void solve(){
    cin >> n;
    rep(i, 1, n) rep(j, 1, n) cin >> (a[i][j]), vis[i][j] = 0;
    dfs(1, 1, 1); 
}

int main(){
    IOS;
    int t=1;
    cin>>t;
    while(t--) solve();
    return 0;
}