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

int main() {
	long long int fib[1000];
	int N=1;

	fib[0]=0;
	fib[1]=1;
	while (fib[N] <= 1000000000LL) {
		++N;
		fib[N] = fib[N-1]+fib[N-2];
	}
	
	int K;
	scanf("%d",&K);
	while (K--) {
		long long int v;
		bool ok = false;
		scanf("%lld",&v);
		
		for (int i=0;i<=N;++i) {
			for (int j=0;j<=N;++j) {
				if (fib[i]*fib[j] == v) ok = true;
			}
		}
		
		printf("%s\n",ok?"TAK":"NIE");
	}
	

	return 0;
}