// #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];

bool sy = 0;
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
void dfs(int x, int y, int u, int cd)
{
    //if(u == 35) cout << x << y << '\n';
    f[u] = {x, y}; vis[x][y] = 1;
    if(u == n * n)
    {
        if(cd < 0 || sy) return; sy = 1;
        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};
        // }
        vis[xx][yy] = 1;
        dfs(xx, yy, u + 1, cd + (a[xx][yy] > a[x][y] ? -1 : 1));
        vis[xx][yy] = 0;
    }
    
    //if(d1.x != -1) dfs(d1.x, d1.y, u + 1); else dfs(d2.x, d2.y, u + 1);
}

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

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