#include<bits/stdc++.h>
using namespace std;
const int M=1010;
int n;
pair <int,int> G[M][M];
//pair <int,int> NG[M][M];
int mp[M][M];
pair <int,int> ans[M];
int tot,tim;
int f[M];
int findf(int a){
	return f[a]==a?a:f[a]=findf(f[a]);
}
void addans(int a,int b){
	if(mp[a][b]!=tim){
		mp[a][b]=mp[b][a]=tim;
		ans[++tot]=make_pair(a,b);
	}
}
int had[M],idx[M];
int hadb[M][M],res[M];
int topp;
pair <int,int> hb[M];
void solve(int hcnt,int coln){
	if(hcnt==1||coln==1) return;
	int next_coln=coln;
	topp=0;
	for(int i=1,a,b;i<=hcnt;i++){
		if(coln==n){
			addans(G[i][1].first,G[i][2].first);
			a=findf(G[i][1].first);
			b=findf(G[i][2].first);
			if(a<b)swap(a,b);
			if(a^b) f[a]=b,--next_coln;
		}else{
			a=G[i][1].second;
			b=G[i][2].second;
			if(hadb[a][b]==coln) continue;
			hadb[a][b]=hadb[b][a]=coln;
			hb[++topp]=make_pair(a,b);
			int ii=idx[b];
			for(int j=2;j<=coln;j++){
				if(G[ii][j].second==a){
					addans(G[i][2].first,G[ii][j].first);
					break;
				}
			}
		}
	}
	for(int i=1,a,b;i<=topp;i++){
		a=findf(hb[i].first);
		b=findf(hb[i].second);
		if(a==b) continue;
		if(b>a)swap(a,b);
		f[a]=b;--next_coln;
	}
	int nowup=0;
	for(int i=1;i<=n;i++){
		if(findf(i)==i){
			res[++nowup]=i;
		}
	}
	for(int i=1;i<=n;i++)had[i]=0;
	for(int i=1;i<=nowup;i++){
		int h=idx[res[i]];
		int nowt=0;
		for(int j=1;j<=coln;j++){
			int a=findf(G[h][j].first);
			if(had[a]!=i){
				had[a]=i;
				G[i][++nowt].first=G[h][j].first;
				G[i][nowt].second=a;
			}
		}
	}
	for(int i=1;i<=n;i++){
		idx[res[i]]=i;
	}
	solve(nowup,next_coln);
}
int main(){
	int T;
	for(scanf("%d",&T);T;T--){
		scanf("%d",&n);
		tot=0;
		++tim;
		for(int i=1;i<=n;i++){
			f[i]=i;
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				scanf("%d",&G[i][j].first);
				G[i][j].second=G[i][j].first;
			}
		}
		for(int i=1;i<=n;i++)idx[i]=i;
		solve(n,n);
		if(tot!=n-1) return 0;
		for(int i=1;i<=tot;i++){
			printf("%d %d\n",ans[i].first,ans[i].second);
		}
	}
	return 0;
}
/*
1
7
1 2 7 3 5 4 6
2 7 1 3 4 6 5
3 5 4 6 1 2 7
4 6 3 1 2 7 5
5 3 1 2 7 4 6
6 4 3 5 1 2 7
7 2 1 3 5 4 6
*/