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
90
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <cctype>
#include <cmath>
#include <iostream>
#include <set>
#include <map>
#include <sstream>
#include <typeinfo>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ull> vull;
typedef vector<string> vs;
 
#define SIZE(x) ((int)(x.size()))
#define LET(var, val) typeof(val) var = (val)
#define FOR(k, a, b) for(typeof(a) k = (a); k < (b); ++k)
#define FORR(k, a, b) for(typeof(a) k = (a); k >= (b); --k)
#define REP(x, n) for(int x = 0; x < (n); ++x)
#define ALL(c) (c).begin(), (c).end()
#define FOREACH(i, c) for(LET(i, (c).begin()); i != (c).end(); ++i)
#define PB push_back
#define PF push_front
 
const int INF = 1000000001;
const double EPS = 10e-9;
const double PI = acos(-1.0);
 
ostringstream out;

int fibonacci[45];


bool is_fibonacci(int n)
{
	long test1 = 5 * n * n + 4;
	long test2 = 5 * n * n - 4;
	long sq1 = sqrt(test1);
	long sq2 = sqrt(test2);
	return (test1 == sq1 * sq1 || test2 == sq2 * sq2);
}

int main()
{
	ios_base::sync_with_stdio(0);
	fibonacci[0] = 0;
	fibonacci[1] = 1;
	fibonacci[2] = 2;
	{
		int i = 2;
		while (fibonacci[i] <= 1000000000)
		{
			i++;
			fibonacci[i] = fibonacci[i-1] + fibonacci[i-2];
		}
	}
	int t;
	cin >> t;
	while (t--)
	{
		int n;
		cin >> n;
		int sq = (int)sqrt(n);
		int i = 0;
		bool is = false;
		if (n == 0)
		{
			out << "TAK\n";
			continue;
		}
		while (fibonacci[++i] <= sq)
		{
			if (n % fibonacci[i] == 0 && is_fibonacci(n / fibonacci[i]))
			{
				is = true;
				break;
			}
		}
		out << (is ? "TAK\n" : "NIE\n");
	}
	cout << out.str();
	return 0;
}