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<iostream>
#include<cstdio>
using namespace std;
int fib[1000];
int main(){
	int z;
	cin >> z;
	fib[0] = 0;
	fib[1] = fib[2] = 1;
	int k = 2;
	while(fib[k]<1000000000){
		fib[k+1] = fib[k]+fib[k-1];
		k++;
	}
	while(z--){
		long long int n;
		cin >> n;
		int end = 0;
		while(fib[end] < n) end++;
		int beg = 0;
		int ok = false;
		while(beg<=end){
			if(fib[beg]*fib[end]<n)beg++;
			else if(fib[beg]*fib[end]>n)end--;
			else { ok = true; break; }
		}
		if(ok) cout << "TAK\n";
		else cout << "NIE\n";
	}
}