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
#include <iostream>
#include <set>
#include <vector>

using namespace std;

const long long kMaxN = 1000000000;

set<long long> products;

void Init() {
  vector<long long> f;
  long long a = 0;
  long long b = 1;
  f.push_back(a);
  while (b <= kMaxN) {
    f.push_back(b);
    long long c = a + b;
    a = b;
    b = c;
  }
  for (int i = 0; i < f.size(); ++i) for (int j = 0; j <= i; ++j) products.insert(f[i] * f[j]);
}

void Solve() {
  int n;
  cin >> n;
  cout << (products.find(n) == products.end() ? "NIE" : "TAK") << endl;
}

int main() {
  Init();
  int t;
  cin >> t;
  while (t--) Solve();
  return 0;
}