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
#include <algorithm>
#include <iostream>
#include <vector>
#define MAX_N 1000000000
using namespace std;

int t;
vector<int> fib;

int main()
{
	for (int a=0,b=1; a<=MAX_N; ) {
		fib.push_back(a);
		swap(a+=b,b);
	}

	cin >> t;
	for (int i=0; i<t; ++i) {
		int n;
		cin >> n;
		if (n==0) goto tak;
		for (int i=2; i<fib.size(); ++i) {
			if (n%fib[i]==0)
				if (binary_search(fib.begin(), fib.end(), n/fib[i]))
					goto tak;
		}
		cout << "NIE\n";
		continue;
		tak:
		cout << "TAK\n";
	}

	return 0;
}