#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cassert>

typedef unsigned long long ull;
using namespace std;
const int MAX_N = 2000;

struct point
{
	int id;
	ull x, y;
	mutable ull edge = 0;
	point(int _id, ull _x, ull _y) : id(_id), x(_x), y(_y) {}
	inline ull distance_to(const point& p) const
	{
		return (x - p.x)*(x - p.x) + (y - p.y)*(y - p.y);
	}
};

struct line
{
	point start, end;
};

struct horizontal_compare 
{
	bool operator() (const line& lhs, const line& rhs) const
	{
		return lhs.start.y == rhs.start.y ? lhs.start.x < rhs.start.x : lhs.start.y < rhs.start.y;
	}
};

struct vertical_compare
{
	bool operator() (const line& lhs, const line& rhs) const
	{
		return lhs.start.x == rhs.start.x ? lhs.start.y < rhs.start.y : lhs.start.x < rhs.start.x;
	}
};

std::vector<point> points;
std::vector<point> skipped;
ull result_place[MAX_N];
int n;

bool solve()
{
	if (points.size() == 1)
	{
		cout << "TAK 1" << endl;
		return true;
	}

	// start with most bottom-left point
	std::set<line, horizontal_compare> horizontal;
	std::set<line, vertical_compare> vertical;
	ull total_area = 0, top = 0, right = 0;
	ull bottom = points.front().y, left = points.front().x;

	size_t k = 0;
	for (auto& p : points)
	{
		ull closest_dist = -1;
		point closest_point(-1, -1, -1);
		for(size_t l = k + 1; l < points.size(); ++l)
		{
			const auto& w = points[l];
			if (w.x >= p.x && w.y >= p.y)
			{
				ull d = p.distance_to(w);
				if (closest_dist > d)
				{
					closest_point = w;
					closest_dist = d;

				}
			}
		}

		auto it = horizontal.upper_bound(line{point(-1,p.x, p.y),point(-1,p.x,p.y)});
		for(; it != horizontal.end(); ++it)
		{
			if (it->start.y > p.y && it->start.x < p.x && it->end.x > p.x)
			{
				ull d = it->start.y - p.y;
				d *= d;
				if (d < closest_dist)
				{
					closest_dist = d;
					closest_point = point(0, p.x, it->start.y);
					break;
				}
			}
		}

		it = vertical.upper_bound(line{ point(-1,p.x, p.y),point(-1,p.x,p.y) });
		for (; it != vertical.end(); ++it)
		{
			if (it->start.x > p.x && it->start.y < p.y && it->end.y > p.y)
			{
				ull d = it->start.x - p.x;
				d *= d;
				if (d < closest_dist)
				{
					closest_dist = d;
					closest_point = point(0, it->start.x, p.y);
					break;
				}
			}
		}

		if (closest_point.id != -1)
		{
			p.edge = std::max(closest_point.x - p.x, closest_point.y - p.y);
			total_area += p.edge*p.edge;
			right = std::max(right, p.x + p.edge);
			top = std::max(top, p.y + p.edge);
			result_place[p.id] = p.edge;

			auto l = line{ point{ 0, p.x, p.y }, point{ 0, p.x, p.y + p.edge } };
			auto it = vertical.find(l);
			if(it != vertical.end())
			{
				if (l.end.y - l.start.y > it->end.y - it->start.y)
				{
					vertical.erase(it);
					vertical.insert(l);
				}
			}
			else
			{
				vertical.insert(l);
			}

			l = line{ point{ 0, p.x + p.edge, p.y }, point{ 0, p.x + p.edge, p.y + p.edge } };
			it = vertical.find(l);
			if (it != vertical.end())
			{
				if (l.end.y - l.start.y > it->end.y - it->start.y)
				{
					vertical.erase(it);
					vertical.insert(l);
				}
			}
			else
			{
				vertical.insert(l);
			}

			l = line{ point{ 0, p.x, p.y }, point{ 0, p.x + p.edge, p.y } };
			it = horizontal.find(l);
			if (it != horizontal.end())
			{
				if (l.end.x - l.start.x > it->end.x - it->start.x)
				{
					horizontal.erase(it);
					horizontal.insert(l);
				}
			}
			else
			{
				horizontal.insert(l);
			}

			l = line{ point{ 0, p.x, p.y + p.edge }, point{ 0, p.x + p.edge, p.y + p.edge } };
			it = horizontal.find(l);
			if (it != horizontal.end())
			{
				if (l.end.x - l.start.x > it->end.x - it->start.x)
				{
					horizontal.erase(it);
					horizontal.insert(l);
				}
			}
			else
			{
				horizontal.insert(l);
			}
		}
		else
		{
			skipped.push_back(p);
		}

		++k;
	}

	if (skipped.size() == points.size())
	{
		return false;
	}

	ull old_right = right;
	ull old_top = top;

	for (auto& p : skipped)
	{
		// fill top-right
		if (p.y < top && p.x < right)
		{
			p.edge = std::min(old_top - p.y, old_right - p.x);
		}

		// fill bottom-right
		else if (p.y == bottom)
		{
			p.edge = right - p.x;
			// fill, not fit
			if (p.edge == 0)
			{
				p.edge = top - bottom;
			}
			right += p.edge;
		}

		// fill top-left
		else if (p.x == left)
		{
			p.edge = top - p.y;
			// fill, not fit
			if (p.edge == 0)
			{
				p.edge = right - left;
			}
			top += p.edge;
		}

		if (p.edge == 0)
		{
			return false;
		}

		total_area += p.edge*p.edge;
		result_place[p.id] = p.edge;
	}

	if (total_area != (top - bottom) * (right - left))
	{
		return false;
	}

	std::cout << "TAK";
	for (int i = 0; i < n; ++i)
	{
		std::cout << ' ' << result_place[i];
	}
	std::cout << std::endl;
	return true;
}

void clear_state()
{
	skipped.clear();
	for(auto& x : points)
	{
		x.edge = 0;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	int t;
	ull p1, p2;
	points.reserve(MAX_N);
	skipped.reserve(MAX_N);

	cin >> t;
	while (t--)
	{
		points.clear();
		skipped.clear();
		cin >> n;
		for (int i = 0; i < n; ++i)
		{
			cin >> p1 >> p2;
			points.push_back(point(i, p1, p2));
		}

		std::sort(points.begin(), points.end(), [](const point& a, const point& b) { return a.x*a.x + a.y*a.y < b.x*b.x + b.y*b.y; });
		bool ok = solve();
		if (ok) continue;

		std::cout << "NIE" << std::endl;
	}
	return 0;
}