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
#include <stdio.h>
#define MAXF 45
#define MAXR 485
//----------------------------------

int F[MAXF] = {0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170};
int T[MAXR] = {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};
//----------------------------------

char check(int n)
{
 int p, l=0, r=MAXR;
   
 while (l<r)
 {
   p = (l+r)>>1;
   if (n==T[p]) return 1;      
   if (n>T[p]) l=p+1; else r=p;
 }

return 0;
}
//----------------------------------

int main(void)
{
  int i, j, k, n, t;    
  //freopen("ilo/0.in", "r", stdin);
  //freopen("ilo/0.out", "w", stdout);
    
  scanf("%d\n", &t);
  while(t--)
  {
    scanf("%d", &n);

    if (check(n)) puts("TAK");
     else puts("NIE");
  }

return 0;
}
//----------------------------------