1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    vector<int> fib(2,1);
    while (fib.back() < 1e9)
        fib.push_back(fib.back() + fib[fib.size()-2]);
    vector<long long> tab;
    for (int x: fib)
        for (int y: fib)
            tab.push_back(x*(long long)y);
    sort(tab.begin(), tab.end());
    int t,x;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &x);
        if (binary_search(tab.begin(),tab.end(),x))
            printf("TAK\n");
        else
            printf("NIE\n");
    }
    return 0;
}