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
#include <cstdio>
#include <algorithm>
#include <string>

class FibSet
{
public:
	FibSet(int n);
	FibSet(const FibSet &arg);
	virtual ~FibSet() { delete fib; }
	
	FibSet& operator= (const FibSet &arg);
	int operator[] (const unsigned int i) const { return fib[i]; }

	bool isFib(int value);
	int  length() { return len; }

private:
	int *fib;
	int len;
};

FibSet::FibSet(int n)
{
	fib = new int[n + 1];
	
	len = n;
	fib[0] = 1;
	fib[1] = 1;
	for(int i = 2; i <= n; i++)
		fib[i] = fib[i - 2] + fib[i - 1];
}

FibSet::FibSet(const FibSet &arg)
{
	fib = new int[len];
	
	for(int i = 0; i < len; i++)
		fib[i] = arg[i];
}

FibSet& FibSet::operator= (const FibSet& arg)
{
	delete fib;
	
	fib = new int[len];
	
	for(int i = 0; i < len; i++)
		fib[i] = arg[i];
		
	return *this;
}

bool FibSet::isFib(int value)
{
	return std::binary_search(fib, fib + len + 1, value);
}

int main()
{
	FibSet fib(45);
	
	int t;
	scanf("%d", &t);
	while(t--)
	{
		int n, i = 0;
		std::string res;
		
		scanf("%d", &n);
		while(fib[i] <= n)
		{
			if(n % fib[i] == 0)
			{
				if(fib.isFib(n / fib[i]))
				{
					res = std::string("TAK");
					break;
				}
			}
			i++;
		}
		if(res.empty()) res = std::string("NIE");
		printf("%s\n", res.c_str());
	}
	
	return 0;
}