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

vector <int> fib;

int main()
{
	bool czy;
	int t, a, p;
	fib.push_back(1);
	fib.push_back(1);
	while( fib.back() < 1000000000 )
		fib.push_back( fib.back() +  fib[ fib.size()-2 ] );
//	printf("%zu\n", fib.size() );
	scanf("%d",&t);
	while( t-- )
	{
		czy=0;
		scanf("%d",&a);
		if (a==0) czy=1;
		p=0;
		for (int i=fib.size()-1;i>=p && czy==0 ;i--)
		{
			while( p<fib.size() && fib[p]*(long long)fib[i] < a ) p++;
			if (fib[p]*(long long)fib[i] == a) czy=1;
		}
		printf("%s\n", czy? "TAK":"NIE");
	}
	return 0;
}