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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
program project1;

{$mode objfpc}{$H+}

uses
  {$IFDEF UNIX}{$IFDEF UseCThreads}
  cthreads,
  {$ENDIF}{$ENDIF}
  Classes
  { you can add units after this };


var
  fibo:array[1..43] of int64;
  multiple_fibo:array[1..947] of int64;


procedure create_fibo;
var
i:integer;
begin
fibo[1]:=1;
fibo[2]:=2;
for i:=3 to 43 do
   fibo[i]:=fibo[i-2]+fibo[i-1];
end;

procedure create_multiple_fibo;
var
i,j,k,c,n:integer;
plus,minus:boolean;
arr_temp:array[1..22] of int64;
begin
multiple_fibo[1]:=0;
n:=1;
c:=1;
n:=1;
plus:=false;
for i:=2 to 44 do      
   begin
   for j:=1 to c do
      arr_temp[j]:=fibo[i-j]*fibo[j];

   //sortowanie
   k:=1;
   while (k<=c) do
      begin
      inc(n);
      multiple_fibo[n]:=arr_temp[k];
      inc(k,2);
      end;
   dec(k,2);
   if (k<c) then
      inc(k)
   else
      dec(k);
   while (k>=1) do
      begin
      inc(n);
      multiple_fibo[n]:=arr_temp[k];
      dec(k,2);
      end;


   if plus then
      inc(c);
   plus:= not plus;
   end;

minus:=false;
dec(c);
for i:=1 to 43 do          
   begin
   for j:=1 to c do
      arr_temp[j]:=fibo[44-j]*fibo[i+j];

   //sortowanie
   if minus then
      k:=1
   else
      k:=2;
   while (k<=c) do
      begin
      inc(n);
      multiple_fibo[n]:=arr_temp[k];
      inc(k,2);
      end;
   dec(k,2);
   if (k<c) then
      inc(k)
   else
      dec(k);
   while (k>=1) do
      begin
      inc(n);
      multiple_fibo[n]:=arr_temp[k];
      dec(k,2);
      end;


   if minus then
      dec(c);
   minus:= not minus;
   end;

end;


function check_value(v:int64):boolean;
var
l, p, s: Integer;
finish:boolean;
begin
finish:=false;
l:=1;
p:=947;
while ((l<=p) and (not finish)) do
   begin
   s:=(l+p) div 2;
   if (v=multiple_fibo[s]) then
      finish:=true;
   if (v>multiple_fibo[s]) then
      l:=s+1
   else
      p:=s-1;
   end;
result:=finish;
end;

var
  count_in:integer;
  data_in:array[1..10] of int64;
  i:integer;

begin

  create_fibo;
  create_multiple_fibo;

  readln(count_in);
  for i:=1 to count_in do
     readln(data_in[i]);

  for i:=1 to count_in do
     begin
     if check_value(data_in[i]) then
        writeln('TAK')
     else
        writeln('NIE');
     end;

end.