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

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