1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <algorithm>

using namespace std;

int tab[]={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,218645501,218841919,218870576,218874757,218875367,218875456,218875469,218875471,218875472,218875477,218875511,218875744,218877341,218888287,218963312,219477541,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,513448585,516973163,517487392,517562417,517573363,517574960,517575193,517575227,517575232,517575233,517575235,517575248,517575337,517575947,517580128,517608785,517805203,519151472,528378937,535828592,623026377,701408733,800684815,800806208,800823919,800826503,800826880,800826935,800826943,800826944,800826945,800826948,800826969,800827113,800828100,800834865,800881233,803742888,818673240,820851549,821169360,821215728,821222493,821223480,821223624,821223645,821223648,821223649,821223650,821223658,821223713,821224090,821226674,821244385,821365778,822197818,827900705,866988874,877155952,877155957,877155958,877155960,877155973,956127256,956127257};

int main()
{
    int t;
    cin >> t;

    for(int i=0;i<t;i++){
        int n;
        cin >> n;
        if(binary_search(tab,tab+543,n))cout << "TAK\n";
        else cout << "NIE\n";
    }

    return 0;
}