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

public class ilo {

    private static int positionBefore(long num, long[] fib) {
        int i = fib.length - 1;
        while (num < fib[i]) {
            i--;
        }
        return i;
    }

    private static boolean isFibProduct(long num, long[] fib) {
        int divisor = 0;

        int pos = positionBefore(num, fib);

        for (int i = pos; i >= 0; i--) {
            if (num % fib[pos] == 0) {
                num /= fib[pos];
                pos = i = positionBefore(num, fib);
                divisor++;
            } else {
                pos--;
            }

            if (divisor == 2 && num == 1) {
                return true;
            }

            if (divisor > 2) {
                break;
            }
        }
        return false;
    }

    public static void prodcut() {
        long[] fib = { 0, 1, 1, 2, 3, 5, 8, 13, 21, //8 index
                34, 55, 89, 144, 233, 377, 610,
                987, 1597, 2584, 4181, 6765, 10946,
                17711, 28657, 46368, 75025, 121393,
                196418, 317811, 514229, 832040,
                1346269, 2178309, 3524578, 5702887,
                9227465, 14930352, 24157817, 39088169,
                63245986, 102334155, 165580141, 267914296,
                433494437, 701408733 };

        Scanner scanner = new Scanner(System.in);
        int testCases = scanner.nextInt();

        for (int i = 0; i < testCases; i++) {
            long num = scanner.nextLong();
            System.out.println((isFibProduct(num, fib) ? "TAK" : "NIE"));
        }
    }

    public static void main(String... args) {
        prodcut();
    }
}