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
#include <stdio.h>
#include <vector>

using namespace std;

int main() {
	vector<int> fibs;
	int f0 = 0, f1 = 1;
	do {
		fibs.push_back(f1);
		int x = f0 + f1;
		f0 = f1;
		f1 = x;
	} while(f1 <= 1000000000);
	int t;
	scanf("%d", &t);
	for(int i = 0; i < t; i++) {
		int n;
		scanf("%d", &n);
		bool found = false;
		for(vector<int>::iterator it1 = fibs.begin(); it1 < fibs.end() && *it1 * *it1 <= n && !found; ++it1)
			if(n % *it1 == 0)
				for(vector<int>::iterator it2 = it1; it2 < fibs.end() && *it1 * *it2 <= n; ++it2)
					if(*it1 * *it2 == n)
						found = true;
		printf(found? "TAK\n" : "NIE\n");
	}
	return 0;
}