1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
#include <bits/stdc++.h>
#define xi first.first
#define yi first.second
#define ii second
using namespace std;
int n, xmin, ymin, X, Y; int L[3000], L1[3000]; bool B[100][100]; pair < pair <int,int> , int > P[3000];
bool solve()
{
    for(int i=0; i<X; i++)
        for(int j=0; j<Y; j++)
            B[i][j]=false;
    for(int i=0; i<n; i++)
        for(int j=0; j<L[i]; j++)
            for(int k=0; k<L[i]; k++)
                if(B[P[i].xi+j][P[i].yi+k])
                    return false;
                else
                    B[P[i].xi+j][P[i].yi+k]=true;
    for(int i=0; i<X; i++)
        for(int j=0; j<Y; j++)
            if(!B[i][j])
                return false;
    return true;
}
void testcase_mosaic()
{
    cin >> n;
    xmin=ymin=(1<<30);
    for(int i=0; i<n; i++){
        cin >> P[i].xi >> P[i].yi;
        xmin = min(xmin,P[i].xi);
        ymin = min(ymin,P[i].yi);
        P[i].ii=i;
    }
    for(int i=0; i<n; i++){
        P[i].xi-=xmin;
        P[i].yi-=ymin;
    }
    sort(&P[0],&P[n]);
    if(P[0].xi!=0 || P[0].yi!=0){
        cout << "NIE\n";
        return;
    }
    if(n==1){
        cout << "TAK 1\n";
        return;
    }
    if(n==2){
        if(P[0].xi==P[1].xi){
            cout << "TAK " << abs(P[1].yi-P[0].yi) << " " << abs(P[1].yi-P[0].yi) << "\n";
            return;
        }
        if(P[0].yi==P[1].yi){
            cout << "TAK " << abs(P[1].xi-P[0].xi) << " " << abs(P[1].xi-P[0].xi) << "\n";
            return;
        }
        cout << "NIE\n";
        return;
    }
    int b=5, b1=1, k;
    if(n>=8)
        b=4;
    if(n>=10)
        b=3;
    if(n>=13)
        b=2;
    if(n>=20)
        b=1;
    for(int j=0; j<n; j++)
        b1*=b;
    for(int j=0; j<b1; j++){
        k=j, X=Y=0;
        for(int i=0; i<n; i++){
            L[i]=(k%b)+1;
            k/=b;
            X=max(X,P[i].xi+L[i]);
            Y=max(Y,P[i].yi+L[i]);
        }
        if(solve()){
            cout << "TAK";
            for(int i=0; i<n; i++)
                L1[P[i].ii]=L[i];
            for(int i=0; i<n; i++)
                cout << " " << L1[i];
            cout <<"\n";
            return;
        }
    }
    cout << "NIE\n";
    return;
}
int main()
{
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int Z;
    cin >> Z;
    while(Z--)
        testcase_mosaic();
    return 0;
}