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
#include <cstdio>
#include <vector>
#define SIZE(x) ((int)(x).size())
#define REP(i,b) for(int i=0; i<(b); ++i)
#define PB push_back

using namespace std;
typedef vector<int> VI;

const int MAXN = 1000000000;
int t;

bool is_multi(int x, VI& S) {
	int s = SIZE(S);
	REP(i,s) {
		REP(j,s) {
			if (S[i] * S[j] == x) return true;
		}
	}
	return false;
}

int main() {
	VI fib;
	fib.PB(0); fib.PB(1); fib.PB(1);

	while(fib.back()<MAXN) {
		int b = fib[SIZE(fib)-2] + fib[SIZE(fib)-1];
		fib.PB(b);
	}
	fib.erase(--fib.end());

	//for(auto x: fib) printf("%d\n", x);


	scanf("%d", &t);
	REP(i,t) {
		int a;
		scanf("%d", &a);
		printf(is_multi(a,fib) ? "TAK\n" : "NIE\n");
	}

	return 0;
}