/*----------------------
Koniecko Łukasz - lukon
lukon10@wp.pl
----------------------*/
/*---------------------------------------- 
Potyczki Algorytmiczne 2014, runda próbna
Zadanie: ILO
Iloczyn 
-----------------------------------------*/

#include <iostream>
using namespace std;

/* Obliczanie n-tego wyrazu ciągu F. */
int fibonacci(int n){
	if(n==0) return 0;
	if(n==1) return 1;
	int f=0;
	int f1=0;
	int f2=1;
	for(int i=2; i <= n; i++){
		f = f1 + f2;
		f1 = f2;
		f2 = f;				
	}	
	return f;
}

/* Szukanie dwóch liczb z ciągu F., które są iloczynem licby n */
int iloczyn(int n){
	if(n==0 || n==1) return 0;
	
	int f = 0; //kolejne liczby z ciągu F.
	
	/* Jezeli liczba n >= 2 i jest liczbą z ciągu F. to ma dwa dzielniki -> TAK */
	int fk = 0; //ile liczb w ciagu
	for(int i=3; f<=n; i++){
		f = fibonacci(i);
		if(f == n) return 1;
		fk=i;
	}
	
	f = 0;
	/* Sprawdzanie, które liczby z ciągu F. są dzielnikami liczby n */
	int tab_dz[fk]; //tablica z dzielnikami liczby n
	int ld=0; // liczba dzielników
	for(int i=3; f <= n; i++){
		f = fibonacci(i);		
		if(n%f == 0) {
			tab_dz[ld] = f;			
			ld++;
		}
	}
	
	/* Sprawdzanie czy jest iloczyn dwóch liczb, który daje liczbę n */
	for(int i=0; i < ld; i++)
		for(int j=i; j < ld; j++){
			if(tab_dz[i]*tab_dz[j] == n) return 1;
		}
	
	return 0;
}

int main(){	
	int t; //liczba przypadków testowych	
	int n; //liczba do testu
	cin >> t;
	
	/* Sprawdzanie... */
	for(int i=0; i < t; i++){
		cin >> n;
		if(iloczyn(n)) 
			cout << "TAK" << endl;
		else 
			cout << "NIE" << endl;
	}
}