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
45
46
47
48
49
50
51
52
53
54
55
56
57
#define NDEBUG
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <queue>
#include <string>
#include <vector>
using namespace std;
#define TRACE(x) cerr<<"# "#x<<endl;
#define DEBUG(x) cerr<<#x<<" = "<<(x)<<endl;
typedef unsigned long long ULL;
typedef long long LL;
const int INF = 0x7FFFFFFF;

int fib[] = {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};
const int fib_size = sizeof(fib)/sizeof(fib[0]);


int f(int x) {
	for(auto i:fib) {
		if(i == x)
			return 1;
	}

	return 0;
}


int main() {
	int t;
	scanf("%d", &t);

	for(int i=0; i<t; ++i) {
		int x,a,b,c=0;
		scanf("%d", &x);

		if(x <= fib[fib_size-1]) {
			for(int k=2; k<fib_size ;++k) {
				a = x / fib[k]; 
				if((a*fib[k]==x) && f(a)) {
					c=1;
					break;
				}
			}
		}
		printf((c)?"TAK\n":"NIE\n");
	}

	return 0;
}