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
#include<iostream>
#include<vector>
#include<set>
using namespace std;

int main()
{
    long long maxN = 1000000000;
    vector<long long> f;
    f.push_back(0); f.push_back(1);
    long long wsk = 1;
    
    while(true)
    {
       long long next = f[wsk]+f[wsk-1];
       if(next>maxN)break;  
       f.push_back(next);
       ++wsk;
    }
    
    set<long long> els;
    
    for(int i=0;i<wsk;++i)
     for(int j=0;j<wsk;++j)
     {
        long long next = f[i]*f[j];
        if(next>=0 && next<=maxN)
        { 
                   els.insert(next);
        }
     }
    
    int t; cin>>t;
    for(int i=0;i<t;++i)
    {
       long long el; cin>>el;
       if(els.find(el)==els.end()) cout<<"NIE"<<endl;
       else cout<<"TAK"<<endl;
    }
    
    return 0;
}