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

/**
 * Created by Krzysztof Kornakiewicz on 07/05/14.
 * krzysztof.kornakiewicz@gmail.com
 */


public class ilo {
    private static Set<Integer> generateFibbonacci(int max) {
        HashSet<Integer> set = new HashSet<Integer>();
        int a = 1;
        int b = 1;
        int temp = 0;
        set.add(1);
        while (b < max) {
            temp = a;
            a = b;
            b = temp;
            b += a;
            set.add(b);
        }
        return set;

    }

    public static void main(String args[]) {
        Set<Integer> set = generateFibbonacci(1000000000);
        int n, x;
        double y;
        boolean flag = false;
        Scanner s = new Scanner(System.in);
        n = s.nextInt();
        while (n-- > 0) {
            flag = false;
            x = s.nextInt();
            for (int i : set) {
                y = ((double)x/i);
                if (set.contains((int) y) && y == Math.floor(y)) {
                    flag = true;
                    System.out.println("TAK");
                    break;
                }
            }
            if (!flag) {
                System.out.println("NIE");
            }
        }
    }
}