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
#include <iostream>

using namespace std;

int tab[]={1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,165580141,267914296,433494437,701408733};

bool spr(int l)
{
        int z=42;
        for(int i=0;i<43;i++)
        {

            if(i>z)return 0;
            if(l%tab[i]==0);
                for(z=z;z>=i;z--)
                {
                    if(tab[i]*tab[z]<l)break;
                    if(tab[i]*tab[z]==l){return 1;}
                }
        }
        return 0;

}
int main()
{
    int t,l,z;
    cin >> t;
    while(t--)
    {
        cin >>l;
        if(l==0)cout << "TAk \n";
        else if(spr(l))cout<<"TAK \n";
        else cout << "NIE \n";
    }
    return 0;
}