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
/*************************************************************************
 *   Zadanie:           Iloczyn                                          *
 *   Zlozonosc czasowa: O(t log n log log n)                             *
 *   Wynik:             --/10                                            *
 *************************************************************************/

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define FOR(x,b,e) for(int x=b; x<=e; ++x)

/*************************************************************************/

int main()
{
    ios_base::sync_with_stdio(0);

    int F[44] = {1, 1};
    FOR(i,2,43) F[i] = F[i-1] + F[i-2];

    int t;
    cin >> t;

    FOR(c,1,t)
    {
        int n;
        cin >> n;

        bool ans = (n == 0);

        for(int i = 1; F[i]*F[i] <= n; ++i)
            if (n%F[i] == 0 && binary_search(F,F+44,(n/F[i])))
            {
                ans = 1;
                break;
            }
        cout << ((ans)? "TAK" : "NIE") << '\n';
    }

    return 0;
}

/*************************************************************************/