#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,a[N][N],p[N][N],ps[N],f[N],c;
int fa(int x){return x==f[x]?x:f[x]=fa(f[x]);}
set<pair<int,int>>s;
vector<int>st;
vector<pair<int,int>>ans;
void add(int x,int y)
{
	if(x>y) swap(x,y);
	if(s.find(make_pair(x,y))!=s.end()) return;
	s.insert(make_pair(x,y));
	c++;
	f[fa(x)]=fa(y);
	for(int i=1;i<=n;i++)
	{
		int px=p[i][x],py=p[i][y];
		if(abs(px-py)==1) continue;
		if(px>py) swap(px,py);
		add(a[i][px],a[i][px+1]);
	}
}
void cal(int x)
{
	while(ps[x]<=n&&fa(x)==fa(a[x][ps[x]]))
		ps[x]++;
}
void sol()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&a[i][j]);
	if(n==1) return;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			p[i][a[i][j]]=j;
	for(int i=1;i<=n;i++)
		f[i]=i,ps[i]=1;
	s.clear();
	c=0;
	for(int i=1;i<=n;i++)
		add(a[i][1],a[i][2]);
	while(c!=n-1)
	{
		int ls=1,t=0;
		while(1)
		{
			cal(ls);
			int nx=a[ls][ps[ls]];
			cal(nx);
			if(a[nx][ps[nx]]==ls)
			{
				add(ls,nx);
				break;
			}
			ls=nx;
			t++;
			if(t>n)
			{
				for(int i=1;i<=n;i++)
				{
					for(int j=1;j<=n;j++)
						printf("%d ",a[i][j]);
					puts("");
				}
				exit(0);
			}
		}
	}
	for(auto [i,j]:s)
		ans.emplace_back(i,j);
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
		sol();
	for(auto [i,j]:ans)
		printf("%d %d\n",i,j);
	return 0;
}