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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct fib_pair{
unsigned int f1;
unsigned int f2;
};

constexpr unsigned int SIZE = 10;

inline void get_next(fib_pair &p){
    unsigned int t = p.f2;
    p.f2 = p.f1 + p.f2;
    p.f1 = t;
}

inline bool is_divisible(const unsigned int x, const fib_pair &p){
    return x % p.f2 == 0;
}

inline bool is_greater(const unsigned int x, const fib_pair &p){
    return x >= p.f2;
}

inline unsigned int get_division(const unsigned int x, const fib_pair &p){
    return x / p.f2;
}

inline bool in_save(unsigned int x,std::vector<unsigned int> saved){
    return binary_search(saved.begin(),saved.end(),x);
}

bool is_fib_decomp(const unsigned int x){
    fib_pair fib{1,2};
    unsigned int tmp = x;
    std::vector<unsigned> saved;
    saved.reserve(SIZE);
    saved.push_back(1);

    while( is_greater(tmp,fib) ){
        if( is_divisible(tmp,fib) ){
            unsigned t = get_division(tmp,fib);
            saved.push_back(fib.f2);
            if( in_save(t,saved) )
                return true;
        }
        get_next(fib);
    }
    return false;
}

int main()
{
    int n;
    cin >> n;
    for( int i=0; i<n; i++){
        unsigned int tmp;
        cin>>tmp;
        if( is_fib_decomp(tmp) ){
            cout<<"TAK\n";
        }else{
            cout<<"NIE\n";
        }
    }
    return 0;
}