#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];
int topp;
pair <int,int> hb[M];
void solve(int coln){
	if(coln==1) return;
	int next_coln=coln;
	topp=0;
	for(int i=1,a,b;i<=n;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) 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=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;
		f[a]=b;--next_coln;
	}
	for(int i=1;i<=coln;i++)had[i]=0;
	for(int i=1;i<=n;i++){
		int nowt=0;
		for(int j=1,a;j<=coln;j++){
			a=findf(G[i][j].first);
			if(had[a]!=i){
				had[a]=i;
				G[i][++nowt].first=G[i][j].first;
				G[i][nowt].second=a;
			}
		}
	}
	solve(next_coln);
}
vector <int> A;
int dfs(int a){
	if(a<=-10) return 0;
	return A[a]+dfs(a-1);
}
int main(){
	int T;
	A.resize(2);
	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;
			}
		}
		solve(n);
		if(tot!=n-1) dfs(1);
		for(int i=1;i<=tot;i++){
			printf("%d %d\n",ans[i].first,ans[i].second);
		}
	}
	return 0;
}