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
#include<cstdio>
int t, i, n, f[50];

bool fib(int x)
{
  for(int i = 0; i <= x; i++)
  {
    if (f[i] == x){return true;}
  }
  return false;
}

int main()
{
  scanf("%d", &t);
  
  f[0] = 1;
  f[1] = 2;
  
  for(i = 2; i < 45; i++)
  {
    f[i] = f[i - 1] + f[i - 2];
  }
  
  while(t--)
  {
    scanf("%d", &n);
    for(i = 1; i * i <= n; i++)
    {
      if (n % i == 0 && fib(i) == true && fib(n / i) == true)
      {
	printf("TAK\n");
	break;
      }
      if ((i + 1) * (i + 1) > n){printf("NIE\n");}
    }
  }
  
return 0;
}