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

public class ilo{
	static ArrayList<Integer> fibb;
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		fibb = new ArrayList<Integer>();
		int t;
		int number;
		generateFibbonacci();
		/*for(int el : fibb){
			System.out.println(el);
		}*/
		t = input.nextInt();
		while(t-- > 0){
			number = input.nextInt();
			System.out.println(checkNumber(number)?"TAK":"NIE");
		}
	}
	private static void generateFibbonacci(){
		fibb.add(1);
		fibb.add(2);
		int next = 3;
		int i = 2; // index of current element
		while(next < 1000000001){
			fibb.add(next);
			next = fibb.get(i) + fibb.get(i-1);
			i++;
		}
	}
	private static boolean checkNumber(int number){
		int count = 0;
		ArrayList<Integer> divisors = new ArrayList<Integer>();
		for(int i = fibb.size() - 1; i >= 0; i--){
			if(number % fibb.get(i) == 0){
				count++;
				number /= fibb.get(i); 
				divisors.add(fibb.get(i));
				i++;
			}
			if(count == 2)
				break;
		}
		return (count == 2 && number==1)? true:false;
	}
}