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

public class ilo {

	static int[] fib = new int[47];
	static Set<Integer> multi = new HashSet<Integer>();

	public static void main(String[] args) throws IOException {
		fib[0] = 0;
		fib[1] = 1;
		for (int i = 2; i < fib.length; i++) {
			fib[i] = fib[i - 2] + fib[i - 1];
		}
		multi.add(0);
		for (int i = 1; i < fib.length; i++) {
			for (int j = i; (long) fib[i] * fib[j] < 10000000; j++) {
				multi.add(fib[i] * fib[j]);
			}
		}

		BufferedReader reader = new BufferedReader(new InputStreamReader(
				System.in));
		int t = Integer.parseInt(reader.readLine().trim());
		while (t-- > 0) {
			int n = Integer.parseInt(reader.readLine().trim());
			System.out.println(multi.contains(n) ? "TAK" : "NIE");
		}
		reader.close();
	}
}