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
#include <cstdio>

int main(){
	int fib[45] ={2,3};
	int ok,i,j,n,t;
	for(i=2; i<45; i++)
		fib[i] = fib[i-2] + fib[i-1];
	//for(i=0; i<45;i++)
       //printf("%d ",fib[i]);
	     
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(ok=0,i=0,j=41;fib[j]>n;j--);
		if(n%fib[j] == 0) ok=1;
		else
		for(; fib[j]*fib[j]>=n;j--){
		        if(n%fib[j]==0){
		             while(n/fib[j]>fib[i])++i;
		             if(n/fib[j]==fib[i]){ok=1; break;}
			    }
		     }
			//printf("\n%d %d\n",i,j);   
		   if(ok)	   
			   puts("TAK");
		   else 
		       puts("NIE");
		  }	   
	return 0;
}