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

using namespace std;

vector<long> fibos;

void fiboinit() {
        long curfibo = 1;
        long fiboind = 2;
        fibos.push_back(0);
        fibos.push_back(1);

        while(curfibo < 20000) {
                curfibo = fibos[fiboind-1] + fibos[fiboind-2];
                ++fiboind;
                fibos.push_back(curfibo);
        }
}


int main() {
        int count;

        fiboinit();

        cin >> count;
        for(int i = 0; i < count; ++i) {
                long n;
                cin >> n;
                bool div = false;
                for (int j = 1; j < fibos.size(); ++j) {
                        if(n % fibos[j] == 0) {
                                for (int k = 1; k < fibos.size(); ++k) {
                                        if (fibos[j]*fibos[k] == n) {
                                                div = true;
                                        }
                                }
                        }
                }
                if(div) {
                        cout << "TAK" << endl;
                } else {
                        cout << "NIE" << endl;
                }
        }

        return 0;
}