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
92
#include <stdio.h>

#define ARRAY_SIZE(a) (sizeof(a)/sizeof(a[0]))

int fibo[] = {
  1, /* 0 */
  2, /* 1 */
  3, /* 2 */
  5, /* 3 */
  8, /* 4 */
  13, /* 5 */
  21, /* 6 */
  34, /* 7 */
  55, /* 8 */
  89, /* 9 */
  144, /* 10 */
  233, /* 11 */
  377, /* 12 */
  610, /* 13 */
  987, /* 14 */
  1597, /* 15 */
  2584, /* 16 */
  4181, /* 17 */
  6765, /* 18 */
  10946, /* 19 */
  17711, /* 20 */
  28657, /* 21 */
  46368, /* 22 */
  75025, /* 23 */
  121393, /* 24 */
  196418, /* 25 */
  317811, /* 26 */
  514229, /* 27 */
  832040, /* 28 */
  1346269, /* 29 */
  2178309, /* 30 */
  3524578, /* 31 */
  5702887, /* 32 */
  9227465, /* 33 */
  14930352, /* 34 */
  24157817, /* 35 */
  39088169, /* 36 */
  63245986, /* 37 */
  102334155, /* 38 */
  165580141, /* 39 */
  267914296, /* 40 */
  433494437, /* 41 */
  701408733, /* 42 */
};

int is_fibo(int k)
{
  int i;
  
  for(i = 0; i < ARRAY_SIZE(fibo); i++)
  {
    if(fibo[i] == k) return 1;
    if(fibo[i] > k) break;
  }
  return 0;
}

int calc(int k)
{
  int i, p, f;
  
  for(i = 0; i < ARRAY_SIZE(fibo); i++)
  {
    f = fibo[i];
    
    if(k % f == 0)
    {
      p = k / f;
      if(is_fibo(p)) return 1;
    }
  }
  return 0;
}

int main()
{
  int n, k;
  
  scanf("%d", &n);
  while(n-- > 0)
  {
    scanf("%d", &k);
    printf("%s\n", calc(k) ? "TAK" : "NIE");
  }
  
  return 0;
}