#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

#define _debugVar(x) { cerr << "* "#x" = " << x << endl; }
#define _debugHere { fprintf(stderr, "* Passing [%s] in Line %d\n", __FUNCTION__, __LINE__); }

using namespace std;
using LL = long long;
using PII = pair<int, int>;

const int N = 4005, Bias = 2001;
constexpr int INF = 0x3f3f3f3f;

int f[N][N];
void initSG(int n)
{
	static bitset<N> S1[Bias], S2[Bias], S3[N];

	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			int k = i-j+Bias;
			if(i == 1 && j == 1) f[i][j] = 0;
			else {
				int x = -1, y = -1;
				if(i-2 >= 1 && j-1 >= 1) x = f[i-2][j-1];
				if(i-1 >= 1 && j-2 >= 1) y = f[i-1][j-2];

				bitset<N> tmp = S3[k] | S1[i] | S2[j];
				if(x > -1) tmp[x] = 1;
				if(y > -1) tmp[y] = 1;
				// for(int r = 0; true; r++) 
				// 	if(r != x && r != y && 
				// 	   !S3[k][r] && !S1[i][r] && !S2[j][r]) {
				// 		f[i][j] = r;
				// 		break;
				// 	}
				tmp.flip();
				f[i][j] = tmp._Find_first();
				// if(f[i][j] < min(f[i-1][j-1], min(f[i][j-1], f[i-1][j]))) _debugHere;
			}
			S3[k][f[i][j]] = true;
			S1[i][f[i][j]] = true;
			S2[j][f[i][j]] = true;

			// if(i % 101 == 0 && j % 101 == 0) {
				// fprintf(stderr, "SG(%d, %d) = %d\n", i, j, f[i][j]);
				// _debugVar(i); _debugVar(j); _debugVar(f[i][j]);
			// }
			// if(f[i][j] != min(i, j)-1) _debugHere;
		}
	}

	// for(int i = 1; i <= 20; i++) {
	// 	fprintf(stderr, "%02d: ", i);
	// 	for(int j = 1; j <= 20; j++) {
	// 		fprintf(stderr, "%3d ", f[i][j]);
	// 	}
	// 	cerr << endl;
	// }
}

int sg(int i, int j)
{
	return f[i][j];
	// return min(i, j)-1;
}

int n;
PII a[N];

int main()
{
	// freopen("1.in", "r", stdin);
	clock_t st_time = clock();

	initSG(2000);
	int totCases; cin >> totCases;
	for(int curCase = 1; curCase <= totCases; curCase++) {
		cin  >> n;
		int sum = 0;
		for(int i = 1; i <= n; i++) {
			cin >> a[i].first >> a[i].second;
			sum ^= sg(a[i].first, a[i].second);
		}
		// _debugVar(sum);
		if(sum == 0) {
			puts("-1 -1 -1");
			continue;
		}

		for(int i = 1; i <= n; i++) {
			PII ans = PII(INF, INF);
			auto [x, y] = a[i];
			for(int j = 1; j < min(x, y); j++) {
				if(sum^sg(x, y)^sg(x-j, y-j)) continue;
				ans = min(ans, PII(x-j, y-j));
			}
			if(x-2 >= 1 && y-1 >= 1 && !(sum^sg(x, y)^sg(x-2, y-1))) 
				ans = min(ans, PII(x-2, y-1));
			if(x-1 >= 1 && y-2 >= 1 && !(sum^sg(x, y)^sg(x-1, y-2)))
				ans = min(ans, PII(x-1, y-2));
			if(ans.first != INF) {
				printf("%d %d %d\n", i, ans.first, ans.second);
				break;
			}
		}
	}

	cerr << "time: " << (double)(clock()-st_time)/CLOCKS_PER_SEC << endl;
	return 0;
}