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
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;


public class ilo {

	public static void main(String[] args)
	{
		try{
			int[] fiboNumbers = new int[43];
			fiboNumbers[0] = 1;
			fiboNumbers[1] = 2;
			for(int i=2; i<43; i++){
				fiboNumbers[i] = fiboNumbers[i-1] + fiboNumbers[i-2];
			}
			
			BufferedReader buffReader = new BufferedReader(new InputStreamReader(System.in));
			int t = Integer.parseInt(buffReader.readLine());
			for(int i=0; i<t; i++){
				int n = Integer.parseInt(buffReader.readLine());
				if(n>1){
					int fiboTest = -1;
					int j = 0;
					while(fiboTest<0 && j<43){
						int m = n/fiboNumbers[j];
						if(m*fiboNumbers[j] == n)
							fiboTest = Arrays.binarySearch(fiboNumbers, m);
						j++;
					}
					if(fiboTest >= 0)
						System.out.println("TAK");
					else
						System.out.println("NIE");
				}else{
					System.out.println("TAK");
				}
			}
		}catch(Exception e){
			e.printStackTrace();
		}
	}
	
}