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
#include<iostream>
#include<set>
#define SETINT std::set<int>
#define CI const_iterator

const int max=1000000000;

SETINT genFib(int m){
	SETINT S;
	S.insert(1);
	int p2=0,p1=1;
	while(p1<=max)
		S.insert(p1+p2),p2=p1,p1=*(--S.end());
	return S;	
}

int main(){
	std::ios_base::sync_with_stdio(false);
	
	SETINT fibs=genFib(max);
	unsigned int t;
	std::cin>>t;
	
	while(t-->0){
		int a;
		bool s=false;
		std::cin>>a;
		for(SETINT::CI iE=fibs.begin();iE!=fibs.end()&&*iE*(*iE)<=a;++iE)
			if(!(a%*iE)&&fibs.find(a/ *iE)!=fibs.end()){
				s=true;
				break;
			}
		
		if(a)
			std::cout<<(s?"TAK":"NIE")<<"\n";
		else
			std::cout<<"TAK"<<"\n";
	}
	
	return 0;
}