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
#include<algorithm>
#include<iostream>
#include<list>
#include<map>
#include<queue>
#define FOR(i,n) for(int i = 0;i<n;++i)
#define FORI(i,b,n) for(int i = b;i<n;++i)
#define FORD(i,n) for(int i = n;i>=0;--i)
#define ZERO 0.000001
#define MAX ((1<<31)-1)
#define qprintf debug && printf
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define ull long long int
//int debug=0;
//#define dcout debug && cout
using namespace std;
#define MP 33343
#define MAX_FACTORS 1000
#define MAX_DIFF_FACTORS 15
int main(){
        int n;
        cin>>n;
        int t[100];
        t[0]=0;
        t[1]=1;
        int h=1;
        while(t[h]<=1000000000){
                ++h;
                t[h]=t[h-1]+t[h-2];
        }
        while(n--){
                int k;
                cin>>k;
                ull s;
                int ok=0;
                FOR(i,h){
                        s=0;
                        FOR(j,h){
                                if(j>i)break;
                                if(s>k)break;
                                s=t[i]*(ull)t[j];
                                if(s==k){
                                        i=h;ok=1;
                                        cout<<"TAK"<<endl;
                                }
                        }
                }
                if(!ok)cout<<"NIE"<<endl;
        }
        return 0;
}