#include <bits/stdc++.h>
#define int long long
#define X first
#define Y second

#define NIE do { \
        cout << "NIE\n"; \
        goto kuniec; \
    } while (0);

#define TAK do { \
        print_sol(swapped); \
        goto kuniec; \
    } while (0);
using namespace std;

typedef pair<int, int> PII;
typedef unsigned long long ULL;

const int INF = 2e9;
const ULL TRYLION = 1000000ULL * 1000000ULL * 1000000ULL;

struct Point {
    int x, y, s;

    Point(int x = 0, int y = 0, int s = -1): x(x), y(y), s(s) {}
};

bool cmp(const Point& a, const Point& b) {
    if (a.y != b.y) return a.y < b.y;
    return a.x < b.x;
}
struct setcmp {
    bool operator()(PII a, PII b) {
        if (a.second != b.second) return a.second < b.second;
        return a.first < b.first;
    }
};

int t, n;
vector<Point> points;
vector<int> leftovers;

map<pair<int,int>, int> id;


void print_sol(bool swapped) {
    vector<int> res(n);

    for (int i = 0; i < n; i++) {
        pair<int, int> p;
        p = swapped ? make_pair(points[i].y, points[i].x) : make_pair(points[i].x, points[i].y);
        res[id[p]] = points[i].s;
    }

    cout << "TAK ";
    for (auto x: res)
        cout << x << " ";
    cout << "\n";
}

bool check() {

    ULL upper = 0;
    ULL lower = TRYLION;
    ULL left = TRYLION;
    ULL right = 0;

    for (auto p: points) {
        if (p.s <= 0 || p.s > INF) return false;
        upper = max(upper, (ULL)p.y + p.s);
        lower = min(lower, (ULL)p.y);
        left = min(left, (ULL)p.x);
        right = max(right, (ULL)p.x + p.s);
    }

    ULL area = (upper - lower) * (right - left);

    ULL sum = 0;

    for (auto p: points) {
        sum += (ULL)p.s * p.s;
        if (sum > area) {
            return false;
        }
    }

    if (sum != area) return false;

    /*
    for (int i = 0; i < n; i++) {

        auto p = points[i];
        for (int j = i + 1; j < n; j++) {
            auto q = points[j];

            bool ok = false;
            ok |= p.x >= q.x + q.s;
            ok |= q.x >= p.x + p.s;
            ok |= p.y >= q.y + q.s;
            ok |= q.y >= p.y + p.s;

            if (!ok) {
                return false;
            }
        }
    }*/
    set<PII, setcmp> S;

    set<pair<int, PII>> evs;


    //for (auto p

    return true;
}


bool ins(set<PII, setcmp> &S, PII d) {
    auto it = S.insert(d).first;
    
    if (it != S.begin()) {
        auto pre = prev(it);
        if (pre->second > it->first) return false;
    }

    if (next(it) != S.end()) {
        auto ne = next(it);
        if ((*it).second > (*ne).first) return false;
    }

    return true;
}

int findlim(set<PII, setcmp> &S, int x) {
    auto lim = make_pair(INF + INF, x);

    auto it = S.lower_bound(lim);

    if (it == S.end()) return -1;

    return it->first;
}

int32_t main() {

    ios_base::sync_with_stdio(0);

    cin >> t;

    while (t--) {
        cin >> n;

        bool swapped = false;

        points.clear();
        points.resize(n);

        leftovers.clear();
        id.clear();



        for (int i = 0; i < n; i++) {
            cin >> points[i].x >> points[i].y;
            id[make_pair(points[i].x, points[i].y)] = i;
        }

        if (n == 1) {
            cout << "TAK 1\n";
            goto kuniec;
        }

        for (int z = 0; z < 2; z++) {
            sort(begin(points), end(points), cmp);

            int min_x = points[0].x;
            int min_y = points[0].y;
            int ln;

            int last_low = -1;

            for (auto p: points) {
                if (p.x < min_x) {
                    NIE;
                }
            }

            for (int i = 0; i < n; i++) {
                if (points[i].y == min_y) {
                    last_low = i;
                }
            }


            for (int i = last_low + 1; i < n; i++) {
                //cerr << "i = " << i << "\n";
                for (int j = 0; j < n; j++) points[j].s = -1;

                points[last_low].s = points[i].y - points[last_low].y;
                int right_border = points[last_low].s + points[last_low].x;



                bool ok = true;

                set<PII, setcmp> S;

                set<pair<int, PII>> evs;

                {
                    auto p = points[last_low];
                    auto inter = make_pair(p.x, p.x + p.s);
                    auto lol = make_pair(p.y + p.s, inter);
                    S.insert(inter);
                    evs.insert(lol);
                }

                for (int j = 0; j < n; j++) {
                    if (j == last_low) continue;

                    auto p = points[j];


                    //cerr << p.x << " "<< p.y << "\n";
                    while (!evs.empty() && (*evs.begin()).first <= p.y) {
                        S.erase((*evs.begin()).second);
                        evs.erase(evs.begin());
                        //cerr << "erase \n";
                    }


                    int s = right_border - p.x;
                    //cerr << "s1 " << s << "\n";

                    if (j + 1 < n && points[j+1].y == points[j].y) {
                        s = min(s, points[j+1].x - points[j].x);
                    }

                    //cerr << "s2 " << s << "\n";
                    auto lim = findlim(S, p.x);

                    //cerr << "lim " << lim << "\n";

                    if (lim != -1) 
                        s = min(s, lim - p.x);
                    /*for (int j = 0; j < n; j++) {
                        auto q = points[j];
                        if (q.s != -1 && q.x + q.s > p.x && q.y + q.s > p.y) {
                            s = min(s, q.x - p.x);
                        }
                    }*/

                    //cerr << "s = " << s << "\n";
                    if (s <= 0) {
                        ok = false;
                        break;
                    }
                    points[j].s = s;

                    if (!ins(S, make_pair(p.x, p.x+s))) {
                        ok = false;
                        break;
                        //cerr << "EEE " << S.size() << "\n";
                    }
                    auto lol = make_pair(p.y + s, make_pair(p.x, p.x + s));
                    evs.insert(lol);

                    //cerr << "insert " << p.y+s << " " << p.x << " " << p.x + s << "\n";
                }

                if (ok && check()) {
                    TAK;
                }

            }

            if (z == 0) {
                swapped = true;
                for (auto &p: points) {
                    int t = p.x;
                    p.x = p.y;
                    p.y = t;
                }

            }
        }
        NIE;

kuniec:
        1;
    }

    return 0;
}