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
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

const int MAX_INT = 1000 * 1000 * 1000;
vector<int> fibo;

int main()
{
	fibo.push_back(0);
	fibo.push_back(1);
	while(fibo[fibo.size()-1] + fibo[fibo.size()-2] <= MAX_INT)
	{
		fibo.push_back(fibo[fibo.size()-1] + fibo[fibo.size()-2]);
	}
	
	int n, x;
	bool possible;
	scanf("%d", &n);
	while(n--)
	{
		possible = false;
		scanf("%d", &x);
		for(int i = 0; i < fibo.size(); i++)
		{
			for(int j = i; j < fibo.size(); j++)
			{
				if((long long int)fibo[i] * fibo[j] == x)
				{
					possible = true;
					break;
				}
			}
			if(possible == true)
				break;
		}
		if(possible == true)
			printf("TAK\n");
		else
			printf("NIE\n");
	}
	
	return 0;
}