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

using namespace std;

int main(){
	ios_base::sync_with_stdio(0);
	vector<int> v={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};

	int N;
	cin>>N;
	for(int i=0;i<N;++i){
		int p;
		cin>>p;
		if(binary_search(v.begin(),v.end(),p))
			cout<<"TAK"<<endl;
		else
			cout<<"NIE"<<endl;
		}
	v.clear();
	return 0;
}