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
#include<cstdio>
#include<iostream>
using namespace std;
int n,F[50],l,a,b,D[50];
void tworz(int n) {
 F[0]=0;F[1]=1;
 for (int i=2;i<=n;i++) F[i]=F[i-1]+F[i-2];
}

int dzielniki(int l) {
 int ile=0;
 if (l==0) return 0;
 for (int i=1;F[i]<=l;i++) {
   if (l%F[i]==0) {
    D[ile]=F[i];
    ile++;
   }
 }
  return ile;
}
bool sprawdz(int n) {
 int l=0,p;
 p=dzielniki(n)-1;
 //cout <<p<<endl;
 while (l<=p) {
  if (D[l]*D[p]==n) return true;
  if   (D[l]*D[p]<n) l++;
  else p--;
 }
 return false;
}


int main(){
 ios_base::sync_with_stdio(0);
 tworz(50);
 cin >>n;
 for (int i=0;i<n;i++) {
  cin>>l;
  if (l==0) cout <<"TAK"<<endl;
  else {
    if (sprawdz(l)) cout <<"TAK"<<endl;
    else cout <<"NIE"<<endl;
  }
 }

 return 0;
}