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

using namespace std;

const int MAX = 1000000000;

void solve_case(vector<int>* fib, vector<int>::iterator begin, vector<int>::iterator end) {
    int n, m;
    
    scanf("%d", &n);
    
    for (vector<int>::iterator it = begin; it != end; ++it) {
        m = *it;
        if (n % m == 0 && binary_search(begin, end, n / m)) {
            printf("TAK\n");
            return;
        }
    }
    
    printf("NIE\n");
}

vector<int>* get_fib() {
    vector<int>* fib = new vector<int>();
    int a = 1, b = 1, c;
    
    fib->push_back(a);

    do {
        fib->push_back(b);
        c = a + b;
        a = b;
        b = c;
    } while (b <= MAX);
    
    return fib;
}

int main() {
    vector<int>* fib = get_fib();
    vector<int>::iterator begin = fib->begin();
    vector<int>::iterator end = fib->end();

    int cases;
    scanf("%d", &cases);
    
    for (int i = 0; i < cases; ++i) {
        solve_case(fib, begin, end);
    }

    delete fib;
    
    return 0;
}