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;
import static java.lang.Math.*;

class Main {

	final static double PHI = (1 + sqrt(5)) / 2;
	final static double PSI = (1 - sqrt(5) / 2);
	final static double LN_PHI = log(PHI);

	public static int fibo(double n) {
		return (int) round((1 / sqrt(5) * (pow(PHI, n) - pow(PSI, n))));
	}

	public static void main(String args[]) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		for (int i = 0; i < n; i++) {
			double x = in.nextInt();
			double k = floor(0.5 + log(5 * x) / LN_PHI);
			double y = 5 * x - pow(PHI, k);
			double d = floor(0.5 + log(abs(y)) / LN_PHI);
			double kd = k + d;
			double en = (k + d) / 2;
			double em = (k - d) / 2;

			if (x == fibo(k)) {
				System.out.println("TAK");
			} else if (x == pow(fibo(k / 2), 2)) {
				System.out.println("TAK");
			} else if (x == fibo(k) + 1 || x == fibo(k) - 1) {
				System.out.println("TAK");
			} else if (kd % 2 == 0)
				System.out.println("TAK");
			else
				System.out.println("NIE");

		}
	}
}