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
import java.io.BufferedInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.LinkedHashSet;
import java.util.Set;

public class ilo {
    private static final InputStream in = new BufferedInputStream(System.in);
    private static int readInt() {
        try {
            int ret = 0, b;
            while ((b = in.read()) != -1) if (b != ' ' && b != '\r' && b != '\n') break;
            do {
                if (b < '0' || b > '9') break;
                ret = ret * 10 + (b - '0');
            } while ((b = in.read()) != -1);
            return ret;
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }
    private static final Set<Integer> fibs = new LinkedHashSet<>();

    public static void main(String[] args) {
        int fib1 = 0, fib2 = 1, fib;
        do {
            fibs.add(fib = fib1 + fib2);
            fib1 = fib2; fib2 = fib;
        } while (fib <= 1000000000);

        int t = readInt();
        for (int i = 0; i < t; ++i) {
            int n = readInt();
            String ans = "NIE";
            for (Integer f : fibs) {
                if (n % f == 0 && fibs.contains(n / f)) {
                    ans = "TAK";
                    break;
                }
            }
            System.out.println(ans);
        }
    }
}