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
59
60
61
62
63
64
import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
 * 
 * Roman (Riomus) Bartusiak (riomus@gmail.com http://riomus.github.io)
 * 
 **/
public class ilo {

	private static final String NIE = "NIE";
	private static final String TAK = "TAK";

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int count = Integer.parseInt(br.readLine());
		int[] numbers = new int[count];
		int index = 0;
		while (index < count) {
			numbers[index] = Integer.parseInt(br.readLine());
			index++;
		}

		for (int i : numbers) {
			if (checkIfProductOfTwoFibbonaci(i)) {
				System.out.println(TAK);
			} else {
				System.out.println(NIE);
			}
		}

	}

	private static boolean checkIfProductOfTwoFibbonaci(int i) {
		int[] fibbonaci = getFibonaciNumbersSmallerOf(i);
		for (int j : fibbonaci) {
			for (int k : fibbonaci) {
				if ((j * k) == i)
					return true;
			}
		}
		return false;
	}

	private static int[] getFibonaciNumbersSmallerOf(int i) {
		int[] numbers = new int[46];
		int first = 0;
		int second = 1;
		numbers[0] = 0;
		int index = 0;
		while (numbers[index] < i) {
			index++;
			numbers[index] = first + second;
			first = numbers[index - 1];
			second = numbers[index];
		}

		return numbers;

	}

}