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
#include<cstdio>

using namespace std;

typedef struct myMat {
public:
    long long a, b, c, d;
    myMat(long long na, long long nb, long long nc, long long nd) {
        a = na; b = nb;
        c = nc; d = nd;
    }
    myMat() {
        a = 1; b = 0;
        c = 0; d = 1;
    }
} myMat;

myMat mul(myMat x, myMat y) {
    return myMat(x.a*y.a + x.b*y.c, x.a*y.b + x.b*y.d,
            x.c*y.a + x.d*y.c, x.c*y.b + x.d*y.d);
}

myMat pow(myMat a, int n) {
    if(n == 0)
        return myMat();
    if(n % 2 == 1)
        return mul(pow(a, n-1), a);
    else {
        myMat temp = pow(a, n/2);
        return mul(temp, temp);
    }
}

long long fib(int n) {
    myMat f(1, 1, 1, 0);
    f = pow(f, n);
    return f.b;
}

int main() {
    long long p, q, a, b, c, i, j, k, t, result, req;
    scanf("%lld", &t);
//    for(int i=0; i<t; i++)
//        printf("%d: %lld\n", i, fib(i));
//    return 0;
    while(t--) {
        result = 0;
        scanf("%lld", &req);
        a = 0; b = 1;
        while(!result && a < req) {
            p = 0; q = 32;
            while(p != q) {
                c = (p+q)/2;
                if(a * fib(c) >= req)
                    q = c;
                else
                    p = c + 1;
            }
            if(a * fib(p) == req) {
                result = 1;
            }
            b = b + a;
            a = b - a;
        }

        if(result)
            printf("TAK\n");
        else
            printf("NIE\n");

    }
    return 0;
}