#include <iostream>

using namespace std;
#define Int long long int

#define DEBUG(x)
#define INFO(x)

#define ERROR_MAX (2 * 1000000000)

#include <list>
#include <vector>
#include <algorithm>

struct Point {
    Point *right = nullptr;
    Point *upper = nullptr;
    Int x;
    Int y;
    int cnt = 0;
    Int a = 0;
};

Point *read_points(int N) {
    auto *points = new Point[N];

    INFO(cout << "Podaj (x,y)" << endl;)
    Int x, y;
    for (auto n = 0; n < N; ++n) {
        cin >> x >> y;
        points[n].x = x;
        points[n].y = y;
    }

    DEBUG(for (auto i = 0; i < N; ++i) {
        cout << points[i].x << " " << points[i].y << endl;
    })

    return points;
}

Point **create_graph(Point **points, int N) {
    points[0]->cnt = 1;
    for (auto i = 1; i < N; ++i) {
        if (points[i]->y == points[i - 1]->y && points[i - 1]->x < points[i]->x) {
            points[i - 1]->right = points[i];
            points[i]->cnt += 1;
        }
        for (auto j = i; j < N; ++j) {
            if (points[i - 1]->x == points[j]->x && points[i - 1]->upper == nullptr) {
                points[i - 1]->upper = points[j];
                points[j]->cnt += 1;
                break;
            }
        }
    }

    for (auto i = 0; i < N; ++i) {
        if (points[i]->cnt == 0) {
            DEBUG(cout << "Terminated due to: ref cnt" << endl;)
            return nullptr;
        }
    }

    return points;
}

void print_graph(Point *base, int deep = 0) {
    if (base == nullptr)
        return;

    cout << " -> (" << base->x << ", " << base->y << ")";
    print_graph(base->right, deep + 1);
    cout << endl << std::string(deep * 12u, ' ') << "|";
    print_graph(base->upper, deep + 1);
}

bool solve_list(list<Point *> &border, Int &width, Int &height, Int &area) {
    if (border.empty()) {
        DEBUG(cout << "Terminated due to: empty border" << endl;)
        return true;
    }

    Point *node;
    while (!border.empty()) {
        node = border.front();
        border.pop_front();

        Int r = width - node->x - node->a;
        Int u = height - node->y - node->a;
        if (r > ERROR_MAX || u > ERROR_MAX)
            return false;

        if (node->a && (r == 0 || u == 0)) {
            continue;
        } else if (r > 0 && u > 0) {
            area -= node->a * node->a;
            node->a = min(r + node->a, u + node->a);
            area += node->a * node->a;
        } else if (r == 0) {
            node->a = 1;
            width += 1;
            area += 1;
        } else if (u == 0) {
            node->a = (width - node->x);
            height += node->a;
            area += node->a * node->a;
        }
        border.push_back(node);
    }

    return true;
}

void check_overlapping(Point **points, int id, Int &r) {
    for (auto i = 0; i < id; ++i) {
        if ((points[i]->y + points[i]->a > points[id]->y)
            && (points[i]->x > points[id]->x)
            && (points[id]->x + r > points[i]->x)) {
            r = points[i]->x - points[id]->x;
            return;
        }
    }
}

bool solve_graph(Point **points, int N) {
    if (points == nullptr) {
        DEBUG(cout << "Terminated due to: nullptr" << endl;)
        return false;
    }

    Int width = 0;
    Int height = 0;
    Int area = 0;

    list<Point *> border;
    Point *node;
    for (auto i = 0; i < N; ++i) {
        node = points[i];

        if (node->right == nullptr) {
            if (node->upper != nullptr) {
                node->a = node->upper->y - node->y;
                height = max(height, node->upper->y);
                width = max(width, node->x + node->a);
                area += node->a * node->a;
                DEBUG(cout << "Added: (" << node->x << ", " << node->y << ") a = " << node->a << endl);
            } else {
//                width = max(width, node->x + 1);
                border.push_back(node);
                DEBUG(cout << "Border add: (" << node->x << ", " << node->y << ") a = " << node->a << endl);
            }
        } else if (node->upper == nullptr) {
            Int r = node->right->x - node->x;
            check_overlapping(points, i, r);

            node->a = r;
            width = max(width, node->right->x);
            height = max(height, node->y + node->a);
            area += node->a * node->a;
            DEBUG(cout << "Added: (" << node->x << ", " << node->y << ") a = " << node->a << endl);
        } else {
            Int r = node->right->x - node->x;
            Int u = node->upper->y - node->y;
            check_overlapping(points, i, r);

            node->a = min(r, u);
            height = max(height, node->upper->y);
            width = max(width, node->right->x);
            area += node->a * node->a;
            DEBUG(cout << "Added: (" << node->x << ", " << node->y << ") a = " << node->a << endl);
        }
    }

    auto isValid = solve_list(border, width, height, area);
    if (!isValid) {
        DEBUG(cout << "Terminated due to: solve_list" << endl;)
        return false;
    }

    DEBUG(cout << "Area = " << area << endl;)
    DEBUG(cout << "width = " << width << " height = " << height << endl;)
    if (area != width * height) {
        DEBUG(cout << "Area mismatch" << endl;)
        return false;
    }

    return true;
}

int main() {
    ios::sync_with_stdio(false);
    INFO(cout << "Podaj t: ";)
    int T;
    cin >> T;

    for (auto t = 0; t < T; ++t) {
        INFO(cout << "Podaj n: ";)
        int N;
        cin >> N;

        auto *points_in = read_points(N);
        if (N == 1) {
            cout << "TAK " << 1 << endl;
            continue;
        }

        auto points_lex = vector<Point *>(N);
        for (auto i = 0; i < N; ++i) {
            points_lex[i] = &points_in[i];
        }
        sort(points_lex.begin(), points_lex.end(), [](Point *lhs, Point *rhs) {
            if (lhs->y < rhs->y)
                return true;
            if (lhs->y > rhs->y)
                return false;
            return lhs->x < rhs->x;
        });
        DEBUG(cout << "LEX" << endl;)
        DEBUG(for (auto i = 0; i < N; ++i) {
            cout << points_lex[i]->x << " " << points_lex[i]->y << endl;
        })

        Point **points_lex_data = create_graph(points_lex.data(), N);
        DEBUG(print_graph(points_lex_data[0]);)
        DEBUG(cout << endl << endl;)

        auto isValid = solve_graph(points_lex_data, N);
        if (isValid) {
            DEBUG(cout << "isValid" << endl);


            cout << "TAK";
            for (auto i = 0; i < N; ++i) {
                cout << " " << points_in[i].a;
            }
            cout << endl;
        } else {
            cout << "NIE" << endl;
        }


        delete[] points_in;
    }

    return 0;
}