#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

void solve() {
    int n;
    cin >> n;
    vector a(n + 1, vector(n + 1, 0));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1;  j <= n; ++j) {
            cin >> a[i][j];
        }
    }

    int dr = 0;
    vector<int> b;
    vector vis(n + 1, vector(n + 1, 0));
    auto dfs = [&](auto&& self, int x, int y) -> void {
        b.push_back(a[x][y]);
        vis[x][y] = 1;
//        cerr << x << " " << y << "\n";
        if (ssize(b) == n * n) return;
        int nxtx = x, nxty = y;
        while (true) {
            nxtx = x + dx[dr];
            nxty = y + dy[dr];
            if (1 <= nxtx && nxtx <= n && 1 <= nxty && nxty <= n && !vis[nxtx][nxty]) break;
            dr = (dr + 1) % 4;
        }
        self(self, nxtx, nxty);
    };

    dfs(dfs, 1, 1);

    int cnt0 = 0, cnt1 = 0;
    for (int i = 1; i < ssize(b); ++i) {
        if (b[i - 1] < b[i]) cnt0++;
        else cnt1++;
    }
    if (cnt0 <= cnt1) {
        for (int i = 0; i < ssize(b); ++i) {
            cout << b[i] << " \n"[i == ssize(b) - 1];
        }
    } else {
        reverse(b.begin(), b.end());
        for (int i = 0; i < ssize(b); ++i) {
            cout << b[i] << " \n"[i == ssize(b) - 1];
        }
    }
}
int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);

    int _;
    cin >> _;
    while (_--) solve();

    return 0;
}