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
program ilo;

var
  m: byte;
  n: longword;
  f: longword;
  d: longword;
  a: array[1..42] of longword;
  i,j,k: byte;
  OK: boolean;

begin
  readln(m);

  a[1]:=2; a[2]:=3; j:=2;
  while (a[j]+a[j-1]) <=1000000000 do
  begin
    a[j+1]:=a[j]+a[j-1];
    j:=j+1
  end;

  for i:=1 to m do
  begin
    readln(n);
    if n<7 then writeln('TAK')
      else
      begin
        j:=1; OK:=false; f:=2;
        repeat
          if (n mod f)=0 then
          begin
	    k:=j; d:=n div f;
	    repeat
	      if (d=f) or (d=1) then OK:=true
	      else if d>f then
	      begin
		k:=k+1; f:=a[k];
              end
	    until (d<f) or OK
          end
          else
          begin
            j:=j+1; f:=a[j];
          end
        until (n<f) or OK;
        if OK then writeln('TAK') else writeln('NIE');
      end;
  end;
end.