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
#include<cstdio>

long long fib[50];

int main()
{
	fib[0] = 0;
	fib[1] = 1;
	for (int i=2; fib[i-1] <= 1000*1000*1000; ++i)
		fib[i] = fib[i-1] + fib[i-2];
	for (int i=2; i < 50; ++i)
		if (fib[i-1] >= fib[i])
			fib[i] = fib[i-1];
	//efekt: [0, 1, 1, 2, ..., X, X, X, X], gdzie X to pierwsza l. Fib. większa od 10^9
	int t;
	scanf("%d", &t);
	while (t--) {
		long long n;
		scanf("%lld", &n);
		int b=0,e=49;
		while (b <= e && fib[b]*fib[e] != n) {
			if (fib[b] * fib[e] < n)
				++b;
			else
				--e;
		}
		if (fib[b]*fib[e] == n)
			printf("TAK\n");
		else
			printf("NIE\n");
	}
	return 0;
}