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
#include <cstdio>
#include <set>
#include <list>

using namespace std;

const int maximum = 1000000000;

int main() {
  set<int> yes_set;
  list<int> fibs;
  int a, b, c;
  fibs.push_back(1);
  a = 1;
  b = 1;
  while (b <= maximum) {
    c = a + b;
    fibs.push_back(c);
    a = b;
    b = c;
  }

  for (list<int>::iterator f1 = fibs.begin(); f1 != fibs.end(); f1++) {
    for (list<int>::iterator f2 = fibs.begin(); f2 != fibs.end(); f2++) {
      if ((long long)(*f1) * (*f2) < (long long)1 << 32)
        yes_set.insert((*f1) * (*f2));
    }
  }

  scanf("%d", &a);
  while (a--) {
    scanf("%d", &b); 
    printf(yes_set.find(b) != yes_set.end() ? "TAK\n" : "NIE\n");
  }

}