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
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>


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

   while (mn < mx) {
      mid = (mx+mn)/2;
      if (x < a[mid]) {
         mx = mid;
      } else if (x > a[mid]) {
         mn = (mx+mn+1)/2;;
      } else {
         return mid;
      }
   }
   if (x == a[mn]) {
      return mn;
   } else {
      return -1;
   }
}




int main() {
   unsigned int *arr = init();

   char m;
   unsigned int x;

   unsigned int div;
   unsigned int mod;

   int t, i, j;
   scanf("%d", &t);
   for (i=0; i < t; i++) {
      scanf("%u", &x);
      if (in(x, arr, 44) >= 0) {
         printf("TAK\n");
      } else {
         for (j=44; j > 2; j--) {
            if (arr[j] > x) continue;
            div = x / arr[j];
            if (div <= 1) continue;
            mod = x % arr[j];
            if (mod > 0) continue;

            if (in(div, arr, j) >= 0) {
               printf("TAK\n");
               break;
            }
         }
         if (j == 2) printf("NIE\n");
      }
   }
   return 0;
}