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
#include <cstdio>
using namespace std;

const long long fibs[] = {0,1,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,1134903170,1836311903};

const long MAX=45;

int main() {
	long t;
	long long x;
	bool possible;
	scanf("%ld\n", &t);

	for (int i=0; i<t; i++) {
		scanf("%lld\n", &x);
		//printf("%ld\n", fibs[x]);

		possible = false;

		for (int j=0;j<MAX && fibs[j]<=x;j++) {
			for (int k=0;k<MAX && fibs[k]<=x;k++) {
				if (fibs[j]*fibs[k] == x) {
					possible = true;
				}
			}		
		}
		if (possible) {
			printf("TAK\n");
		} else {
			printf("NIE\n");
		}
	}

	return 0;
}