#include <cstdio>
#include <set>

using namespace std;

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

int main() {
  int i;
  int j;
  scanf("%d", &i);
  while(i--) {
    scanf("%d", &j);
    if (values.find(j) == values.end())
      printf("NIE\n");
    else 
      printf("TAK\n");
  }
  return 0;
}