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
140
141
142
143
144
145
146
147
148
149
150
#include <stdio.h>

typedef long long int llint;

llint tocheck[485] =
{
	         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 findnmb(llint nmb, llint *arr, int size);

int main(void)
{
	int datasetNumber;
	llint nmb;
	
	scanf("%d ", &datasetNumber);
	
	while(datasetNumber--)
	{
		scanf("%lld ", &nmb);
		if(findnmb(nmb,tocheck,485) == -1)
			printf("NIE\n");
		else
			printf("TAK\n");
	}

	return 0;
}

int findnmb(llint nmb, llint *arr, int size)
{
	int ip=0, ik=size-1, is;
	
	while(1)
	{
		if((ik-ip) == 1)
		{
			if(nmb==arr[ip])
				return ip;
			else if(nmb==arr[ik])
				return ik;
			return -1;
		}
		
		is=(ip+ik)/2;
		if(nmb == arr[is])
			return is;
		else if(nmb > arr[is])
			ip=is;
		else
			ik=is;
	}
}