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
42
43
44
45
46
47
48
49
//============================================================================
// Name        : test.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
using namespace std;

int gen(long* f) {
	f[0]=0;
	f[1]=1;
	for(int i=0; i<1000; i++) {
		f[i+2]=f[i+1]+f[i];
		//cout << f[i+2] << ' ';
		if(f[i+2]>1000000000) return i+1;
	}
	return 0; //error
}

bool check(long* f, int imax, long value) {
	for(int i=1; i<=imax; i++) {
		if(value%f[i] == 0)
		{
			long v2 = value/f[i];
			//find v2
			for(int i2=1; i2<=imax; i2++)
			{
				if(f[i2]==v2) return true;
			}
		}
	}

	return false;
}

int main() {
	int n;
	long a[10];
	long f[1000];
	int imax = gen(f);
	//cout << endl << imax;
	cin >> n;
	for(int i=0; i<n; i++) cin >> a[i];
	for(int i2=0; i2<n; i2++) cout << (check(f, imax, a[i2]) ? "TAK" : "NIE") << endl;
	return 0;
}