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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long int LL;

vector <LL> tworz_spis()
{
	vector <LL> Fibb;
	
	Fibb.push_back(1);
	Fibb.push_back(1);
	
	int M = Fibb.size() - 1;
	
	while(Fibb[M] + Fibb[M - 1] <= 1e9)
	{
		Fibb.push_back(Fibb[M] + Fibb[M - 1]);	M++;
	}
	
	return Fibb;
}

vector <LL> oblicz_iloczyn(vector <LL> Fibb)
{
	vector <LL> Iloczyn;
	
	for(int i = 0; i < Fibb.size(); i++)
		for(int j = i; j < Fibb.size(); j++)
			if(Fibb[i] * Fibb[j] <= 1e9)
				Iloczyn.push_back(Fibb[i] * Fibb[j]);
				
	return Iloczyn;
}

vector <LL> SPISUJ()
{
	vector <LL> Fibb = tworz_spis();
	vector <LL> Iloczyn = oblicz_iloczyn(Fibb);
	
	sort(Iloczyn.begin(), Iloczyn.end());
	
	vector <LL> SPIS;
	
	for(int i = 0; i < Iloczyn.size() - 1; i++)
		if(Iloczyn[i] != Iloczyn[i + 1])
			SPIS.push_back(Iloczyn[i]);
			
	SPIS.push_back(Iloczyn[Iloczyn.size() - 1]);
	
	return SPIS;
}

int main()
{
	int t;
	cin >> t;
	
	vector <LL> SPIS = SPISUJ();
	
	while(t--)
	{
		LL n;
		cin >> n;
		
		if(binary_search (SPIS.begin(), SPIS.end(), n))
			cout << "TAK" << endl;
		else
			cout << "NIE" << endl;
	}

	return 0;
}