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

public class ilo {

	static ArrayList<Integer> list = getList();

	public static void main(String[] args) {
		Scanner scanIn = new Scanner(System.in);
		int size = Integer.parseInt(scanIn.nextLine());

		for (int i = 0; i < size; i++) {
			String result = solveIt(Integer.parseInt(scanIn.nextLine()));
			System.out.println(result);
		}
		scanIn.close();

	}

	private static ArrayList<Integer> getList() {
		ArrayList<Integer> result = new ArrayList<Integer>();
		result.add(1);
		result.add(1);
		int last = 1;
		for (int i = 2; last < Math.pow(10, 9); i++) {
			last = result.get(i - 1) + result.get(i - 2);
			result.add(last);

		}
		return result;
	}

	private static String solveIt(int number) {
		if (number == 0)
			return "TAK";

		for (int i : list) {
			int a = number / i;
			if (number % i != 0)
				continue;
			for (int j : list) {
				if (a % j == 0 && a/j == 1)
					return "TAK";
			}

		}
		return "NIE";

	}

}