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
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <strings.h>

#define tabSize sizeof(buff)/sizeof(int)


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

bool ilo(unsigned int n) {
    
    int i,j,index = 2;
    if(n == 0 || n == 1)return true;
    while((index != tabSize) && (buff[index] <= n))index++;
    for(i = 0; i < index - 1; i++) {
        if(buff[i] == n)return true;
        for(j=i; j < index; j++) {
            if(buff[i] * buff[j] == n)return true;
        }
    }
    return false;
}

int main() {
    int t,n,i;
    scanf("%d",&t);
    for(i = 0; i < t; i++) {
        scanf("%d",&n);
        printf(ilo(n) ? "TAK\n" : "NIE\n");
    }
    return (0);
}