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
50
51
52
#include <iostream>
#include <cstdlib>
#include <vector>

using namespace std;

void fib (vector<long long int> &fibNumber, long long int interval){
	long long int f0 = 0;
  	long long int f1 = 1;
  	long long int f=0;
  	int i = 0;
  	while(f<interval){
  	
	    if(i > 1)
	    {
	      f  = f0 + f1;
	      f0 = f1;
	      f1 = f;
	    }
	    else f = i;
	    fibNumber.push_back(f);
		i++;
	    
	}
}

int main(){
	//int
	int t;
	cin >> t;
	
	
	for(int i = 0; i < t; i++){
		//vector
		vector<long long int> fibNumber;
		//int
		int tmp;
		//bool
		bool result = false;
		
		cin >> tmp;
		fib(fibNumber,tmp);

		for(int i = 0; i < fibNumber.size(); i++)
			for(int j = 0; j < fibNumber.size(); j++)
				if(fibNumber[i]*fibNumber[j] == tmp) result = true;
		if(result) cout << "TAK" << endl; else cout << "NIE" << endl;
	}
	
	//system("pause");
	return 0;	
}