#include<bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &x)
{
	x=0;short f=1;char c=getchar();
	for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	x*=f;return;
}
const int N=4005;
using node=array<int,3>;
bitset<N>h[N],l[N],d[N],tmp;
int sg[N][N];
int x[N],y[N];
void init()
{
	for(int i=1;i<=4000;i++)
	{
		h[i].set();
		l[i].set();
		d[i].set();
	}
	for(int i=1;i<=2000;i++)
	{
		for(int j=1;j<=2000;j++)
		{
			tmp.set();
			tmp=tmp&h[i];
			tmp=tmp&l[j];
			tmp=tmp&d[i-j+2000];
			if(i>=3&&j>=2) tmp[sg[i-2][j-1]]=0;
			if(i>=2&&j>=3) tmp[sg[i-1][j-2]]=0;
			sg[i][j]=tmp._Find_first();
			h[i][sg[i][j]]=0;
			l[j][sg[i][j]]=0;
			d[i-j+2000][sg[i][j]]=0;
		}
	}
}
int main()
{
	init();
	int T;read(T);
	while(T--)
	{
		int k;read(k);
		int res=0;
		for(int i=1;i<=k;i++)
		{
			read(x[i]),read(y[i]);
			res^=sg[x[i]][y[i]];
		}
		if(res==0)
		{
			puts("-1 -1 -1");
			continue;
		}
		node ans={1e9,1e9,0};
		for(int t=1;t<=k;++t)
		{
			for(int i=1;i<=x[t]-1;++i)
				if(sg[i][y[t]]==(res^sg[x[t]][y[t]]))
					ans=min(ans,{i,y[t],t});
			for(int i=1;i<=y[t]-1;++i)
				if(sg[x[t]][i]==(res^sg[x[t]][y[t]]))
					ans=min(ans,{x[t],i,t});
			for(int i=1;i<=min(x[t],y[t])-1;++i)
				if(sg[x[t]-i][y[t]-i]==(res^sg[x[t]][y[t]]))
					ans=min(ans,{x[t]-i,y[t]-i,t});
			if(x[t]>=3&&y[t]>=2)
				if(sg[x[t]-2][y[t]-1]==(res^sg[x[t]][y[t]]))
					ans=min(ans,{x[t]-2,y[t]-1,t});
			if(x[t]>=2&&y[t]>=3)
				if(sg[x[t]-1][y[t]-2]==(res^sg[x[t]][y[t]]))
					ans=min(ans,{x[t]-1,y[t]-2,t});
		}
		printf("%d %d %d\n",ans[2],ans[0],ans[1]);
	}
	return 0;
}

answer.code: In function ‘int main()’:
answer.code:58:36: error: narrowing conversion of ‘1.0e+9’ from ‘double’ to ‘int’ [-Wnarrowing]
   58 |                 node ans={1e9,1e9,0};
      |                                    ^
answer.code:58:36: error: narrowing conversion of ‘1.0e+9’ from ‘double’ to ‘int’ [-Wnarrowing]