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
113
114
115
116
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class ilo
{
   static List<Integer> fibb = new ArrayList<Integer>(50);
   private static int maxValue;
   private static int prevValue;

   static
   {
      prevValue = 0;
      maxValue = 1;

      fibb.add(prevValue);
      fibb.add(maxValue);
   }

   private static void ensureComputedUpTo(int number)
   {
      int newValue;
      while (maxValue < number)
      {
         newValue = prevValue + maxValue;
         fibb.add( newValue );

         prevValue = maxValue;
         maxValue = newValue;
      }
   }

   private static boolean canFactorize(int n)
   {
      if (n == 0)
         return true;

      ensureComputedUpTo(n);

      int stopAt = (int) Math.floor(Math.sqrt(n));

      for (int i = 1; fibb.get(i) <= stopAt; i++)
      {
         if ( n % fibb.get(i) == 0)
         {
            if (Collections.binarySearch(fibb, n / fibb.get(i)) > 0)
               return true;
         }
      }

      return false;
   }

   public static void main(String[] args)
   {
//      canFactorize(1000*1000*1000);    // 46 values in 17 ms
      Scanner scanner = new Scanner(System.in);

      int numberOfTests = scanner.nextInt();
      for (int i = 0; i < numberOfTests; i++)
      {
         int n = scanner.nextInt();
         System.out.println( canFactorize(n) ? "TAK" : "NIE" );
      }
   }

   /*
   1
   2
   3
   5
   8
   13
   21
   34
   55
   89
   144
   233
   377
   610
   987
   1597
   2584
   4181
   6765
   10946
   17711
   28657
   46368
   75025
   121393
   196418
   317811
   514229
   832040
   1346269
   2178309
   3524578
   5702887
   9227465
   14930352
   24157817
   39088169
   63245986
   102334155
   165580141
   267914296
   433494437
   701408733
   1_134_903_170
   time: 15
   46
    */
}