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

using namespace std;

const string YES = "TAK";
const string NO = "NIE";

const int MAXT = 10;
const int MAXN = (int)1e9;
const int F_LENGTH = 45;

int f[F_LENGTH] = {0,1,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::sync_with_stdio ( false );

    int t;
    cin >> t;

    for ( int testcase = 0; testcase < t; ++testcase ){
        int n;
        cin >> n;
        if ( n == 0 ){
            cout << YES << endl;
            continue;
        }
        bool found = false;
        for ( int i = 1; !found && i < F_LENGTH; ++i ){
            if ( n % f[i] == 0 && *lower_bound ( f, f+F_LENGTH, n / f[i] ) == n / f[i] ){
                found = true;
            }
        }
        cout << ( found ? YES : NO ) << endl;
    }

    return 0;
}