#include "bits/stdc++.h"
using namespace std;

struct xyi {
    int x;
    int y;
    int i;
};

struct Points {
    vector<xyi> xy;
    vector<xyi> yx;
    vector<xyi> dx;
};


ostream& operator<<(ostream& out, const xyi& p) {
    out << "(" << p.x << "," << p.y << ")@" << p.i;
    return out;
}

struct XYCmp {
    bool operator()(const xyi& p, const xyi& q) {
        return make_pair(p.x, -p.y) < make_pair(q.x, -q.y);
    }
};


struct YXCmp {
    bool operator()(const xyi& p, const xyi& q) {
        return make_pair(p.y, -p.x) < make_pair(q.y, -q.x);
    }
};

struct DXCmp {
    bool operator()(const xyi& p, const xyi& q) {
        return make_pair(p.x - p.y, p.x) < make_pair(q.x - q.y, q.x);
    }
};

template<int xyi::*X, int xyi::*Y>
xyi DecY(xyi p) {
    (p.*Y) = p.*Y - 1;;
    return p;
}
template<class T>
struct List {
    List():values(1), nxt(1, 0), prv(1,0){}
    vector<T> values;
    vector<int> nxt;
    vector<int> prv;
    void Insert(const T& what, int where=0) {
        int i = (int) values.size();
        values.push_back(what);
        nxt.push_back(where);
        prv.push_back(prv[where]);
        nxt[prv[where]] = i;
        prv[where] = i;
    }

    void Erase(int where) {
        nxt[prv[where]] = nxt[where];
        prv[nxt[where]] = prv[where];
        nxt[where] = prv[where] = -1;
    }

    int Size() {
        int sz = 0;
        for (int i = nxt[0]; i != 0; i = nxt[i]) {
            ++sz;
        }
        return sz;
    }
};

template<int xyi::*X = &xyi::x, int xyi::*Y = &xyi::y>
xyi MakeXyi(int x, int y) {
    xyi p;
    p.*X = x;
    p.*Y = y;
    p.i = -1;
    return p;
}

template<int xyi::*X, int xyi::*Y, vector<xyi> Points::*XY, class Cmp>
int FindA(const Points& ps, xyi p) {
    auto& xy = ps.*XY;
    auto jt = lower_bound(xy.begin(), xy.end(), DecY<X,Y>(p), Cmp());
    int x = -1;
    while (jt != xy.end()) {
        x = *jt.*X + (p.*Y - *jt.*Y);
        jt = lower_bound(xy.begin(), xy.end(),
                MakeXyi<X, Y>(x, (int)1e9), Cmp());
        if (jt != xy.end() && *jt.*X > x) {
            return 0;
        }
    }
    if (x == -1) {
        return 0;
    } else {
        return x - p.*X;
    }
}

bool HeuristicCheck(const Points& ps, int x0, int y0) {
    if (ps.xy.back().x >= x0 || ps.yx.back().y >= y0) {
        return false;
    }
    auto it = ps.dx.begin();

    int y = y0;
    while(true) {
        while (next(it) != ps.dx.end() && next(it)->x - next(it)->y <= x0 - y) ++it;
        if (it->x >= x0) return false;
        if (it->x - it->y == x0 - y) {
            y = it->y;
        } else {
            return ps.yx[0].y == y;
        }
    }

    return true;
}

bool ConsiderTopRight(const Points& ps, xyi p, vector<int>& as) {
    if (ps.xy.size() == 1) {
        as = vector<int>(1, 1);
        return true;
    }
    set<int> pas {
        FindA<&xyi::x, &xyi::y, &Points::xy, XYCmp>(ps, p),
        FindA<&xyi::y, &xyi::x, &Points::yx, YXCmp>(ps, p)};
    for (int a : pas) {
        if (a == -1) {
            as = vector<int>(1, 1);
            return true;
        }
        if (a == -2) {
            return false;
        }
    }

    for (int a0 : pas) {
        if (a0 <= 0) {continue;}
        int x0 = p.x + a0;
        int y0 = p.y + a0;
        if(!HeuristicCheck(ps, x0, y0)) {
            continue;
        }
        as = vector<int>(ps.xy.size(), -1);
        List<xyi> border;
        border.Insert(MakeXyi(x0,y0));
        unordered_set<int> active; active.insert(1);
        while (!active.empty()) {
            auto it = *active.begin(); active.erase(active.begin());
            int x = border.values[it].x;
            int y = border.values[it].y;
            auto jt = lower_bound(ps.dx.begin(), ps.dx.end(), MakeXyi(x, y), DXCmp());
            if (jt == ps.dx.begin() || prev(jt)->x - prev(jt)->y < x - y) {continue;}
            int a = x - prev(jt)->x;
            int ii = prev(jt)->i;
            if (a <= 0) {return false;}
            if ((it != border.nxt[0] && border.values[border.prv[it]].x > x - a) ||
                (border.nxt[it] != 0 && border.values[border.nxt[it]].y > y - a)) {
                continue;
            };
            as[ii] = a;
            if (it == border.nxt[0] || (it != border.nxt[0] && border.values[border.prv[it]].x < x - a)) {
                border.Insert(MakeXyi(x-a, y), it);
            }
            active.insert(border.prv[it]);
            if (border.nxt[it] == 0 || (border.nxt[it] != 0 && border.values[border.nxt[it]].y < y - a)) {
                border.Insert(MakeXyi(x, y-a), border.nxt[it]);
            }
            active.insert(border.nxt[it]);
            border.Erase(it);
        }
        if(border.Size() == 2 && find(as.begin(), as.end(), -1) == as.end()) {
            return true;
        }
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        Points ps;
        ps.xy.resize(n);
        for (int i = 0; i < n; ++i) {
            cin >> ps.xy[i].x >> ps.xy[i].y;
            ps.xy[i].i = i;
        }
        ps.yx = ps.dx = ps.xy;
        sort(ps.xy.begin(), ps.xy.end(), XYCmp{});
        sort(ps.yx.begin(), ps.yx.end(), YXCmp{});
        sort(ps.dx.begin(), ps.dx.end(), DXCmp{});

        vector<xyi> maxi;
        for (auto p : ps.xy) {
            while (!maxi.empty() && maxi.back().y <= p.y) {
                maxi.pop_back();
            }
            if (maxi.empty() || maxi.back().x < p.x) {
                maxi.push_back(p);
            }
        }
        bool found = false;
        vector<int> as;
        for(auto p : maxi) {
            if (ConsiderTopRight(ps, p, as)) {
                found = true;
                break;
            }
        }
        if (found) {
            cout << "TAK";
            for (int a : as) {
                cout << ' ' << a;
            }
                cout << '\n';
        } else {
            cout << "NIE\n";
        }
    }


}