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
#include <cstdio>
#include <set>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
//#define DEBUG(args...) printf(args);
#define DEBUG(args...)
#define NMX 1000000001ULL
using namespace std;

typedef unsigned long long LG;
set<LG> Fib;

void prepare() {
        LG F[50] = { 0, 1 };
        int k = 1;
        while(F[k] < NMX) {
                ++k;
                F[k] = F[k-1] + F[k-2];
                DEBUG("%d ", F[k]);
        }
        DEBUG("\nk: %d\n", k);
        FOR(i,0,k) FOR(j,0,k) {
                LG product = F[i] * F[j];
                Fib.insert(product);
        }
}

int main() {
        prepare();
        int t; scanf("%d", &t);
        while(t--) {
                LG n; scanf("%llu", &n);
                printf(Fib.find(n) != Fib.end() ? "TAK\n" : "NIE\n");
        }
        return 0;
}