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
#include <stdio.h>

int f[485]=
{
0,1,2,3,4,5,6,8,9,10,13,15,16,21,24,25
,26,34,39,40,42,55,63,64,65,68,89,102,104,105,110,144
,165,168,169,170,178,233,267,272,273,275,288,377,432,440,441,442
,445,466,610,699,712,714,715,720,754,987,1131,1152,1155,1156,1157,1165
,1220,1597,1830,1864,1869,1870,1872,1885,1974,2584,2961,3016,3024,3025,3026,3029
,3050,3194,4181,4791,4880,4893,4895,4896,4901,4935,5168,6765,7752,7896,7917,7920
,7921,7922,7930,7985,8362,10946,12543,12776,12810,12815,12816,12818,12831,12920,13530,17711
,20295,20672,20727,20735,20736,20737,20740,20761,20905,21892,28657,32838,33448,33537,33550,33552
,33553,33558,33592,33825,35422,46368,53133,54120,54264,54285,54288,54289,54290,54298,54353,54730
,57314,75025,85971,87568,87801,87835,87840,87841,87843,87856,87945,88555,92736,121393,139104,141688
,142065,142120,142128,142129,142130,142133,142154,142298,143285,150050,196418,225075,229256,229866,229955,229968
,229970,229971,229976,230010,230243,231840,242786,317811,364179,370944,371931,372075,372096,372099,372100,372101
,372109,372164,372541,375125,392836,514229,589254,600200,601797,602030,602064,602069,602070,602072,602085,602174
,602784,606965,635622,832040,953433,971144,973728,974105,974160,974168,974169,974170,974173,974194,974338,975325
,982090,1028458,1346269,1542687,1571344,1575525,1576135,1576224,1576237,1576239,1576240,1576245,1576279,1576512,1578109,1589055
,1664080,2178309,2496120,2542488,2549253,2550240,2550384,2550405,2550408,2550409,2550410,2550418,2550473,2550850,2553434,2571145
,2692538,3524578,4038807,4113832,4124778,4126375,4126608,4126642,4126647,4126648,4126650,4126663,4126752,4127362,4131543,4160200
,4356618,5702887,6534927,6656320,6674031,6676615,6676992,6677047,6677055,6677056,6677057,6677060,6677081,6677225,6678212,6684977
,6731345,7049156,9227465,10573734,10770152,10798809,10802990,10803600,10803689,10803702,10803704,10803705,10803710,10803744,10803977,10805574
,10816520,10891545,11405774,14930352,17108661,17426472,17472840,17479605,17480592,17480736,17480757,17480760,17480761,17480762,17480770,17480825
,17481202,17483786,17501497,17622890,18454930,24157817,27682395,28196624,28271649,28282595,28284192,28284425,28284459,28284464,28284465,28284467
,28284480,28284569,28285179,28289360,28318017,28514435,29860704,39088169,44791056,45623096,45744489,45762200,45764784,45765161,45765216,45765224
,45765225,45765226,45765229,45765250,45765394,45766381,45773146,45819514,46137325,48315634,63245986,72473451,73819720,74016138,74044795,74048976
,74049586,74049675,74049688,74049690,74049691,74049696,74049730,74049963,74051560,74062506,74137531,74651760,78176338,102334155,117264507,119442816
,119760627,119806995,119813760,119814747,119814891,119814912,119814915,119814916,119814917,119814925,119814980,119815357,119817941,119835652,119957045,120789085
,126491972,165580141,189737958,193262536,193776765,193851790,193862736,193864333,193864566,193864600,193864605,193864606,193864608,193864621,193864710,193865320
,193869501,193898158,194094576,195440845,204668310,267914296,307002465,312705352,313537392,313658785,313676496,313679080,313679457,313679512,313679520,313679521
,313679522,313679525,313679546,313679690,313680677,313687442,313733810,314051621,316229930,331160282,433494437,496740423,505967888,507314157,507510575,507539232
,507543413,507544023,507544112,507544125,507544127,507544128,507544133,507544167,507544400,507545997,507556943,507631968,508146197,511670775,535828592,701408733
,803742888,818673240,820851549,821169360,821215728,821222493,821223480,821223624,821223645,821223648,821223649,821223650,821223658,821223713,821224090,821226674
,821244385,821365778,822197818,827900705,866988874
};

int main(void)
{
 int i=0,t,l,a,b,c;
 scanf("%d",&t);
 for(;i<t;++i)
 {
  a=0;b=484;
  scanf("%d",&l);
  while(f[a]!=l && f[b]!=l && b-a>1)
  {
   c=a+((b-a)>>1);
   if(f[c]>=l)b=c;
   else a=c;
   //printf("%d %d\n",a,b);
  }
  if(f[a]==l || f[b]==l)printf("TAK\n");
  else printf("NIE\n");
  //printf("%d %d\n",l,f[b]);
 }
 return 0;
}