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
// ilo02.cpp

#include <cstdio>
#include <iostream>
using namespace std;

#define N 46

int f[N];

int main()
{
  f[0]=0;
  f[1]=1;
  for(int i=2; i<N; i++ ) f[i]=f[i-1]+f[i-2];
  
  int t,n,a,b,x,y;
  cin >> t;
  for(int i=0; i<t; i++)
  {
     cin >> n;
     if(!n){printf("TAK\n");continue;}
  
     for( a=0, b=N-1;++a<N;)
     {
       x=f[a];
       y=n/x;
       if (y<x) { y=0; break; }
       if (x*y==n)
       {
         while (y<f[b]) b--;
         if (y==f[b]) break;
       }
     }
     if (y) printf("TAK\n"); else printf("NIE\n");
  }
}