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
#include <cstdio>
#include <set>

std::set<long long> products(long long const* from, long long const* until){
	std::set<long long> result;
	for(auto it1 = from; it1 != until; ++it1)
		for(auto it2 = from; it2 != until; ++it2)
			result.insert((*it1) * (*it2));
	return result;
}

int main(){
	const int LIMIT = 1000000000;
	const int N_NUMBERS = 100;

	long long fibonacci[N_NUMBERS];
	
	fibonacci[0] = 0; fibonacci[1] = 1;
	int i;
	for(i = 2; fibonacci[i - 1] <= LIMIT; i++)
		fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2];
	auto fibonacciProducts = products(fibonacci, fibonacci + i);
	int testCases;
	scanf("%d", &testCases);
	while(testCases--){
		long long n;
		scanf("%lld", &n);
		printf("%s\n", fibonacciProducts.count(n) ? "TAK" : "NIE");
	}
}