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
#include <cstdio>
#include <algorithm>
#include <vector>

#define unm unsigned long long int
#define uint unsigned int

unm fib[947] = {0ULL,1ULL,2ULL,3ULL,4ULL,5ULL,6ULL,8ULL,9ULL,10ULL,13ULL,15ULL,16ULL,21ULL,24ULL,25ULL,26ULL,34ULL,39ULL,40ULL,42ULL,55ULL,63ULL,64ULL,65ULL,68ULL,89ULL,102ULL,104ULL,105ULL,110ULL,144ULL,165ULL,168ULL,169ULL,170ULL,178ULL,233ULL,267ULL,272ULL,273ULL,275ULL,288ULL,377ULL,432ULL,440ULL,441ULL,442ULL,445ULL,466ULL,610ULL,699ULL,712ULL,714ULL,715ULL,720ULL,754ULL,987ULL,1131ULL,1152ULL,1155ULL,1156ULL,1157ULL,1165ULL,1220ULL,1597ULL,1830ULL,1864ULL,1869ULL,1870ULL,1872ULL,1885ULL,1974ULL,2584ULL,2961ULL,3016ULL,3024ULL,3025ULL,3026ULL,3029ULL,3050ULL,3194ULL,4181ULL,4791ULL,4880ULL,4893ULL,4895ULL,4896ULL,4901ULL,4935ULL,5168ULL,6765ULL,7752ULL,7896ULL,7917ULL,7920ULL,7921ULL,7922ULL,7930ULL,7985ULL,8362ULL,10946ULL,12543ULL,12776ULL,12810ULL,12815ULL,12816ULL,12818ULL,12831ULL,12920ULL,13530ULL,17711ULL,20295ULL,20672ULL,20727ULL,20735ULL,20736ULL,20737ULL,20740ULL,20761ULL,20905ULL,21892ULL,28657ULL,32838ULL,33448ULL,33537ULL,33550ULL,33552ULL,33553ULL,33558ULL,33592ULL,33825ULL,35422ULL,46368ULL,53133ULL,54120ULL,54264ULL,54285ULL,54288ULL,54289ULL,54290ULL,54298ULL,54353ULL,54730ULL,57314ULL,75025ULL,85971ULL,87568ULL,87801ULL,87835ULL,87840ULL,87841ULL,87843ULL,87856ULL,87945ULL,88555ULL,92736ULL,121393ULL,139104ULL,141688ULL,142065ULL,142120ULL,142128ULL,142129ULL,142130ULL,142133ULL,142154ULL,142298ULL,143285ULL,150050ULL,196418ULL,225075ULL,229256ULL,229866ULL,229955ULL,229968ULL,229970ULL,229971ULL,229976ULL,230010ULL,230243ULL,231840ULL,242786ULL,317811ULL,364179ULL,370944ULL,371931ULL,372075ULL,372096ULL,372099ULL,372100ULL,372101ULL,372109ULL,372164ULL,372541ULL,375125ULL,392836ULL,514229ULL,589254ULL,600200ULL,601797ULL,602030ULL,602064ULL,602069ULL,602070ULL,602072ULL,602085ULL,602174ULL,602784ULL,606965ULL,635622ULL,832040ULL,953433ULL,971144ULL,973728ULL,974105ULL,974160ULL,974168ULL,974169ULL,974170ULL,974173ULL,974194ULL,974338ULL,975325ULL,982090ULL,1028458ULL,1346269ULL,1542687ULL,1571344ULL,1575525ULL,1576135ULL,1576224ULL,1576237ULL,1576239ULL,1576240ULL,1576245ULL,1576279ULL,1576512ULL,1578109ULL,1589055ULL,1664080ULL,2178309ULL,2496120ULL,2542488ULL,2549253ULL,2550240ULL,2550384ULL,2550405ULL,2550408ULL,2550409ULL,2550410ULL,2550418ULL,2550473ULL,2550850ULL,2553434ULL,2571145ULL,2692538ULL,3524578ULL,4038807ULL,4113832ULL,4124778ULL,4126375ULL,4126608ULL,4126642ULL,4126647ULL,4126648ULL,4126650ULL,4126663ULL,4126752ULL,4127362ULL,4131543ULL,4160200ULL,4356618ULL,5702887ULL,6534927ULL,6656320ULL,6674031ULL,6676615ULL,6676992ULL,6677047ULL,6677055ULL,6677056ULL,6677057ULL,6677060ULL,6677081ULL,6677225ULL,6678212ULL,6684977ULL,6731345ULL,7049156ULL,9227465ULL,10573734ULL,10770152ULL,10798809ULL,10802990ULL,10803600ULL,10803689ULL,10803702ULL,10803704ULL,10803705ULL,10803710ULL,10803744ULL,10803977ULL,10805574ULL,10816520ULL,10891545ULL,11405774ULL,14930352ULL,17108661ULL,17426472ULL,17472840ULL,17479605ULL,17480592ULL,17480736ULL,17480757ULL,17480760ULL,17480761ULL,17480762ULL,17480770ULL,17480825ULL,17481202ULL,17483786ULL,17501497ULL,17622890ULL,18454930ULL,24157817ULL,27682395ULL,28196624ULL,28271649ULL,28282595ULL,28284192ULL,28284425ULL,28284459ULL,28284464ULL,28284465ULL,28284467ULL,28284480ULL,28284569ULL,28285179ULL,28289360ULL,28318017ULL,28514435ULL,29860704ULL,39088169ULL,44791056ULL,45623096ULL,45744489ULL,45762200ULL,45764784ULL,45765161ULL,45765216ULL,45765224ULL,45765225ULL,45765226ULL,45765229ULL,45765250ULL,45765394ULL,45766381ULL,45773146ULL,45819514ULL,46137325ULL,48315634ULL,63245986ULL,72473451ULL,73819720ULL,74016138ULL,74044795ULL,74048976ULL,74049586ULL,74049675ULL,74049688ULL,74049690ULL,74049691ULL,74049696ULL,74049730ULL,74049963ULL,74051560ULL,74062506ULL,74137531ULL,74651760ULL,78176338ULL,102334155ULL,117264507ULL,119442816ULL,119760627ULL,119806995ULL,119813760ULL,119814747ULL,119814891ULL,119814912ULL,119814915ULL,119814916ULL,119814917ULL,119814925ULL,119814980ULL,119815357ULL,119817941ULL,119835652ULL,119957045ULL,120789085ULL,126491972ULL,165580141ULL,189737958ULL,193262536ULL,193776765ULL,193851790ULL,193862736ULL,193864333ULL,193864566ULL,193864600ULL,193864605ULL,193864606ULL,193864608ULL,193864621ULL,193864710ULL,193865320ULL,193869501ULL,193898158ULL,194094576ULL,195440845ULL,204668310ULL,267914296ULL,307002465ULL,312705352ULL,313537392ULL,313658785ULL,313676496ULL,313679080ULL,313679457ULL,313679512ULL,313679520ULL,313679521ULL,313679522ULL,313679525ULL,313679546ULL,313679690ULL,313680677ULL,313687442ULL,313733810ULL,314051621ULL,316229930ULL,331160282ULL,433494437ULL,496740423ULL,505967888ULL,507314157ULL,507510575ULL,507539232ULL,507543413ULL,507544023ULL,507544112ULL,507544125ULL,507544127ULL,507544128ULL,507544133ULL,507544167ULL,507544400ULL,507545997ULL,507556943ULL,507631968ULL,508146197ULL,511670775ULL,535828592ULL,701408733ULL,803742888ULL,818673240ULL,820851549ULL,821169360ULL,821215728ULL,821222493ULL,821223480ULL,821223624ULL,821223645ULL,821223648ULL,821223649ULL,821223650ULL,821223658ULL,821223713ULL,821224090ULL,821226674ULL,821244385ULL,821365778ULL,822197818ULL,827900705ULL,866988874ULL,1300483311ULL,1324641128ULL,1328165706ULL,1328679935ULL,1328754960ULL,1328765906ULL,1328767503ULL,1328767736ULL,1328767770ULL,1328767775ULL,1328767776ULL,1328767778ULL,1328767791ULL,1328767880ULL,1328768490ULL,1328772671ULL,1328801328ULL,1328997746ULL,1330344015ULL,1339571480ULL,1402817466ULL,2104226199ULL,2143314368ULL,2149017255ULL,2149849295ULL,2149970688ULL,2149988399ULL,2149990983ULL,2149991360ULL,2149991415ULL,2149991423ULL,2149991424ULL,2149991425ULL,2149991428ULL,2149991449ULL,2149991593ULL,2149992580ULL,2149999345ULL,2150045713ULL,2150363524ULL,2152541833ULL,2167472185ULL,3467955496ULL,3477182961ULL,3478529230ULL,3478725648ULL,3478754305ULL,3478758486ULL,3478759096ULL,3478759185ULL,3478759198ULL,3478759200ULL,3478759201ULL,3478759206ULL,3478759240ULL,3478759473ULL,3478761070ULL,3478772016ULL,3478847041ULL,3479361270ULL,3482885848ULL,3507043665ULL,5611269864ULL,5626200216ULL,5628378525ULL,5628696336ULL,5628742704ULL,5628749469ULL,5628750456ULL,5628750600ULL,5628750621ULL,5628750624ULL,5628750625ULL,5628750626ULL,5628750634ULL,5628750689ULL,5628751066ULL,5628753650ULL,5628771361ULL,5628892754ULL,5629724794ULL,5635427681ULL,9103383177ULL,9106907755ULL,9107421984ULL,9107497009ULL,9107507955ULL,9107509552ULL,9107509785ULL,9107509819ULL,9107509824ULL,9107509825ULL,9107509827ULL,9107509840ULL,9107509929ULL,9107510539ULL,9107514720ULL,9107543377ULL,9107739795ULL,9109086064ULL,9118313529ULL,14729583393ULL,14735286280ULL,14736118320ULL,14736239713ULL,14736257424ULL,14736260008ULL,14736260385ULL,14736260440ULL,14736260448ULL,14736260449ULL,14736260450ULL,14736260453ULL,14736260474ULL,14736260618ULL,14736261605ULL,14736268370ULL,14736314738ULL,14736632549ULL,14738810858ULL,23842194035ULL,23843540304ULL,23843736722ULL,23843765379ULL,23843769560ULL,23843770170ULL,23843770259ULL,23843770272ULL,23843770274ULL,23843770275ULL,23843770280ULL,23843770314ULL,23843770547ULL,23843772144ULL,23843783090ULL,23843858115ULL,23844372344ULL,23847896922ULL,38577480315ULL,38579658624ULL,38579976435ULL,38580022803ULL,38580029568ULL,38580030555ULL,38580030699ULL,38580030720ULL,38580030723ULL,38580030724ULL,38580030725ULL,38580030733ULL,38580030788ULL,38580031165ULL,38580033749ULL,38580051460ULL,38580172853ULL,38581004893ULL,62423198928ULL,62423713157ULL,62423788182ULL,62423799128ULL,62423800725ULL,62423800958ULL,62423800992ULL,62423800997ULL,62423800998ULL,62423801000ULL,62423801013ULL,62423801102ULL,62423801712ULL,62423805893ULL,62423834550ULL,62424030968ULL,62425377237ULL,101002857552ULL,101003689592ULL,101003810985ULL,101003828696ULL,101003831280ULL,101003831657ULL,101003831712ULL,101003831720ULL,101003831721ULL,101003831722ULL,101003831725ULL,101003831746ULL,101003831890ULL,101003832877ULL,101003839642ULL,101003886010ULL,101004203821ULL,163427402749ULL,163427599167ULL,163427627824ULL,163427632005ULL,163427632615ULL,163427632704ULL,163427632717ULL,163427632719ULL,163427632720ULL,163427632725ULL,163427632759ULL,163427632992ULL,163427634589ULL,163427645535ULL,163427720560ULL,163428234789ULL,264431092341ULL,264431410152ULL,264431456520ULL,264431463285ULL,264431464272ULL,264431464416ULL,264431464437ULL,264431464440ULL,264431464441ULL,264431464442ULL,264431464450ULL,264431464505ULL,264431464882ULL,264431467466ULL,264431485177ULL,264431606570ULL,427859009319ULL,427859084344ULL,427859095290ULL,427859096887ULL,427859097120ULL,427859097154ULL,427859097159ULL,427859097160ULL,427859097162ULL,427859097175ULL,427859097264ULL,427859097874ULL,427859102055ULL,427859130712ULL,427859327130ULL,692290419471ULL,692290540864ULL,692290558575ULL,692290561159ULL,692290561536ULL,692290561591ULL,692290561599ULL,692290561600ULL,692290561601ULL,692290561604ULL,692290561625ULL,692290561769ULL,692290562756ULL,692290569521ULL,692290615889ULL,1120149625208ULL,1120149653865ULL,1120149658046ULL,1120149658656ULL,1120149658745ULL,1120149658758ULL,1120149658760ULL,1120149658761ULL,1120149658766ULL,1120149658800ULL,1120149659033ULL,1120149660630ULL,1120149671576ULL,1120149746601ULL,1812440166072ULL,1812440212440ULL,1812440219205ULL,1812440220192ULL,1812440220336ULL,1812440220357ULL,1812440220360ULL,1812440220361ULL,1812440220362ULL,1812440220370ULL,1812440220425ULL,1812440220802ULL,1812440223386ULL,1812440241097ULL,2932589866305ULL,2932589877251ULL,2932589878848ULL,2932589879081ULL,2932589879115ULL,2932589879120ULL,2932589879121ULL,2932589879123ULL,2932589879136ULL,2932589879225ULL,2932589879835ULL,2932589884016ULL,2932589912673ULL,4745030078745ULL,4745030096456ULL,4745030099040ULL,4745030099417ULL,4745030099472ULL,4745030099480ULL,4745030099481ULL,4745030099482ULL,4745030099485ULL,4745030099506ULL,4745030099650ULL,4745030100637ULL,4745030107402ULL,7677619973707ULL,7677619977888ULL,7677619978498ULL,7677619978587ULL,7677619978600ULL,7677619978602ULL,7677619978603ULL,7677619978608ULL,7677619978642ULL,7677619978875ULL,7677619980472ULL,7677619991418ULL,12422650070163ULL,12422650076928ULL,12422650077915ULL,12422650078059ULL,12422650078080ULL,12422650078083ULL,12422650078084ULL,12422650078085ULL,12422650078093ULL,12422650078148ULL,12422650078525ULL,12422650081109ULL,20100270054816ULL,20100270056413ULL,20100270056646ULL,20100270056680ULL,20100270056685ULL,20100270056686ULL,20100270056688ULL,20100270056701ULL,20100270056790ULL,20100270057400ULL,20100270061581ULL,32522920131744ULL,32522920134328ULL,32522920134705ULL,32522920134760ULL,32522920134768ULL,32522920134769ULL,32522920134770ULL,32522920134773ULL,32522920134794ULL,32522920134938ULL,32522920135925ULL,52623190190741ULL,52623190191351ULL,52623190191440ULL,52623190191453ULL,52623190191455ULL,52623190191456ULL,52623190191461ULL,52623190191495ULL,52623190191728ULL,52623190193325ULL,85146110325069ULL,85146110326056ULL,85146110326200ULL,85146110326221ULL,85146110326224ULL,85146110326225ULL,85146110326226ULL,85146110326234ULL,85146110326289ULL,85146110326666ULL,137769300517407ULL,137769300517640ULL,137769300517674ULL,137769300517679ULL,137769300517680ULL,137769300517682ULL,137769300517695ULL,137769300517784ULL,137769300518394ULL,222915410843463ULL,222915410843840ULL,222915410843895ULL,222915410843903ULL,222915410843904ULL,222915410843905ULL,222915410843908ULL,222915410843929ULL,222915410844073ULL,360684711361480ULL,360684711361569ULL,360684711361582ULL,360684711361584ULL,360684711361585ULL,360684711361590ULL,360684711361624ULL,360684711361857ULL,583600122205320ULL,583600122205464ULL,583600122205485ULL,583600122205488ULL,583600122205489ULL,583600122205490ULL,583600122205498ULL,583600122205553ULL,944284833567033ULL,944284833567067ULL,944284833567072ULL,944284833567073ULL,944284833567075ULL,944284833567088ULL,944284833567177ULL,1527884955772497ULL,1527884955772552ULL,1527884955772560ULL,1527884955772561ULL,1527884955772562ULL,1527884955772565ULL,1527884955772586ULL,2472169789339619ULL,2472169789339632ULL,2472169789339634ULL,2472169789339635ULL,2472169789339640ULL,2472169789339674ULL,4000054745112171ULL,4000054745112192ULL,4000054745112195ULL,4000054745112196ULL,4000054745112197ULL,4000054745112205ULL,6472224534451824ULL,6472224534451829ULL,6472224534451830ULL,6472224534451832ULL,6472224534451845ULL,10472279279564016ULL,10472279279564024ULL,10472279279564025ULL,10472279279564026ULL,10472279279564029ULL,16944503814015853ULL,16944503814015855ULL,16944503814015856ULL,16944503814015861ULL,27416783093579877ULL,27416783093579880ULL,27416783093579881ULL,27416783093579882ULL,44361286907595735ULL,44361286907595736ULL,44361286907595738ULL,71778070001175615ULL,71778070001175616ULL,71778070001175617ULL,116139356908771352ULL,116139356908771353ULL,187917426909946968ULL,187917426909946969ULL,304056783818718321ULL,491974210728665289ULL};
uint n;
unm temp;

int main()
{
    scanf("%u", &n);
    for(uint i=0;i<n;i++) {
        scanf("%llu", &temp);
        if(std::binary_search(std::begin(fib),std::end(fib),temp))
            printf("TAK\n");
        else
            printf("NIE\n");
    }


    return 0;
}