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

using namespace std;

int tab[44]={0,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};


int main(){
    ios_base::sync_with_stdio(0);
    int n;
    cin>>n;
    int x;
    int j,co;
    bool czy=false;
    for(int i=0;i<n;i++){
        czy=false;
        j=1; co=0;
        cin>>x;
        if(x==0){
            cout<<"TAK"; if(i!=n-1) cout<<endl;}
        else{
            while(j<=ceil(sqrt(x))){
                if(x%j==0&&binary_search(tab,tab+44,(x/j))==true){
                    cout<<"TAK"; czy=true; if(i!=n-1) cout<<endl; break;
                }
                co++;
                j=tab[co];
            }
            if(!czy){
                cout<<"NIE"; if(i!=n-1) cout<<endl;
            }
        }
    }
    return 0;
}