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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
//Grzegorz Pstrucha

#include <algorithm>
#include <cassert>
#include <cstdio>
#include <functional>
#include <iostream>
#include <sstream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <math.h>

#define ASSERT_ for (;;) {}
#define PII pair<int, int>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<string> vs;

#define REP(i,n)    for(int i=0; i<(n); ++i)
#define FOR(i,p,k)  for(typeof(p) i=(p); i<=(k); ++i)
#define FORD(i,p,k) for(typeof(p) i=(p); i>=(k); --i)

#define MAX_FIBO 50

vll fibonacci_numbers;

void preprocess() {
  fibonacci_numbers.push_back(0);
  fibonacci_numbers.push_back(1);
  ll fibo;
  REP(i,MAX_FIBO - 2) {
    fibo = fibonacci_numbers.back() + (*----fibonacci_numbers.end());
    fibonacci_numbers.push_back(fibo);
  }
}

void solve(ll n) {
  vll smaller_numbers;
  FOR(i, 1, MAX_FIBO) {
    if (fibonacci_numbers[i] <= n) {
      smaller_numbers.push_back(fibonacci_numbers[i]);
    } else {
      break;
    }
  }

  // Wektor par
  vector<pair<ll,ll> > pairs;
  REP(i, smaller_numbers.size()) {
    REP(j, smaller_numbers.size()) {
      pairs.push_back(make_pair(smaller_numbers[i], smaller_numbers[j]));
    }
  }

  REP(i, pairs.size()) {
    pair<ll,ll> fibo_pair = pairs[i];

    if (fibo_pair.first * fibo_pair.second == n) {
      printf("TAK\n");
      return;
    }
  }
  printf("NIE\n");
}

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

  preprocess();

  int t;
  scanf("%d", &t);
  REP(i,t) {
    ll n;
    scanf("%lld", &n);
    solve(n);
  }

  return 0;
}