#include <bits/stdc++.h>

namespace Solution {
  std::optional<std::vector<int>>
  Solve(const std::vector<std::pair<int, int>> &points, int lo, int hi) {
    int N = (int) points.size();

    // std::cerr << lo << ' ' << hi << '\n';

    std::vector<int> ord(N);
    std::iota(ord.begin(), ord.end(), 0);
    std::ranges::sort(ord, [&](int a, int b) { return points[a] < points[b]; });

    std::vector<int> ans(N, -1);
    std::map<int, std::vector<int>> mp;

    auto Set = [&](int id, int l) {
      ans[id] = l;
      auto [x, y] = points[id];
      mp[x + l].emplace_back(y);
      mp[x + l].emplace_back(y + l);
      // std::cerr << "SET " << id << ' ' << l << '\n';
      // std::cerr << "PUSH " << x + l << ' ' << y << '\n';
      // std::cerr << "PUSH " << x + l << ' ' << y + l << '\n';
    };

    int lt = points[ord[0]].first;
    mp[lt].emplace_back(lo), mp[lt].emplace_back(hi);

    size_t p = 0;
    for (auto it = mp.begin(); it != mp.end(); it = mp.erase(it)) {
      std::vector<int> buc;
      auto &tmp = it->second;
      std::ranges::sort(tmp);
      for (size_t i = 0; i < tmp.size();) {
        size_t j = i;
        while (j < tmp.size() && tmp[i] == tmp[j]) { j++; }
        if ((j - i) & 1) { buc.emplace_back(tmp[i]); }
        i = j;
      }
      assert(~buc.size() & 1);
      if (p == N && buc == std::vector{lo, hi}) { return ans; }
      for (size_t i = 0; i < buc.size(); i += 2) {
        int l = buc[i], r = buc[i + 1];
        // std::cerr << "BUC " << it->first << ' ' << l << ' ' << r << '\n';
        if (p == N || points[ord[p]].first != it->first ||
            points[ord[p]].second != l) {
          return std::nullopt;
        }
        while (p + 1 < N && points[ord[p + 1]].first == it->first &&
               points[ord[p + 1]].second < r) {
          Set(ord[p], points[ord[p + 1]].second - points[ord[p]].second);
          p++;
        }
        Set(ord[p], r - points[ord[p]].second), p++;
      }
    }
    return std::nullopt;
  }
}// namespace Solution

int main() {
#ifdef LOCAL
  freopen("task.in", "r", stdin);
  freopen("task.out", "w", stdout);
  freopen("task.err", "w", stderr);
#endif
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int test;
  std::cin >> test;
  while (test--) {
    int N;
    std::cin >> N;
    std::vector<std::pair<int, int>> points(N);
    for (auto &[x, y]: points) { std::cin >> x >> y; }

    std::optional<std::vector<int>> ans;
    if (N == 1) { ans.emplace({1}); }

    for (int o = 0; o < 2; o++) {
      int lt = INT_MAX;
      for (auto x: points | std::views::keys) { lt = std::min(lt, x); }

      int lo = INT_MAX, hi = INT_MIN;
      for (auto [x, y]: points) {
        if (x == lt) {
          lo = std::min(lo, y);
          hi = std::max(hi, y);
        }
      }

      std::map<int, int> mp;
      for (int i = 0; i < N && !ans; i++) {
        int l = points[i].first - lt;
        if (l && !mp.contains(l)) {
          ans = Solution::Solve(points, lo, hi + l), mp[l] = true;
        }
      }

      for (auto &[x, y]: points) { std::swap(x, y); }
    }

    // if (!ans) {
    //   int p = -1;
    //   for (int i = 1; i < N; i++) {
    //     if (points[p] == std::pair{lt, hi - 1}) { p = i; }
    //   }
    //   if (~p) {
    //     points.erase(points.begin() + p);
    //     ans = Solution::Solve(points, lo, hi);
    //     if (ans) {
    //       (*ans).insert(ans->begin() + p, -1);
    //       int ri = INT_MIN;
    //       for (int i = 0; i < N; i++) {
    //         if (i != p) { ri = std::max(ri, points[i].first + (*ans)[i]); }
    //       }
    //       (*ans)[p] = ri - lt;
    //     }
    //   }
    // }

    if (!ans) {
      std::cout << "NIE\n";
    } else {
      std::cout << "TAK";
      for (auto v: *ans) { std::cout << ' ' << v; }
      std::cout << '\n';
    }
  }

  return 0;
}