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
#include <stdio.h>
#include <math.h>
#include <stdbool.h>

bool isFibb(unsigned long long int number){
	unsigned long long int X1 = 5 * (number * number) + 4;
	unsigned long long int X2 = 5 * (number * number) - 4;

	unsigned long long int X1s = (unsigned long long int)sqrt((double)X1);
	unsigned long long int X2s = (unsigned long long int)sqrt((double)X2);

	return (X1s*X1s == X1) || (X2s*X2s == X2);
}

int main(int argc, char** argv){
	unsigned int tests;
	unsigned long long int number;
	unsigned long long int divider;
	scanf("%d", &tests);
	while(tests--){
		scanf("%lld", &number);
		unsigned long long int i;
		for(i=1; i<number; i++){
			if(number%i == 0){
				divider = number / i;
				if(isFibb(i) && isFibb(divider)){
					printf("TAK\n");
					goto after;
				}
			}
		}
		printf("NIE\n");
		after:
			i=i;
	}
	return 0;
}