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

bool vfind(int x, vector<int> v,int b,int e){
	
	if(b==e) return x==v[b];
	if(e-b==1) return (x==v[b] || x==v[e]);
	int mid=(e+b)/2;
	if(x==v[mid]) return true;
	if(x<v[mid]) return vfind(x,v,b,mid-1);
	if(x>v[mid]) return vfind(x,v,mid,e);
	}

int main() {
	int t,n,s,m,i,x;
	bool b;
	vector<int> v;
	v.push_back(0);
	v.push_back(1);
	
	cin>>t;
	while(t){
		cin>>n;
		b=false;
		s=v.size();
		while(v[s-1]<n) {m=v[s-2]+v[s-1]; v.push_back(m); s++;}
		
		if(n<4) cout<<"TAK"<<endl; 
		else{
			for(i=2; v[i]<n/2+1; i++){
				if(!(n%v[i])){
					x=n/v[i]; b=vfind(x,v,2,s-1);
				}
				if(b) break;
			}
			if(b) cout<<"TAK"<<endl;
			else cout<<"NIE"<<endl;
		}
		t--;
		}
	return 0;
}