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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<stdio.h>
#include<stdlib.h>

// Helper definition
#define VAR(v, i) __typeof(i) v=(i)
#define FOR(i, j, k) for (int i = (j); i <= (k); ++i)
#define FORD(i, j, k)for (int i=(j); i >= (k); --i)
#define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define REP(i, n) for(int i = 0;i <(n); ++i)

#define SIZE_FIB 44 // last number 701 408 733
#define SIZE 10

#define T "TAK"
#define F "NIE"

/** Return array of Fibonacci sequence
* @param n size sequence 1..n
* @param tab array of next number of Fubonacci from tab[0] = f1, to tab[n-1] = fn
*/
void fib(int n,unsigned int tab[])
{
	tab[0] = 1;
	tab[1] = 1;

	FOR(i, 2, n - 1)
	{
		tab[i] = tab[i - 1] + tab[i - 2];
	}
}

bool binary_search(unsigned int val, int begin,int end, unsigned int tab[])
{
	if (begin > end) return false;
	int div = (begin + end) / 2;

	if (tab[div] == val)
		return true;
	if (tab[div] < val)
		return binary_search(val, div + 1, end, tab);
	else 
		return binary_search(val, begin, div - 1, tab);
}

int main(int argc, char **argv)
{
	unsigned int fib_array[SIZE_FIB];
	bool out;
	unsigned int ilo;
	int row;
	
	fib(SIZE_FIB, fib_array);
	scanf("%d", &row);
	
	REP(i, row)
	{
		out = false;
		scanf("%d", &ilo);
		FORD(j, SIZE_FIB - 1, 2)
		{
			if ( ilo % fib_array[j] == 0 && binary_search(ilo/fib_array[j], 0, SIZE_FIB, fib_array))
			{
				out = true;
				break;
			}
		}
		if (out)
			printf("%s\n", T);
		else 	
			printf("%s\n", F);
	}

	return 0;
}