1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<cstdio>

typedef long long int int64;

int main () {
	int64 fib[] = {0L, 1L, 2L, 3L, 5L, 8L, 13L, 21L, 34L, 55L, 89L, 144L, 233L, 377L, 610L, 987L, 1597L, 2584L, 4181L, 6765L, 10946L, 17711L, 28657L, 46368L, 75025L, 121393L, 196418L, 317811L, 514229L, 832040L, 1346269L, 2178309L, 3524578L, 5702887L, 9227465L, 14930352L, 24157817L, 39088169L, 63245986L, 102334155L, 165580141L, 267914296L, 433494437L, 701408733L, 1134903170L};
	int64 t, i, j, k, n;
	scanf("%lld", &t);
	for (i = 0; i < t; ++i) {
		scanf("%lld", &n);
		bool found = false;
		for (j = 0; j < 44; ++j) {
			for (k = 0; k < 44; ++k) {
				if (fib[j] * fib[k] == n) {
					found = true;
					break;
				}
			}
			if (found) break;
		}
		printf(found ? "TAK\n" : "NIE\n");
	}
	return 0;	
}