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
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
//============================================================================
// Name        : ilo.cpp
// Author      : Grzegorz Gajoch
// Version     :
// Copyright   : 
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <vector>
#include <set>
using namespace std;

typedef unsigned long long ULL;

ULL tab[500];

set<ULL> S(
{ 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, 1134903170,
		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,
		2269806340, 3404709510, 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,
		5674515850, 9079225360, 9103383177, 9106907755, 9107421984, 9107497009,
		9107507955, 9107509552, 9107509785, 9107509819, 9107509824, 9107509825,
		9107509827, 9107509840, 9107509929, 9107510539, 9107514720, 9107543377,
		9107739795, 9109086064, 9118313529 });

int main()
{
	int Z;
	cin >> Z;
	while (Z--)
	{
		int Z;
		cin >> Z;
		if (S.find(Z) == S.end())
			cout << "NIE\n";
		else
			cout << "TAK\n";
	}
	/*vector <ULL> tab;
	 set <ULL>S;
	 tab.push_back(0);
	 tab.push_back(1);
	 auto i = (int)2;
	 while(true)
	 {
	 auto x = tab[i-1] + tab[i-2];
	 tab.push_back(x);
	 if( x > 1e9 ) break;
	 i++;
	 }
	 cout << "tab[] = { ";
	 for(auto &x: tab)
	 {
	 for(auto &y: tab)
	 {
	 auto t = x*y;
	 if( t < 1e10 ){
	 S.insert(t);
	 }
	 }
	 }
	 for(auto &x: S)
	 {
	 cout << x << ", ";
	 }
	 cout << "!!!Hello World!!!" << endl; // prints !!!Hello World!!!*/
	return 0;
}