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
//Autor: Mateusz Wasylkiewicz
//Zawody: Potyczki Algorytmiczne 2014
//Strona: http://potyczki.mimuw.edu.pl/
//Zadanie: Iloczyn, runda probna
//Czas: O(log^3(n)+t*log(log(n)))
#include <iostream>
#include <set>
using namespace std;

typedef long long LL;
#define REP(x, n) for (LL x = 0; x < (n); x++)
#define FOR(x, a, b) for (LL x = (a); x <= (b); x++)

const LL MAX = 1000000010, K = 46; //K - ilosc liczb Fibonacciego mniejszych
		//od MAX
set<LL> zbior; //zbior liczb, ktore sa iloczynem dwoch liczb Fibonacciego
		//mniejszych od MAX

void wypelnij_zbior()
{
	LL f[K]; //f[i] - i-ta liczba Fibonacciego
	REP(i, 2)
		f[i] = i;
	FOR(i, 2, K-1)
		f[i] = f[i-1] + f[i-2];
	
	REP(i, K)
		REP(j, K)
			zbior.insert(f[i] * f[j]);
}

bool zrob_test()
{
	LL n;
	cin >> n;
	return zbior.find(n) != zbior.end();
}

int main()
{
	ios_base::sync_with_stdio(0);
	wypelnij_zbior();
	LL t;
	cin >> t;
	while (t--)
		cout << (zrob_test() ? "TAK\n" : "NIE\n");
	return 0;
}