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
#include <algorithm>
#include <iostream>

using namespace std;

namespace {

const unsigned coeffsSize = 947;

unsigned long long coeffs[coeffsSize] = {
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, 1300483311, 1324641128, 1328165706, 1328679935, 1328754960, 1328765906, 1328767503, 1328767736, 1328767770, 1328767775, 1328767776, 1328767778, 1328767791, 1328767880, 1328768490, 1328772671, 1328801328, 1328997746, 1330344015, 1339571480, 1402817466, 2104226199, 2143314368, 2149017255, 2149849295, 2149970688, 2149988399, 2149990983, 2149991360, 2149991415, 2149991423, 2149991424, 2149991425, 2149991428, 2149991449, 2149991593, 2149992580, 2149999345, 2150045713, 2150363524, 2152541833, 2167472185, 3467955496, 3477182961, 3478529230, 3478725648, 3478754305, 3478758486, 3478759096, 3478759185, 3478759198, 3478759200, 3478759201, 3478759206, 3478759240, 3478759473, 3478761070, 3478772016, 3478847041, 3479361270, 3482885848, 3507043665, 5611269864, 5626200216, 5628378525, 5628696336, 5628742704, 5628749469, 5628750456, 5628750600, 5628750621, 5628750624, 5628750625, 5628750626, 5628750634, 5628750689, 5628751066, 5628753650, 5628771361, 5628892754, 5629724794, 5635427681, 9103383177, 9106907755, 9107421984, 9107497009, 9107507955, 9107509552, 9107509785, 9107509819, 9107509824, 9107509825, 9107509827, 9107509840, 9107509929, 9107510539, 9107514720, 9107543377, 9107739795, 9109086064, 9118313529, 14729583393, 14735286280, 14736118320, 14736239713, 14736257424, 14736260008, 14736260385, 14736260440, 14736260448, 14736260449, 14736260450, 14736260453, 14736260474, 14736260618, 14736261605, 14736268370, 14736314738, 14736632549, 14738810858, 23842194035, 23843540304, 23843736722, 23843765379, 23843769560, 23843770170, 23843770259, 23843770272, 23843770274, 23843770275, 23843770280, 23843770314, 23843770547, 23843772144, 23843783090, 23843858115, 23844372344, 23847896922, 38577480315, 38579658624, 38579976435, 38580022803, 38580029568, 38580030555, 38580030699, 38580030720, 38580030723, 38580030724, 38580030725, 38580030733, 38580030788, 38580031165, 38580033749, 38580051460, 38580172853, 38581004893, 62423198928, 62423713157, 62423788182, 62423799128, 62423800725, 62423800958, 62423800992, 62423800997, 62423800998, 62423801000, 62423801013, 62423801102, 62423801712, 62423805893, 62423834550, 62424030968, 62425377237, 101002857552, 101003689592, 101003810985, 101003828696, 101003831280, 101003831657, 101003831712, 101003831720, 101003831721, 101003831722, 101003831725, 101003831746, 101003831890, 101003832877, 101003839642, 101003886010, 101004203821, 163427402749, 163427599167, 163427627824, 163427632005, 163427632615, 163427632704, 163427632717, 163427632719, 163427632720, 163427632725, 163427632759, 163427632992, 163427634589, 163427645535, 163427720560, 163428234789, 264431092341, 264431410152, 264431456520, 264431463285, 264431464272, 264431464416, 264431464437, 264431464440, 264431464441, 264431464442, 264431464450, 264431464505, 264431464882, 264431467466, 264431485177, 264431606570, 427859009319, 427859084344, 427859095290, 427859096887, 427859097120, 427859097154, 427859097159, 427859097160, 427859097162, 427859097175, 427859097264, 427859097874, 427859102055, 427859130712, 427859327130, 692290419471, 692290540864, 692290558575, 692290561159, 692290561536, 692290561591, 692290561599, 692290561600, 692290561601, 692290561604, 692290561625, 692290561769, 692290562756, 692290569521, 692290615889, 1120149625208, 1120149653865, 1120149658046, 1120149658656, 1120149658745, 1120149658758, 1120149658760, 1120149658761, 1120149658766, 1120149658800, 1120149659033, 1120149660630, 1120149671576, 1120149746601, 1812440166072, 1812440212440, 1812440219205, 1812440220192, 1812440220336, 1812440220357, 1812440220360, 1812440220361, 1812440220362, 1812440220370, 1812440220425, 1812440220802, 1812440223386, 1812440241097, 2932589866305, 2932589877251, 2932589878848, 2932589879081, 2932589879115, 2932589879120, 2932589879121, 2932589879123, 2932589879136, 2932589879225, 2932589879835, 2932589884016, 2932589912673, 4745030078745, 4745030096456, 4745030099040, 4745030099417, 4745030099472, 4745030099480, 4745030099481, 4745030099482, 4745030099485, 4745030099506, 4745030099650, 4745030100637, 4745030107402, 7677619973707, 7677619977888, 7677619978498, 7677619978587, 7677619978600, 7677619978602, 7677619978603, 7677619978608, 7677619978642, 7677619978875, 7677619980472, 7677619991418, 12422650070163, 12422650076928, 12422650077915, 12422650078059, 12422650078080, 12422650078083, 12422650078084, 12422650078085, 12422650078093, 12422650078148, 12422650078525, 12422650081109, 20100270054816, 20100270056413, 20100270056646, 20100270056680, 20100270056685, 20100270056686, 20100270056688, 20100270056701, 20100270056790, 20100270057400, 20100270061581, 32522920131744, 32522920134328, 32522920134705, 32522920134760, 32522920134768, 32522920134769, 32522920134770, 32522920134773, 32522920134794, 32522920134938, 32522920135925, 52623190190741, 52623190191351, 52623190191440, 52623190191453, 52623190191455, 52623190191456, 52623190191461, 52623190191495, 52623190191728, 52623190193325, 85146110325069, 85146110326056, 85146110326200, 85146110326221, 85146110326224, 85146110326225, 85146110326226, 85146110326234, 85146110326289, 85146110326666, 137769300517407, 137769300517640, 137769300517674, 137769300517679, 137769300517680, 137769300517682, 137769300517695, 137769300517784, 137769300518394, 222915410843463, 222915410843840, 222915410843895, 222915410843903, 222915410843904, 222915410843905, 222915410843908, 222915410843929, 222915410844073, 360684711361480, 360684711361569, 360684711361582, 360684711361584, 360684711361585, 360684711361590, 360684711361624, 360684711361857, 583600122205320, 583600122205464, 583600122205485, 583600122205488, 583600122205489, 583600122205490, 583600122205498, 583600122205553, 944284833567033, 944284833567067, 944284833567072, 944284833567073, 944284833567075, 944284833567088, 944284833567177, 1527884955772497, 1527884955772552, 1527884955772560, 1527884955772561, 1527884955772562, 1527884955772565, 1527884955772586, 2472169789339619, 2472169789339632, 2472169789339634, 2472169789339635, 2472169789339640, 2472169789339674, 4000054745112171, 4000054745112192, 4000054745112195, 4000054745112196, 4000054745112197, 4000054745112205, 6472224534451824, 6472224534451829, 6472224534451830, 6472224534451832, 6472224534451845, 10472279279564016, 10472279279564024, 10472279279564025, 10472279279564026, 10472279279564029, 16944503814015853, 16944503814015855, 16944503814015856, 16944503814015861, 27416783093579877, 27416783093579880, 27416783093579881, 27416783093579882, 44361286907595735, 44361286907595736, 44361286907595738, 71778070001175615, 71778070001175616, 71778070001175617, 116139356908771352, 116139356908771353, 187917426909946968, 187917426909946969, 304056783818718321, 491974210728665289
};

}

bool test(unsigned const x) {
    return binary_search(
        coeffs,
        coeffs + coeffsSize,
        static_cast<unsigned long long>(x));
}

int main() {
    unsigned n, x;
    cin >> n;

    for (unsigned i = 0; i < n; ++i) {
        cin >> x;
        cout << (test(x) ? "TAK" : "NIE") << endl;
    }
}