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
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(int argc, char *argv[]){
	int t;
	const int fmax = 50;
	int f[fmax];
	int fn,k,m, ni;
	long long tmpk, tmp;

	f[0] = 1;
	f[1] = 2;
	for (fn=2; fn<fmax; fn++) {
	    f[fn] = f[fn-1] + f[fn-2];
	    if (f[fn] > 1000000000)
		break;
	}
	
	scanf( "%d", &t );
	while (t--) {
		tmp = 0;
		scanf( "%d", &ni );
		for (k=0; k<fn; k++){
		    tmpk = f[k];
		    if (tmpk > ni)
			break;
		    for (m=k; m<fn; m++){
			tmp = tmpk * f[m];
			if (tmp >= ni)
			    break;
		    }
		    if (tmp == ni)
			break;
		}
		if (tmp==ni)
		    printf("TAK\n");
		else
		    printf("NIE\n");
	}
	return 0;
}