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

public class ilo {
	
	private static final int[] fib = new int[46];
	
	static {
		fib[1] = 1;
		fib[2] = 1;
		for (int i = 3; i < 46; i++) {
			fib[i] = fib[i - 1] + fib[i - 2];
		}
	}
	
	public static void main(String[] args) {
		try (Scanner in = new Scanner(System.in)) {
			int cases = in.nextInt();
			while (cases-- > 0) {
				int input = in.nextInt();
				
				if (input < 7) {
					System.out.println("TAK");
					continue;
				}
				
				boolean confirmed = false;
				int i = 3;
				
				while (fib[i] < input) {
					if (input % fib[i] != 0) {
						i++;
						continue;
					}
					
					confirmed = isFib(input / fib[i++]);
					
					if (confirmed) {
						System.out.println("TAK");
						break;
					}
				}
				
				if (confirmed) {
					continue;
				}
				
				System.out.println("NIE");
			}
		}
	}
	
	private static boolean isFib(int number) {
		if (number < 4) {
			return true;
		}
		int i = 5;
		while (fib[i] <= number) {
			if (number == fib[i++]) {
				return true;
			}
		}
		return false;
	}
	
}