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

public class ilo {
    public static void main(String[] args) {
        Set mult = new HashSet();

        for (long i = 1; i < 47; i++)
            for (long j = 1; j < 47; j++) {
                mult.add(fib(i) * fib(j));

            }
        //System.out.println(mult);
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            long val = scanner.nextLong();
       //     System.out.println(val);
            if (mult.contains(val)) System.out.println("TAK");
            else System.out.println("NIE");
        }
    }

    static Map map = new HashMap();
    static long fib(long n) {
        if (n == 1 || n == 2) return 1;
        if (map.containsKey(n)) return (Long) map.get(n);
        long res= fib(n - 1) + fib(n - 2);
        map.put(n, res);
        return res;
    }

    private static boolean isIlo(int i) {
       return false;
    }
}