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
// Krzysztof Piesiewicz
// Iloczyn PA 2014
#include <cstdio>
using namespace std;

const int MAX_K = 31;

int t, k = 24, n, f[ MAX_K ];
bool res;

int main() {
	f[ 1 ] = 1;
	for( int i = 2; i < k; i++ )
		f[ i ] = f[ i - 1 ] + f[ i - 2 ];
	
	scanf( "%d", &t );
	while( t > 0 ) {
		scanf( "%d", &n );
		res = false;
		for( int i = 0; i < k; i++ )
			for( int j = 0; j < k; j++ )
				if( f[ i ] * f[ j ] == n ) {
					res = true;
					break;
				}
		if( res )
			printf( "TAK\n" );
		else
			printf( "NIE\n" );
		t--;
	}
	return 0;
}