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
41
42
43
44
45
46
47
48
#ifdef _MSC_VER
  #ifndef __GNUC__
    #pragma warning(disable: 4996)
  #endif
  #define main main0
#endif
#include <iostream>
using namespace std;

//const int FibMax = 1000000000;
const int N = 44;

int main() {
  ios_base::sync_with_stdio(0);

  int fibonacci[N] = {1, 2, 3};
  for(int i = 3; i < N; ++i)
    fibonacci[i] = fibonacci[i-2] + fibonacci[i-1];

  int t;
  cin >> t;
  do {
    int product;
    cin >> product;
    if(product < 4)
      cout << "TAK\n";
    else {
      int index = N;
      while(fibonacci[--index] > product)
        ;
      for(; index > 0; --index) {
        if(product % fibonacci[index] != 0)
          continue;
        int divisor = product / fibonacci[index];
        int i = index;
        while(fibonacci[i] > divisor)
          --i;
        if(fibonacci[i] == divisor) {
          cout << "TAK\n";
          break;
        }
      }
      if(index <= 0)
        cout << "NIE\n";
    }
  }while(--t > 0);
  return 0;
}