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
#include <stdio.h>

int ok(int n) {
	int fib[] = {1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733};
	int *fa, *fb;
	int x, res = 0;
	fa = fib;
	fb = fib+sizeof(fib)/sizeof(*fib)-1;
	if(!n)
		res = 1;
	while(n < *fb)
		fb--;
	while(!res && fa <= fb) {
		if(!(n % *fb)) {
			x = n / *fb;
			while(*fa < x) {
				fa++;
			}
			if(x == *fa)
				res = 1;
		}
		fb--;
	}
	return res;
}

int main() {
	int t, n;
	scanf("%d", &t);
	while(t--) {
		scanf("%d", &n);
		printf("%s\n", ok(n) ? "TAK" : "NIE");
	}
	return 0;
}