#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <bitset>		//UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>		//do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)
#define ALL(u) (u).begin(),(u).end()

#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double

typedef pair<int, int> PII;

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;

const int MR = 2010;
const int inf = 2e9 + 10;

typedef map<int, vector<int>> Mapa;

struct Point
{
	int x, y, id;

	Point(){}
	Point(int x, int y)
	{
		this->x = x;
		this->y = y;
	}
} t[MR];


// porzadek po ktorym chodzimy normalnie
bool cmpUpRight(const Point &p1, const Point &p2)
{
	if (p1.y != p2.y)
		return p1.y < p2.y;
	return p1.x < p2.x;
}

// porzadek dla special case'a ograniczenia z prawej
bool cmpUpLeft(const Point &p1, const Point &p2)
{
	if (p1.y != p2.y)
		return p1.y < p2.y;

	return p1.x > p2.x;
}

// special case - ograniczony z gory
bool cmpRightDown(const Point &p1, const Point &p2)
{
	if (p1.x != p2.x)
		return p1.x < p2.x;

	return p1.y > p2.y;
}

// porzadek do filtrowania od gory
bool cmpDownRight(const Point &p1, const Point &p2)
{
	if (p1.y != p2.y)
		return p1.y > p2.y;
	return p1.x < p2.x;
}

LL sqr(int x)
{
	return x*(LL)x;
}

int res[MR];

bool spr(int n)
{
	// wyznacz BB
	int mnx = inf, mny = inf, mxx = -1, mxy = -1;
	// policz sume pol kwadratow
	LL s = 0;
	REP(i, n)
	{
		// spr czy nie ma pustego kwadratu
		if (res[t[i].id] <= 0)
			return 0;

		mnx = min(mnx, t[i].x);
		mny = min(mny, t[i].y);

		mxx = max(mxx, t[i].x + res[t[i].id]);
		mxy = max(mxy, t[i].y + res[t[i].id]);

		s += sqr(res[t[i].id]);
	}

	return s == (mxx - mnx)*(LL)(mxy - mny);
}

int nearestSquareRight(const Point & p, const vector<int> &squares)
{
	// wyznacz kwadrat najblizej z prawej do danego punktu
	// zakladamy poki co, poprawnosc kwadratow i olewamy sytuacje, gdzie on zawiera dany punkt
	// to powinnismy na koncu wykryc
	int dist = inf;

	for (int s : squares)
	{
		int lx = t[s].x, ly = t[s].y;
		int ux = lx + res[t[s].id], uy = ly + res[t[s].id];

		// spr czy jest ponizej. powyzej lub na prawo od kwadratu
		if (p.y >= uy || p.y <= ly || p.x > lx)
			continue;

		dist = min(dist, lx - p.x);
	}

	return dist;
}

int nearestSquareUp(const Point & p, const vector<int> &squares)
{
	// wyznacz kwadrat najblizej z gory do danego punktu
	// zakladamy poki co, poprawnosc kwadratow i olewamy sytuacje, gdzie on zawiera dany punkt
	// to powinnismy na koncu wykryc
	int dist = inf;

	for (int s : squares)
	{
		int lx = t[s].x, ly = t[s].y;
		int ux = lx + res[t[s].id], uy = ly + res[t[s].id];

		// spr czy jest na lewo, na prawo lub wyzej od kwadratu
		if (p.x <= lx || p.x >= ux || p.y > ly)
			continue;

		dist = min(dist, ly - p.y);
	}

	return dist;
}

void traverseUpLeft(int n, int right, const Point &first, Mapa &Mx, Mapa &My)
{
	// special case, where we have right bound

	// punkty, ktore sa juz kwadratami
	vector<int> squares;

	sort(t, t + n, cmpUpLeft);

	REP(i, n)
	{
		Point p = t[i];
		if (res[p.id])
		{
			squares.push_back(i);
			continue;
		}
		// wyznacz odleglosc od prawej
		int dist = right - p.x;
		// poszukaj punktu na prawo od niego
		auto it = upper_bound(My[p.y].begin(), My[p.y].end(), p.x);
		if (it != My[p.y].end())
			dist = *it - p.x;
		int distToSq = nearestSquareRight(p, squares);
		dist = min(dist, distToSq);

		res[p.id] = dist;
		squares.push_back(i);
	}
}

void traverseRightDown(int n, int up, const Point &first, Mapa &Mx, Mapa &My)
{
	// special case, where we have upper bound

	// punkty, ktore sa juz kwadratami
	vector<int> squares;

	sort(t, t + n, cmpRightDown);

	REP(i, n)
	{
		Point p = t[i];
		if (res[p.id])
		{
			squares.push_back(i);
			continue;
		}
		// wyznacz odleglosc od gory
		int dist = up - p.y;
		// poszukaj punktu w gore od niego
		auto it = upper_bound(Mx[p.x].begin(), Mx[p.x].end(), p.y);
		if (it != Mx[p.x].end())
			dist = *it - p.y;
		int distToSq = nearestSquareUp(p, squares);
		dist = min(dist, distToSq);

		res[p.id] = dist;
		squares.push_back(i);
	}
}

void traverseUpRight(int n, const Point &first, Mapa &Mx, Mapa &My)
{
	// we traverse without upper or right bound

	// punkty, ktore sa juz kwadratami
	vector<int> squares;

	// ostatnie punkty
	vector<int> last;

	sort(t, t + n, cmpUpRight);

	REP(i, n)
	{
		Point p = t[i];

		if (res[p.id])
		{
			squares.push_back(i);
			continue;
		}

		// wyznacz odleglosc do najblizszego z gory
		auto itU = upper_bound(Mx[p.x].begin(), Mx[p.x].end(), p.y);
		int distUp = inf;
		if (itU != Mx[p.x].end())
			distUp = *itU - p.y;

		// wyznacz odleglosc do najblizszego z prawej
		auto itR = upper_bound(My[p.y].begin(), My[p.y].end(), p.x);
		int distRight = inf;
		if (itR != My[p.y].end())
			distRight = *itR - p.x;

		// wyznacz odl do prawego kwadratu
		distRight = min(distRight, nearestSquareRight(p, squares));

		if (distUp == inf || distRight == inf)
		{
			last.push_back(i);
			continue;
		}
		else
		{
			res[p.id] = min(distUp, distRight);
		}

		squares.push_back(i);
	}

	// zgodnie z algorytmem tak powinno byc
	assert(last.size() > 1);

	// odfiltruj z last, te ktore od gory sa ograniczone istniejacymi kwadratami lub innymi punktami
	// w tym celu idziemy po nich od gory i w prawo
	vector<Point> cp;
	REP(i, last.size())
	{
		cp.push_back(t[last[i]]);
		// zapamietaj ich id w wektorze last
		cp.back().id = i;
	}

	sort(cp.begin(), cp.end(), cmpDownRight);

	for (const auto& p : cp)
	{
		// wszystkie kwadraty w gore od niego powinny byc zbudowane
		int dist = nearestSquareUp(p, squares);
		// sprobuj znalezc punkt w gore od niego
		auto itU = upper_bound(Mx[p.x].begin(), Mx[p.x].end(), p.y);
		if (itU != Mx[p.x].end())
			dist = min(dist, *itU - p.y);

		// porownaj jeszcze z punktem i prostokatem na prawo
		dist = min(dist, nearestSquareRight(p, squares));
		
		auto itR = upper_bound(My[p.y].begin(), My[p.y].end(), p.x);
		if (itR != My[p.y].end())
			dist = min(dist, *itR - p.x);

		if (dist != inf)
		{
			res[t[last[p.id]].id] = dist;
			squares.push_back(last[p.id]);
		}
	}

	if (res[t[last[cp.back().id]].id])
	{
		// mamy latwiejszy przypadek, znamy right bound
		Point p = t[last[cp.back().id]];

		int right = p.x + res[p.id];

		traverseUpLeft(n, right, first, Mx, My);
		return;
	}

	// teraz przefiltruj last i posortuj je jeszcze raz do ostatniej fazy
	cp.clear();
	REP(i, last.size())
	{
		if (res[t[last[i]].id])
			continue;
		cp.push_back(t[last[i]]);
		// zapamietaj ich pozycje w t
		cp.back().id = last[i];
	}

	if (cp.empty())
		return;

	sort(cp.begin(), cp.end(), cmpUpLeft);

	// teraz moze zostac tylko 1
	if (cp.size() == 1)
	{
		// on musi siegnac do najwyzszego y
		assert(!My.empty());
		auto it = My.end(); it--;
		res[t[cp.back().id].id] = it->first;
		return;
	}

	// teraz pierwszy bedzie siegal do kazdej mozliwej wysokosci i bedziemy patrzec, czy sie udalo
	// wszystkie niezrobione punkty moga sie przecinac tylko z nowo powstalymi kwadratami
	Point start = cp.front();

	int limUp = start.y + nearestSquareUp(start, squares);

	for (const auto &pr : My)
	{
		if (pr.first > limUp)
			break;
		if (pr.first <= start.y)
			continue;

		vector<int> newSquares;
		res[t[start.id].id] = pr.first;
		newSquares.push_back(start.id);

		// wyznacz prawy limit
		int right = pr.first + start.x;

		// ustaw pozostalym boki
		for (const auto &p : cp)
		{
			if (res[t[p.id].id])
				continue;
			int dist = right - p.x;
			vector<int> squareToCheck; squareToCheck.push_back(newSquares.back());
			dist = min(dist, nearestSquareRight(p, squareToCheck));

			res[t[p.id].id] = dist;
			newSquares.push_back(p.id);
		}

		// spr czy wszystko sie zgadza
		if (spr(n))
			return;
	}
}

bool go(int n)
{
	if (n == 1)
	{
		res[0] = 1;
		return 1;
	}

	// wyznacz lewy dolny punkt i spr pare special caseow
	Point first(inf, inf);
	REP(i, n)
		if (t[i].y < first.y
			|| (t[i].y == first.y && t[i].x < first.x))
			first = t[i];

	// zobacz czy nie ma zadnych punktow na lewo od niego - jesli tak, to sie nie da
	REP(i, n)
		if (t[i].x < first.x)
			return 0;

	// podziel punkty po wspolrzednych
	Mapa Mx, My;

	REP(i, n)
	{
		Mx[t[i].x].push_back(t[i].y);
		My[t[i].y].push_back(t[i].x);
	}

	for (auto &p : Mx)
		sort(p.second.begin(), p.second.end());
	for (auto &p : My)
		sort(p.second.begin(), p.second.end());

	// czy pierwszy jest ograniczony z gory i z prawej
	auto itUp = upper_bound(Mx[first.x].begin(), Mx[first.x].end(), first.y),
		itRight = upper_bound(My[first.y].begin(), My[first.y].end(), first.x);

	bool limUp = (itUp != Mx[first.x].end()), limRight = (itRight != My[first.y].end());

	// jesli z zadnej nie ma limitu, to sie nie da
	if (!limUp && !limRight)
		return 0;

	if (!limRight)
	{
		res[first.id] = *itUp - first.y;
		traverseUpLeft(n, first.x + res[first.id], first, Mx, My);
	}
	else if (!limUp)
	{
		res[first.id] = *itRight - first.x;
		traverseRightDown(n, first.y + res[first.id], first, Mx, My);
	}
	else
	{
		res[first.id] = *itUp - first.y;
		if (*itRight - first.x != res[first.id])
			return 0;

		traverseUpRight(n, first, Mx, My);
	}
	

	return spr(n);
}

int main()
{
	int T;
	scanf("%d", &T);
	REP(c, T)
	{
		int n;
		scanf("%d", &n);
		REP(i, n)
		{
			scanf("%d%d", &t[i].x, &t[i].y);
			t[i].id = i;
		}

		if (!go(n))
			printf("NIE\n");
		else
		{
			printf("TAK ");
			REP(i, n)
				printf("%d ", res[i]);
			printf("\n");
		}

		memset(res, 0, sizeof(res));
	}
	return 0;
}