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

using namespace std;

typedef long long LL;
vector<int> fib;
const int MAKS = 1e9+7;

int main () {
	fib.push_back(0);
	fib.push_back(1);
	int size = 2;
	while(fib[size-1]+fib[size-2] < MAKS) {
		fib.push_back(fib[size-1]+fib[size-2]);
		size++;
	}

	vector<int> fib2;

	for(int i=0;i<(int)fib.size();i++) {
		for(int j=0;j<(int)fib.size();j++) {
			if((LL)fib[i]*fib[j] < (LL)MAKS)
				fib2.push_back(fib[i]*fib[j]);
		}
	}

	sort(fib2.begin(), fib2.end());

	int t,a;
	scanf("%d", &t);
	while(t--) {
		scanf("%d",&a);
		if(binary_search(fib2.begin(), fib2.end(), a))
			printf("TAK\n");
		else
			printf("NIE\n");
	}
}