#include<bits/stdc++.h>
using namespace std;
int T,n,H;
struct node{
    int x,y,h;
    bool operator < (const node &a)const{
        return h<a.h;
    }
}ans[4900];
priority_queue<node> h;
bool check(node a,node b){
    if((a.x==b.x||a.y==b.y)&&(abs(a.x-b.x)<=1)&&(abs(a.y-b.y)<=1)) return 1;
    return 0;
}
int main(){
    cin>>T;
    while(T--){
        cin>>n;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                cin>>H;
                h.push({j,i,H});
            }
        }
        int j=0;
        queue<node> c;
        while(!h.empty()){
            ans[++j]=h.top();
            h.pop();
            while(!c.empty()){
                h.push(c.front());
                c.pop();
            }
            while(!check(ans[j],h.top())){
                c.push(h.top());
                h.pop();
            }
        }
        for(int i=1;i<n*n;i++){
            cout<<ans[i].h<<" ";
        }
        cout<<ans[n*n].h<<endl;
    }
    return 0;
}