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

bool check( int x )
{
	std::vector<int> fib;
	fib.push_back( 0 );
	fib.push_back( 1 );
	do {
		const int k = fib.back() + fib[fib.size() - 2];
		fib.push_back( k );
		for ( std::vector<int>::const_iterator i = fib.begin(); i != fib.end(); ++i )
			if ( k * *i == x )
				return true;
			//else
			//	std::cout << "# " << k << " * " << *i << " != " << x << std::endl;
	} while ( fib.back() < x );
	return false;
}

int main()
{
	int n, x;
	std::cin >> n;
	for ( int i = 0; i < n; ++i ) {
		std::cin >> x;
		std::cout << ( check( x ) ? "TAK" : "NIE" ) << std::endl;
	}
	return 0;
}