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
47
48
49
50
/** Potyczki Algorytmiczne 2014 - Runda próbna - Iloczyn */

#include <cstdio>
#include <cmath>
#include <vector>

using namespace std;

const long Max = 1000000001;

long fibNum[] = {2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987,
	1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418,
	317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465,
	14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296,
	433494437, 701408733};

bool isFib[Max] = {0};

int main(void){
	long n, x, sqrtx;
	bool ok;
	
	isFib[0] = isFib[1] = true;
	
	for(int i=0;i<42;++i){
		isFib[fibNum[i]] = true;
	}
	
	scanf("%ld",&n);
	
	for(long i=0;i<n;++i){
		scanf("%ld",&x);
		sqrtx = ceil(sqrt(x))+1;
		ok = isFib[x]?true:false;
		
		for(long j=0;!ok && fibNum[j]<sqrtx;++j){			
			if(x%fibNum[j]==0 && isFib[x/fibNum[j]]){
				ok = true;
				break;
			}
		}
		
		if(ok)
			printf("TAK\n");
		else
			printf("NIE\n");
	}
	
	return 0;
}