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
#include <cstdio>
#include <vector>
#include <set>
using namespace std;

void fib_up_to(int limit, vector<int> &out){
    int pfn = 1;
    int fn = 0;
    while(fn < limit){
        out.push_back(fn);
        int x = fn;
        fn = pfn + fn;
        pfn = x;
    }
}
void products_set(const vector<int> &val, int limit, set<int> &out){
    for(int i=0;i<val.size();i++){
        int cur = val[i];
        if(!cur){
            out.insert(0);
            continue;
        }
        int up_to = limit/cur + 1;
        for(int j=0;j<val.size() && val[j] < up_to;j++){
            out.insert(val[j] * cur);
        }
    }
}

const int MAX_N = 1000000000;

int main(){
    // *** PRE-PROCESSING ***
    vector<int> fibs;
    fib_up_to(MAX_N, fibs);
    //for(int i=0;i<fibs.size();i++){ printf(" %d", fibs[i]); } printf("\n");
    set<int> prod;
    products_set(fibs, MAX_N, prod);
    //for(set<int>::iterator it=prod.begin();it!=prod.end();it++){ printf(" %d", *it); } printf("\n");

    // *** TESTS ***
    int t;
    scanf("%d",&t);
    while(t--){
        int x;
        scanf("%d",&x);
        printf("%s\n", (prod.find(x) != prod.end()) ? "TAK" : "NIE");
    }
    return 0;
}