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
82
83
84
85
86
87
88
89
#include <iostream>
#include <algorithm>
#define ULL unsigned long long

using namespace std;


ULL fib[44];

bool check(ULL num)
{
	for (int i = 3; i < 44; i++)
		if (num % fib[i] == 0)
		{
			ULL n = num / fib[i];
			bool res = n == 1 || find(fib + 3, fib + 44, n) != fib + 44;
			if (res)
				return true;
		}
	

	return false;
}

int main()
{
	fib[0] = 0;
	fib[1] = 1;
	fib[2] = 1;
	fib[3] = 2;
	fib[4] = 3;
	fib[5] = 5;
	fib[6] = 8;
	fib[7] = 13;
	fib[8] = 21;
	fib[9] = 34;
	fib[10] = 55;
	fib[11] = 89;
	fib[12] = 144;
	fib[13] = 233;
	fib[14] = 377;
	fib[15] = 610;
	fib[16] = 987;
	fib[17] = 1597;
	fib[18] = 2584;
	fib[19] = 4181;
	fib[20] = 6765;
	fib[21] = 10946;
	fib[22] = 17711;
	fib[23] = 28657;
	fib[24] = 46368;
	fib[25] = 75025;
	fib[26] = 121393;
	fib[27] = 196418;
	fib[28] = 317811;
	fib[29] = 514229;
	fib[30] = 832040;
	fib[31] = 1346269;
	fib[32] = 2178309;
	fib[33] = 3524578;
	fib[34] = 5702887;
	fib[35] = 9227465;
	fib[36] = 14930352;
	fib[37] = 24157817;
	fib[38] = 39088169;
	fib[39] = 63245986;
	fib[40] = 102334155;
	fib[41] = 165580141;
	fib[42] = 267914296;
	fib[43] = 433494437;
	fib[44] = 701408733;


	int t;
	ULL num;

	cin >> t;

	while (t--)
	{
		cin >> num;
		if (num == 0 || num == 1 || check(num))
			cout << "TAK\n";
		else
			cout << "NIE\n";
	}

	return 0;
}