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

/**
 * Created by Adam Dziedzic on 09.05.14.
 */
public class ilo {
    public static double pow(double num, int exponent)
    {
        double result = 1;
        double multiplier = num;

        while (exponent != 0) {
            if ((exponent & 1) == 1) {
                result *= multiplier;
            }
            if ((exponent >>>= 1) != 0) {
                multiplier *= multiplier;
            }
        }

        return result;
    }
    public static int fibo(int i) {
        return (int) Math.round(1 / Math.sqrt(5) * (pow(((1 + Math.sqrt(5)) / 2), i) - pow(((1 - Math.sqrt(5)) / 2), i)));
    }
    public static void main(String [] args)
    {
        Scanner in = new Scanner(System.in);
        //int n = Integer.parseInt(in.nextLine());
        int n = in.nextInt();
        for(int i=0;i<n;i++) {
            int ni = in.nextInt();
            if(ni < 7) {
                System.out.println("TAK");
                continue;
            }
            double pierwiastek = (int)Math.sqrt(n);
            pierwiastek = pierwiastek * Math.sqrt(5);
            double fi = (1+Math.sqrt(5))/2;
            int iter1 = (int)(Math.log(pierwiastek)/Math.log(fi))+2;
            int iter2 = iter1-2;
            int itermax = (int)(Math.log(n)/Math.log(fi))+1;
            String wynik = "NIE";
            while(true)
            {
                int ilo = fibo(iter1)*fibo(iter2);
                if(ilo == n) {
                    wynik = "TAK";
                    break;
                }
                if(ilo < n) {
                    if(iter2 == itermax  + 2) break;
                    iter2++;
                }
                else {
                    iter1--;
                    if(iter1 == 1) break;
                }
            }
            System.out.println(wynik);
        }
    }
}