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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>

class FibonacciSequence : public std::vector<long long unsigned>
{
public:
    FibonacciSequence()
    {
        push_back(1);
        push_back(1);
    }

    long long unsigned operator[](size_t n)
    {
        while (n + 1 > size())
        {
            size_t last = size() - 1;
            push_back(Base::operator[](last - 1) + Base::operator[](last));
        }

        return Base::operator[](n);
    }

    long long unsigned upperBound(long long unsigned n)
    {
        while (back() < n)
        {
            operator[](size());
        }
        return back();
    }

private:
    typedef std::vector<long long unsigned> Base;
    using Base::operator[];
};

class ProblemSolver
{
public:
    bool isProductOfTwoFibonacciNumbers(long long unsigned n)
    {
        if (n == 0)
            return true;

        m_fibSeq.upperBound(n);
        for (size_t i = 0; i < m_fibSeq.size() && m_fibSeq[i] <= sqrt(n); ++i)
        {
            if (n % m_fibSeq[i] == 0 &&
              std::binary_search(m_fibSeq.begin(), m_fibSeq.end(), n / m_fibSeq[i]))
                return true;
        }
        return false;
    }

protected:
    FibonacciSequence m_fibSeq;
};

int main()
{
    ProblemSolver solver;

    std::ios_base::sync_with_stdio(0);
    
    unsigned t;
    std::cin >> t;

    while (t--)
    {
        unsigned n;
        std::cin >> n;

        if (solver.isProductOfTwoFibonacciNumbers(n))
            std::cout << "TAK\n";
        else
            std::cout << "NIE\n";
    }

    return 0;
}