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
#include<iostream>
#include<vector>
#include<set>
using namespace std;
const long long max_number = 1000000000;
vector<long long> fib = {0, 1};
set<long long> s = {0, 1};
int main() {
	long long f0 = 0, f1 = 1, f2  = 1, count = 0, n, t;
	while (f2 <= max_number) {
		f0 = f1; 
		f1 = f2;
		f2 = f0 + f1;
		fib.push_back(f2);
		for (int i = 0; i < fib.size(); ++i) 
			s.insert(f2 * fib.at(i));
	};
	cin >> t;
	for (int i = 0; i < t; ++i) {
		cin >> n;
		if (s.count(n) > 0) 
			cout << "TAK\n";
		else
			cout << "NIE\n";
	};
};