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
// Karol Różycki Zadanie Iloczyn
#include<cstdio>
#define MAX 60
using namespace std;

long long int FIB[MAX];

void init(){
	FIB[0] = 0;
	FIB[1] = 1;
	for(int i = 2; i < MAX; i++){
		FIB[i] = FIB[i - 1] + FIB[i - 2];
	}
}

int main(){
	int t;
	scanf("%d",&t);
	init();
	while(t--){
		long long int n;
		scanf("%lld",&n);
		if(n == 0){
			printf("TAK\n");
		}else{
			bool a = false;
			for(int i = 1; FIB[i] <= n; i++){
				int j = 1;
				long long int m = n / FIB[i];
				while(FIB[j] < m){
					j++;
				}
				if(FIB[i] * FIB[j] == n){
					a = true;
					break;
				}
			}
			if(a){
				printf("TAK\n");
			}else{
				printf("NIE\n");
			}
		}
	}
	return 0;
}