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
import java.util.Scanner;

public class ilo {

	public static void main(String[] args) {
		long a = 1, b = 2, max = 1000000000;
		int count = 0, pos = 44, len = 485;
		long[] arr = new long[len];
		arr[0] = 0;
		while (a < max) {
			arr[++count] = a;
			for (int i = 2; i <= count; i++) {
				long ilo = arr[i] * a;
				if (ilo < max) {
					arr[pos++] = (long)(ilo);
				}
			}
			b += a;
			a = b - a;
		}
		Scanner sc = new Scanner(System.in);
		int inSize = sc.nextInt();
		String[] result = new String[inSize];
		scanner:
		for (int i = 0; i < inSize; i++) {
			long x = sc.nextLong();
			for (int j = 0; j < len; j++) {
				if (x == arr[j]) {
					result[i] = "TAK";
					continue scanner;
				}
			}
			result[i] = "NIE";
		}
		sc.close();
		for (String res : result) 
			System.out.println(res);
	}
}