#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
int main()
{
    int liczba_testow;
    int hehe = 2;
    bool warunek = false;
    int rozmiar;
    int liczba;
    int an;
    cin>>liczba_testow;
    vector <int>fib;
    vector<int>dane;
    vector<int>wyniki;
    int cos;
    int temp;
    for(int q=0;q<liczba_testow;q++)
    {
        cin>>temp;
        dane.push_back(temp);
    }

    int a0 = 0,a1 = 1;
for(int e= 0;e<liczba_testow;e++)
{


    fib.push_back(a0);          //dodanie dwóch pierwszych elementów do wektora
    fib.push_back(a1);
    liczba = dane[e];                 //wczytanie liczby do testów


   // int pier = (int)sqrt(liczba)+1;
    for(int i = 2;i<44;i++)
    {
     an = fib[i-2]+fib[i-1];
     fib.push_back(an);
    }
    for(int i=0;i<44;i++)
    {
        for(int y = 0;y<44;y++)
        {
            cos = fib[i]*fib[y];
            wyniki.push_back(cos);
        }
    }
    for(int q = 0;q<wyniki.size();q++)
    {
        if(wyniki[q]==liczba)
        warunek = true;

    }
    if(warunek==true)
        cout<<"TAK"<<endl;
        else
        cout<<"NIE"<<endl;
        fib.clear();
    warunek = false;
}
}                                                 //wczytywanie ciągu