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
program ilo(input,output);

  const
    maxar = 100;
    maxnum = 1000000000;

  var
    fibs : array[1..maxar] of longint;
    nf,i : integer;
    ninp : integer;
    inp,rest : longint;
    low,high : integer;

  function initfib : integer;

    var
      i : integer;

    begin
      fibs[1] := 1;
      fibs[2] := 2;
      i := 2;
      while (fibs[i] < maxnum) do
        begin
          i:=i+1;
          fibs[i] := fibs[i-2] + fibs[i-1];
        end;
      initfib := i-1;
    end;

begin
  nf := initfib;
  readln(ninp);

  for i:= 1 to ninp do
    begin
      readln(inp);

      if inp=0 then
        begin
          writeln('TAK');
          continue
        end;

	  high := nf;
      while (fibs[high] > inp) do
        high := high-1;

	  low := 1;
      while high >= low do
        if fibs[high]*fibs[low] = inp then
          begin
            writeln('TAK');
            break
          end
        else
          begin
            low := low+1;
            rest := inp div fibs[low];
            while fibs[high] > rest do
              high := high-1;
          end;

      if high<low then writeln('NIE');
    end; {for}
end.