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
#include <iostream>
#include <vector>
using namespace std;
#define VAR(i,n) __typeof(n) i=(n)
#define FOREACH(i,n) for(VAR(i,(n).begin());i!=(n).end();i++)
#define REP(i,n) for(int i=0;i<n;i++)
#define SIZE(n) (int)(n).size()
#define PB push_back
#define MP make_pair
#define ST first
#define ND second
const int M1=10000,INF=1000000000;
int tfib[M1],m=-INF,t,a[11],rozm;
void main2()
{
	cin>>t;
	REP(i,t)
	{
		cin>>a[i];
		m=max(m,a[i]);
	}
	tfib[0]=0;
	tfib[1]=1;
	for(int i=2;;i++)
	{
		tfib[i]=tfib[i-1]+tfib[i-2];
		if (tfib[i]>m){rozm=i+1;break;}
	}
	REP(i2,t)
	{
		if (a[i2]==0)
		{
			cout<<"TAK"<<endl;
			goto kon;
		}
		for(int i=1;;i++)
		{
			int k=tfib[i];
			int k2=a[i2]/k;
			if (k*k>a[i2] || k2*k!=a[i2])
			{
				cout<<"NIE"<<endl;
				break;
			}
			pair<int,int>prz=MP(0,rozm-1);
			while(prz.ST!=prz.ND+1)
			{
				int mid=(prz.ST+prz.ND)/2;
				if (tfib[mid]==k2)
				{
					cout<<"TAK"<<endl;
					goto kon;
				}
				if (tfib[mid]>k2)
					prz=MP(prz.ST,mid-1);
				else prz=MP(mid+1,prz.ND);
			}
		}
		kon:;
	}
}
int main()
{
	ios_base::sync_with_stdio(0);
	main2();
}