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
53
54
55
56
57
58
#include <iostream>
using namespace std;

int main() {
	int k;
	scanf("%d",&k);
	while(k>0)
	{
	
		long int t;
		scanf("%ld",&t);
		long int f1=1;
		long int f2 = 1;
		long int c = 2;
		while(c<t)
		{
			f1 = f2;
			f2 = c;
			c = f1+f2;
		}
		if(c==t)
		{
			printf("TAK\n");
			k--;
			continue;
		}
		long int fm1 = 1;
		long int fm2 = 2;
		while(true)
		{
			
			if(fm2>f2) 
			{
				printf("NIE\n");
				break;
			}
			long int L = fm2*f2;
			if(L == t) 
			{
				printf("TAK\n");
				break;
			}
			if(L > t)
			{
				long int T = f2 - f1;
				f2 = f1;
				f1 = T;
				continue;
			}
			long int T2 = fm1 + fm2;
			fm1 = fm2;
			fm2 = T2;
		}
		
		k--;
	}
	return 0;
}