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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <cstdio>
#include <map>

#define FOREACH(i, n) for(int i=0;i<n;i++)

using namespace std;

int F[]={1,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};

map<int, bool> T;

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

bool check(int n){
	if(T[n])
		return true;

	FOREACH(i, 43)
		if(n%F[i]==0 && T[n/F[i]])
			return true;

	return false;
}

int main(){
	int t, n;
	scanf("%d", &t);

	T_data();
	FOREACH(i, t){
		scanf("%d", &n);
		printf(check(n) ? "TAK\n" : "NIE\n");
	}
	return 0;
}