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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
public class ilo
{
	public static void main (String[] args) throws java.lang.Exception
	{
		try {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line;
		StringBuilder sb = new StringBuilder();
		int T;
		line = br.readLine();
		T = Integer.parseInt(line);
		for(;T>0;T--){
			line = br.readLine();
			long n = Long.parseLong(line);
			if(isFib(n))
			sb.append("TAK");
			else {
				boolean isFib = false;
				for(long i=2;i*i<=n;i++)
				if( (n%i)==0){
					if(isFib(i) && isFib(n/i)){
						isFib = true;
						break;
					}
					
				}
				if(isFib)
					sb.append("TAK");
				else
					sb.append("NIE");
				
			}
			if(T>1)
				sb.append("\n");
		}
		System.out.print(sb);
		} catch (Exception e) {
			System.out.println(e.getMessage());
			e.printStackTrace(System.out);
		}
	}
	
	private static boolean isFib(long n) {
		long tmp = 5*n*n;
		return isSqr(tmp-4)||isSqr(tmp + 4);
	}
	private static boolean isSqr(long n){
		long sqrt = (long)Math.sqrt((double) n);
		return sqrt*sqrt == n;
	}
}