#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;

int a[N][N];
int id[N][N];
int vis[N][N];

struct edge {
	int to;
	edge *nex;
}*head[N];

int f[N][N],g[N][N];
int find(int x,int f[]) {
	if(f[x]==x) return x;
	return f[x]=find(f[x],f);
}
void uni(int x,int y,int f[]) {
	f[find(x,f)]=find(y,f);
}
bool check(int u,int v,int f[]) {
	return find(u,f)==find(v,f);
}
int e=0;
bool add(int u,int v) {
	if(vis[u][v]) return 0;
	vis[u][v]=1,e++;
	if(u<v) cout<<u<<" "<<v<<endl;
	edge *cur=new edge;
	cur->to=v;
	cur->nex=head[u];
	head[u]=cur;
	return 1;
}
bool con(int u,int v) {
	return add(u,v)&add(v,u);
}
int dis[N];
void get() {
	e=0;
	int n,i,j;
	cin>>n;
	for(i=1;i<=n;i++) for(head[i]=0,dis[i]=0,j=1;j<=n;j++) vis[i][j]=0;
	for(i=1;i<=n;i++) for(j=1;j<=n;j++) cin>>a[i][j],id[i][a[i][j]]=j;
	for(i=1;i<=n;i++) for(j=1;j<=n+3;j++) f[i][j]=g[i][j]=j;
	for(i=1;i<=n;i++) con(a[i][1],a[i][2]);

	for(i=1;i<=n;i++) {
		for(j=1;j<=n;j++) if(!dis[j]) break;
		if(j==n+1) j=1;
		int u=find(n,g[j]);
		u=a[j][u];
		
		dis[u]=1;
		for(j=1;j<=n;j++) {
			//cout<<"del "<<j<<","<<id[j][u]<<endl;
			uni(id[j][u],id[j][u]+1,f[j]);
			uni(id[j][u],id[j][u]-1,g[j]);
		}
		for(j=1;j<=n;j++) {
			if(dis[j]) continue;
 			int x=find(1,f[j]);
			int y=find(x+1,f[j]);
			if(e==2*n-2) return ;
			con(a[j][x],a[j][y]);
		}
	}
	if(e!=2*n-2) cout<<"lost"<<endl;
	return ;
}
int main() {
	ios::sync_with_stdio(0),cin.tie(0);
	freopen("2.in","r",stdin);
	int T; cin>>T;
	while(T--) get();
	return 0;
}