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
#include <iostream>

using namespace std;

int main(void)
{
	unsigned int t, n, f11, f12, f1, f21, f22, f2;
	for (cin >> t; t > 0; --t)
	{
		cin >> n;
		if (n < 4) cout << "TAK" << endl;
		else
		{
			f11 = 0; f12 = 1; f1 = 1;
			f21 = 0; f22 = 1; f2 = 1;
			while (f1 * f2 < n)
			{
				while (f1 * f2 < n)
				{
					f21 = f22;
					f22 = f2;
					f2 += f21;
				}
				if (f1 * f2 == n) break;
				f11 = f12;
				f12 = f1;
				f1 += f11;
				f21 = 0; f22 = 1; f2 = 1;
			}
			cout << (f1 * f2 == n ? "TAK" : "NIE") << endl;
		}
	}
}