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
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAXN = 1000000000;
const int SQRT_MAXN = sqrt((double) MAXN) + 1;

vector<int> fib;

int main() {
  fib.push_back(0);
  fib.push_back(1);
  while(fib.back() < MAXN)
    fib.push_back( fib.back() + fib[fib.size()-2] );

  int t;
  cin >> t;
  for(int it = 0; it < t; it++) {
    int n;
    cin >> n;
    bool res = false;
    for(int i = 1; fib[i] <= SQRT_MAXN && !res; i++)
      if(n % fib[i] == 0 && binary_search(fib.begin(), fib.end(), n / fib[i]))
        res = true;
    if(res)
       cout << "TAK\n";
    else
       cout << "NIE\n";

  }

  return 0;
}