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
#include <cstdio>
#include <set>
using namespace std;

const int K=45;
const int MAXN=1000000000;

int f[K]={0,1};

int main() {
   int i,j,n,t;

   for (int i=2; i<K; i++)
     f[i]=f[i-1]+f[i-2];

   set<int> S;

   S.insert(0);

   for (i=1;i<K; i++)
     for (j=1;j<K && f[j]<=MAXN/f[i]; j++)
        S.insert(f[i]*f[j]);

    scanf("%d",&t);

    while (t--) {
        scanf("%d",&n);
        puts(S.find(n)!=S.end() ? "TAK":"NIE");
    }

    return 0;
}