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
59
// pa2014-0.cpp : Defines the entry point for the console application.
//

//
#include "stdio.h"

int		  ff[100], fn;

void
init()
{
	int		 a = 0, b = 1, c = 1;

	ff[0]	= a;
	ff[1]	= b;
	fn		= 2;
	while (c<=1000000000)
	{
		ff[fn++]	= c;
		a	= b;
		b	= c;
		c	= a + b;
	}
}

void
calc()
{
	int		 n, a, b, ia, ib, i;

	scanf("%d", &n);
	ib	= 0;
	for (ia=1; ff[ia]<=n && ia<fn && ib==0; ia++)
	{
		a	= ff[ia];
		b	= n / a;
		if (b>=a && a * b == n)
		{
			for (i=ia; ff[i]<=b && i<fn; i++)
				if (ff[i]==b)
					ib	= i;
		}
	}

	printf("%s\n", (ib==0) ? "NIE" : "TAK");
}

int
main()
{
	int		 t;

	init();
	scanf("%d", &t);
	while (t--)
		calc();

	return 0;
}