1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <stdlib.h>

int c(const void *a, const void *b)
{
  return *(int*)a-*(int*)b;
}

int main()
{
  int i,j,p,q,a[500]={0},n=1,t,l;
  for (i=1,j=2;i*i<=1000000000u;j+=i,i=j-i)
  for (p=i,q=j;i*p<=1000000000u;q+=p,p=q-p) a[n++]=i*p;
  qsort(a,n,sizeof(*a),c);
  scanf("%d",&t);
  for (;t--;)
  {
    scanf("%d",&l);
    puts(bsearch(&l,a,n,sizeof(*a),c) == NULL? "NIE": "TAK");
  }
  return 0;
}