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

public class ilo {
    
    // all Fibonacci numbers lower than 1 000 000 000
    private static Integer[] FIBS = new Integer[45];
    private static Set<Integer> FIBS_SET = new HashSet<Integer>(); 
    
    private static int generateNextFib(int fib0, int fib1){
        int res = fib0 + fib1;
        return res;
    }
    
    private static String hasFibFactors(int number){
        if(number == 0){
                return "TAK";
        }
        for(int x : FIBS_SET){
            if(number % x == 0 && FIBS_SET.contains(number/x)){
                return "TAK";
            }
        }
        return "NIE";
    }
    
    public static void main(String args[]){
                
        FIBS[0] = 0;
        FIBS[1] = 1;
        
        for(int i = 2; i < 45; i++){
            FIBS[i] = generateNextFib(FIBS[i-2], FIBS[i-1]);                        
        }
        
        Collections.addAll(FIBS_SET, FIBS);
        FIBS_SET.remove(0);
        
        Scanner scan = new Scanner(System.in);
        int tc = scan.nextInt();
        
        for(int t = 0; t < tc; t++){
            System.out.println(hasFibFactors(scan.nextInt()));
        }
    }
    
}