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
// copyright (c) miodziu@poczta.fm

#include <cstdio>
#include <vector>
#include <set>

const int MAXN = 1000000000;

int read() {
    int n;
    scanf("%d", &n);
    return n;
}

class FibonacciProdukt {
    std::vector<int> fib;
    std::set<int> fibProd;

    void initFib(int maxN) {
        fib.push_back(0);
        fib.push_back(1);
        while (fib.back() <= maxN)
            fib.push_back(fib[fib.size() - 2] + fib[fib.size() - 1]);
        fib.pop_back();
    }

    void initFibProd(long long maxN) {
        for (int i=0; i<fib.size(); ++i) {
            for (int j=i; j<fib.size(); ++j) {
                long long prod = 1LL * fib[i] * fib[j];
                if (prod <= maxN)
                    fibProd.insert(prod);
            }
        }
    }

public:
    FibonacciProdukt(int maxN) {
        initFib(maxN);
        initFibProd(maxN);
    }

    bool operator() (int candidate) {
        return fibProd.count(candidate) > 0;
    }
};

int main() {
    FibonacciProdukt fibProdChecker(MAXN);
    int t = read();
    while (t--)
        printf("%s\n", fibProdChecker(read()) ? "TAK" : "NIE");
    return 0;
}