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

using namespace std;

#define N 46

long long fibNums[N][N] = {{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
						   {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170},
						   {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170},
						   {0, 2, 2, 4, 6, 10, 16, 26, 42, 68, 110, 178, 288, 466, 754, 1220, 1974, 3194, 5168, 8362, 13530, 21892, 35422, 57314, 92736, 150050, 242786, 392836, 635622, 1028458, 1664080, 2692538, 4356618, 7049156, 11405774, 18454930, 29860704, 48315634, 78176338, 126491972, 204668310, 331160282, 535828592, 866988874, 1402817466, 2269806340},
						   {0, 3, 3, 6, 9, 15, 24, 39, 63, 102, 165, 267, 432, 699, 1131, 1830, 2961, 4791, 7752, 12543, 20295, 32838, 53133, 85971, 139104, 225075, 364179, 589254, 953433, 1542687, 2496120, 4038807, 6534927, 10573734, 17108661, 27682395, 44791056, 72473451, 117264507, 189737958, 307002465, 496740423, 803742888, 1300483311, 2104226199, 3404709510},
						   {0, 5, 5, 10, 15, 25, 40, 65, 105, 170, 275, 445, 720, 1165, 1885, 3050, 4935, 7985, 12920, 20905, 33825, 54730, 88555, 143285, 231840, 375125, 606965, 982090, 1589055, 2571145, 4160200, 6731345, 10891545, 17622890, 28514435, 46137325, 74651760, 120789085, 195440845, 316229930, 511670775, 827900705, 1339571480, 2167472185, 3507043665, 5674515850},
						   {0, 8, 8, 16, 24, 40, 64, 104, 168, 272, 440, 712, 1152, 1864, 3016, 4880, 7896, 12776, 20672, 33448, 54120, 87568, 141688, 229256, 370944, 600200, 971144, 1571344, 2542488, 4113832, 6656320, 10770152, 17426472, 28196624, 45623096, 73819720, 119442816, 193262536, 312705352, 505967888, 818673240, 1324641128, 2143314368, 3467955496, 5611269864, 9079225360},
						   {0, 13, 13, 26, 39, 65, 104, 169, 273, 442, 715, 1157, 1872, 3029, 4901, 7930, 12831, 20761, 33592, 54353, 87945, 142298, 230243, 372541, 602784, 975325, 1578109, 2553434, 4131543, 6684977, 10816520, 17501497, 28318017, 45819514, 74137531, 119957045, 194094576, 314051621, 508146197, 822197818, 1330344015, 2152541833, 3482885848, 5635427681, 9118313529, 14753741210},
						   {0, 21, 21, 42, 63, 105, 168, 273, 441, 714, 1155, 1869, 3024, 4893, 7917, 12810, 20727, 33537, 54264, 87801, 142065, 229866, 371931, 601797, 973728, 1575525, 2549253, 4124778, 6674031, 10798809, 17472840, 28271649, 45744489, 74016138, 119760627, 193776765, 313537392, 507314157, 820851549, 1328165706, 2149017255, 3477182961, 5626200216, 9103383177, 14729583393, 23832966570},
						   {0, 34, 34, 68, 102, 170, 272, 442, 714, 1156, 1870, 3026, 4896, 7922, 12818, 20740, 33558, 54298, 87856, 142154, 230010, 372164, 602174, 974338, 1576512, 2550850, 4127362, 6678212, 10805574, 17483786, 28289360, 45773146, 74062506, 119835652, 193898158, 313733810, 507631968, 821365778, 1328997746, 2150363524, 3479361270, 5629724794, 9109086064, 14738810858, 23847896922, 38586707780},
						   {0, 55, 55, 110, 165, 275, 440, 715, 1155, 1870, 3025, 4895, 7920, 12815, 20735, 33550, 54285, 87835, 142120, 229955, 372075, 602030, 974105, 1576135, 2550240, 4126375, 6676615, 10802990, 17479605, 28282595, 45762200, 74044795, 119806995, 193851790, 313658785, 507510575, 821169360, 1328679935, 2149849295, 3478529230, 5628378525, 9106907755, 14735286280, 23842194035, 38577480315, 62419674350},
						   {0, 89, 89, 178, 267, 445, 712, 1157, 1869, 3026, 4895, 7921, 12816, 20737, 33553, 54290, 87843, 142133, 229976, 372109, 602085, 974194, 1576279, 2550473, 4126752, 6677225, 10803977, 17481202, 28285179, 45766381, 74051560, 119817941, 193869501, 313687442, 507556943, 821244385, 1328801328, 2150045713, 3478847041, 5628892754, 9107739795, 14736632549, 23844372344, 38581004893, 62425377237, 101006382130},
						   {0, 144, 144, 288, 432, 720, 1152, 1872, 3024, 4896, 7920, 12816, 20736, 33552, 54288, 87840, 142128, 229968, 372096, 602064, 974160, 1576224, 2550384, 4126608, 6676992, 10803600, 17480592, 28284192, 45764784, 74048976, 119813760, 193862736, 313676496, 507539232, 821215728, 1328754960, 2149970688, 3478725648, 5628696336, 9107421984, 14736118320, 23843540304, 38579658624, 62423198928, 101002857552, 163426056480},
						   {0, 233, 233, 466, 699, 1165, 1864, 3029, 4893, 7922, 12815, 20737, 33552, 54289, 87841, 142130, 229971, 372101, 602072, 974173, 1576245, 2550418, 4126663, 6677081, 10803744, 17480825, 28284569, 45765394, 74049963, 119815357, 193865320, 313680677, 507545997, 821226674, 1328772671, 2149999345, 3478772016, 5628771361, 9107543377, 14736314738, 23843858115, 38580172853, 62424030968, 101004203821, 163428234789, 264432438610},
						   {0, 377, 377, 754, 1131, 1885, 3016, 4901, 7917, 12818, 20735, 33553, 54288, 87841, 142129, 229970, 372099, 602069, 974168, 1576237, 2550405, 4126642, 6677047, 10803689, 17480736, 28284425, 45765161, 74049586, 119814747, 193864333, 313679080, 507543413, 821222493, 1328765906, 2149988399, 3478754305, 5628742704, 9107497009, 14736239713, 23843736722, 38579976435, 62423713157, 101003689592, 163427402749, 264431092341, 427858495090},
						   {0, 610, 610, 1220, 1830, 3050, 4880, 7930, 12810, 20740, 33550, 54290, 87840, 142130, 229970, 372100, 602070, 974170, 1576240, 2550410, 4126650, 6677060, 10803710, 17480770, 28284480, 45765250, 74049730, 119814980, 193864710, 313679690, 507544400, 821224090, 1328768490, 2149992580, 3478761070, 5628753650, 9107514720, 14736268370, 23843783090, 38580051460, 62423834550, 101003886010, 163427720560, 264431606570, 427859327130, 692290933700},
						   {0, 987, 987, 1974, 2961, 4935, 7896, 12831, 20727, 33558, 54285, 87843, 142128, 229971, 372099, 602070, 974169, 1576239, 2550408, 4126647, 6677055, 10803702, 17480757, 28284459, 45765216, 74049675, 119814891, 193864566, 313679457, 507544023, 821223480, 1328767503, 2149990983, 3478758486, 5628749469, 9107507955, 14736257424, 23843765379, 38580022803, 62423788182, 101003810985, 163427599167, 264431410152, 427859009319, 692290419471, 1120149428790},
						   {0, 1597, 1597, 3194, 4791, 7985, 12776, 20761, 33537, 54298, 87835, 142133, 229968, 372101, 602069, 974170, 1576239, 2550409, 4126648, 6677057, 10803705, 17480762, 28284467, 45765229, 74049696, 119814925, 193864621, 313679546, 507544167, 821223713, 1328767880, 2149991593, 3478759473, 5628751066, 9107510539, 14736261605, 23843772144, 38580033749, 62423805893, 101003839642, 163427645535, 264431485177, 427859130712, 692290615889, 1120149746601, 1812440362490},
						   {0, 2584, 2584, 5168, 7752, 12920, 20672, 33592, 54264, 87856, 142120, 229976, 372096, 602072, 974168, 1576240, 2550408, 4126648, 6677056, 10803704, 17480760, 28284464, 45765224, 74049688, 119814912, 193864600, 313679512, 507544112, 821223624, 1328767736, 2149991360, 3478759096, 5628750456, 9107509552, 14736260008, 23843769560, 38580029568, 62423799128, 101003828696, 163427627824, 264431456520, 427859084344, 692290540864, 1120149625208, 1812440166072, 2932589791280},
						   {0, 4181, 4181, 8362, 12543, 20905, 33448, 54353, 87801, 142154, 229955, 372109, 602064, 974173, 1576237, 2550410, 4126647, 6677057, 10803704, 17480761, 28284465, 45765226, 74049691, 119814917, 193864608, 313679525, 507544133, 821223658, 1328767791, 2149991449, 3478759240, 5628750689, 9107509929, 14736260618, 23843770547, 38580031165, 62423801712, 101003832877, 163427634589, 264431467466, 427859102055, 692290569521, 1120149671576, 1812440241097, 2932589912673, 4745030153770},
						   {0, 6765, 6765, 13530, 20295, 33825, 54120, 87945, 142065, 230010, 372075, 602085, 974160, 1576245, 2550405, 4126650, 6677055, 10803705, 17480760, 28284465, 45765225, 74049690, 119814915, 193864605, 313679520, 507544125, 821223645, 1328767770, 2149991415, 3478759185, 5628750600, 9107509785, 14736260385, 23843770170, 38580030555, 62423800725, 101003831280, 163427632005, 264431463285, 427859095290, 692290558575, 1120149653865, 1812440212440, 2932589866305, 4745030078745, 7677619945050},
						   {0, 10946, 10946, 21892, 32838, 54730, 87568, 142298, 229866, 372164, 602030, 974194, 1576224, 2550418, 4126642, 6677060, 10803702, 17480762, 28284464, 45765226, 74049690, 119814916, 193864606, 313679522, 507544128, 821223650, 1328767778, 2149991428, 3478759206, 5628750634, 9107509840, 14736260474, 23843770314, 38580030788, 62423801102, 101003831890, 163427632992, 264431464882, 427859097874, 692290562756, 1120149660630, 1812440223386, 2932589884016, 4745030107402, 7677619991418, 12422650098820},
						   {0, 17711, 17711, 35422, 53133, 88555, 141688, 230243, 371931, 602174, 974105, 1576279, 2550384, 4126663, 6677047, 10803710, 17480757, 28284467, 45765224, 74049691, 119814915, 193864606, 313679521, 507544127, 821223648, 1328767775, 2149991423, 3478759198, 5628750621, 9107509819, 14736260440, 23843770259, 38580030699, 62423800958, 101003831657, 163427632615, 264431464272, 427859096887, 692290561159, 1120149658046, 1812440219205, 2932589877251, 4745030096456, 7677619973707, 12422650070163, 20100270043870},
						   {0, 28657, 28657, 57314, 85971, 143285, 229256, 372541, 601797, 974338, 1576135, 2550473, 4126608, 6677081, 10803689, 17480770, 28284459, 45765229, 74049688, 119814917, 193864605, 313679522, 507544127, 821223649, 1328767776, 2149991425, 3478759201, 5628750626, 9107509827, 14736260453, 23843770280, 38580030733, 62423801013, 101003831746, 163427632759, 264431464505, 427859097264, 692290561769, 1120149659033, 1812440220802, 2932589879835, 4745030100637, 7677619980472, 12422650081109, 20100270061581, 32522920142690},
						   {0, 46368, 46368, 92736, 139104, 231840, 370944, 602784, 973728, 1576512, 2550240, 4126752, 6676992, 10803744, 17480736, 28284480, 45765216, 74049696, 119814912, 193864608, 313679520, 507544128, 821223648, 1328767776, 2149991424, 3478759200, 5628750624, 9107509824, 14736260448, 23843770272, 38580030720, 62423800992, 101003831712, 163427632704, 264431464416, 427859097120, 692290561536, 1120149658656, 1812440220192, 2932589878848, 4745030099040, 7677619977888, 12422650076928, 20100270054816, 32522920131744, 52623190186560},
						   {0, 75025, 75025, 150050, 225075, 375125, 600200, 975325, 1575525, 2550850, 4126375, 6677225, 10803600, 17480825, 28284425, 45765250, 74049675, 119814925, 193864600, 313679525, 507544125, 821223650, 1328767775, 2149991425, 3478759200, 5628750625, 9107509825, 14736260450, 23843770275, 38580030725, 62423801000, 101003831725, 163427632725, 264431464450, 427859097175, 692290561625, 1120149658800, 1812440220425, 2932589879225, 4745030099650, 7677619978875, 12422650078525, 20100270057400, 32522920135925, 52623190193325, 85146110329250},
						   {0, 121393, 121393, 242786, 364179, 606965, 971144, 1578109, 2549253, 4127362, 6676615, 10803977, 17480592, 28284569, 45765161, 74049730, 119814891, 193864621, 313679512, 507544133, 821223645, 1328767778, 2149991423, 3478759201, 5628750624, 9107509825, 14736260449, 23843770274, 38580030723, 62423800997, 101003831720, 163427632717, 264431464437, 427859097154, 692290561591, 1120149658745, 1812440220336, 2932589879081, 4745030099417, 7677619978498, 12422650077915, 20100270056413, 32522920134328, 52623190190741, 85146110325069, 137769300515810},
						   {0, 196418, 196418, 392836, 589254, 982090, 1571344, 2553434, 4124778, 6678212, 10802990, 17481202, 28284192, 45765394, 74049586, 119814980, 193864566, 313679546, 507544112, 821223658, 1328767770, 2149991428, 3478759198, 5628750626, 9107509824, 14736260450, 23843770274, 38580030724, 62423800998, 101003831722, 163427632720, 264431464442, 427859097162, 692290561604, 1120149658766, 1812440220370, 2932589879136, 4745030099506, 7677619978642, 12422650078148, 20100270056790, 32522920134938, 52623190191728, 85146110326666, 137769300518394, 222915410845060},
						   {0, 317811, 317811, 635622, 953433, 1589055, 2542488, 4131543, 6674031, 10805574, 17479605, 28285179, 45764784, 74049963, 119814747, 193864710, 313679457, 507544167, 821223624, 1328767791, 2149991415, 3478759206, 5628750621, 9107509827, 14736260448, 23843770275, 38580030723, 62423800998, 101003831721, 163427632719, 264431464440, 427859097159, 692290561599, 1120149658758, 1812440220357, 2932589879115, 4745030099472, 7677619978587, 12422650078059, 20100270056646, 32522920134705, 52623190191351, 85146110326056, 137769300517407, 222915410843463, 360684711360870},
						   {0, 514229, 514229, 1028458, 1542687, 2571145, 4113832, 6684977, 10798809, 17483786, 28282595, 45766381, 74048976, 119815357, 193864333, 313679690, 507544023, 821223713, 1328767736, 2149991449, 3478759185, 5628750634, 9107509819, 14736260453, 23843770272, 38580030725, 62423800997, 101003831722, 163427632719, 264431464441, 427859097160, 692290561601, 1120149658761, 1812440220362, 2932589879123, 4745030099485, 7677619978608, 12422650078093, 20100270056701, 32522920134794, 52623190191495, 85146110326289, 137769300517784, 222915410844073, 360684711361857, 583600122205930},
						   {0, 832040, 832040, 1664080, 2496120, 4160200, 6656320, 10816520, 17472840, 28289360, 45762200, 74051560, 119813760, 193865320, 313679080, 507544400, 821223480, 1328767880, 2149991360, 3478759240, 5628750600, 9107509840, 14736260440, 23843770280, 38580030720, 62423801000, 101003831720, 163427632720, 264431464440, 427859097160, 692290561600, 1120149658760, 1812440220360, 2932589879120, 4745030099480, 7677619978600, 12422650078080, 20100270056680, 32522920134760, 52623190191440, 85146110326200, 137769300517640, 222915410843840, 360684711361480, 583600122205320, 944284833566800},
						   {0, 1346269, 1346269, 2692538, 4038807, 6731345, 10770152, 17501497, 28271649, 45773146, 74044795, 119817941, 193862736, 313680677, 507543413, 821224090, 1328767503, 2149991593, 3478759096, 5628750689, 9107509785, 14736260474, 23843770259, 38580030733, 62423800992, 101003831725, 163427632717, 264431464442, 427859097159, 692290561601, 1120149658760, 1812440220361, 2932589879121, 4745030099482, 7677619978603, 12422650078085, 20100270056688, 32522920134773, 52623190191461, 85146110326234, 137769300517695, 222915410843929, 360684711361624, 583600122205553, 944284833567177, 1527884955772730},
						   {0, 2178309, 2178309, 4356618, 6534927, 10891545, 17426472, 28318017, 45744489, 74062506, 119806995, 193869501, 313676496, 507545997, 821222493, 1328768490, 2149990983, 3478759473, 5628750456, 9107509929, 14736260385, 23843770314, 38580030699, 62423801013, 101003831712, 163427632725, 264431464437, 427859097162, 692290561599, 1120149658761, 1812440220360, 2932589879121, 4745030099481, 7677619978602, 12422650078083, 20100270056685, 32522920134768, 52623190191453, 85146110326221, 137769300517674, 222915410843895, 360684711361569, 583600122205464, 944284833567033, 1527884955772497, 2472169789339530},
						   {0, 3524578, 3524578, 7049156, 10573734, 17622890, 28196624, 45819514, 74016138, 119835652, 193851790, 313687442, 507539232, 821226674, 1328765906, 2149992580, 3478758486, 5628751066, 9107509552, 14736260618, 23843770170, 38580030788, 62423800958, 101003831746, 163427632704, 264431464450, 427859097154, 692290561604, 1120149658758, 1812440220362, 2932589879120, 4745030099482, 7677619978602, 12422650078084, 20100270056686, 32522920134770, 52623190191456, 85146110326226, 137769300517682, 222915410843908, 360684711361590, 583600122205498, 944284833567088, 1527884955772586, 2472169789339674, 4000054745112260},
						   {0, 5702887, 5702887, 11405774, 17108661, 28514435, 45623096, 74137531, 119760627, 193898158, 313658785, 507556943, 821215728, 1328772671, 2149988399, 3478761070, 5628749469, 9107510539, 14736260008, 23843770547, 38580030555, 62423801102, 101003831657, 163427632759, 264431464416, 427859097175, 692290561591, 1120149658766, 1812440220357, 2932589879123, 4745030099480, 7677619978603, 12422650078083, 20100270056686, 32522920134769, 52623190191455, 85146110326224, 137769300517679, 222915410843903, 360684711361582, 583600122205485, 944284833567067, 1527884955772552, 2472169789339619, 4000054745112171, 6472224534451790},
						   {0, 9227465, 9227465, 18454930, 27682395, 46137325, 73819720, 119957045, 193776765, 313733810, 507510575, 821244385, 1328754960, 2149999345, 3478754305, 5628753650, 9107507955, 14736261605, 23843769560, 38580031165, 62423800725, 101003831890, 163427632615, 264431464505, 427859097120, 692290561625, 1120149658745, 1812440220370, 2932589879115, 4745030099485, 7677619978600, 12422650078085, 20100270056685, 32522920134770, 52623190191455, 85146110326225, 137769300517680, 222915410843905, 360684711361585, 583600122205490, 944284833567075, 1527884955772565, 2472169789339640, 4000054745112205, 6472224534451845, 10472279279564050},
						   {0, 14930352, 14930352, 29860704, 44791056, 74651760, 119442816, 194094576, 313537392, 507631968, 821169360, 1328801328, 2149970688, 3478772016, 5628742704, 9107514720, 14736257424, 23843772144, 38580029568, 62423801712, 101003831280, 163427632992, 264431464272, 427859097264, 692290561536, 1120149658800, 1812440220336, 2932589879136, 4745030099472, 7677619978608, 12422650078080, 20100270056688, 32522920134768, 52623190191456, 85146110326224, 137769300517680, 222915410843904, 360684711361584, 583600122205488, 944284833567072, 1527884955772560, 2472169789339632, 4000054745112192, 6472224534451824, 10472279279564016, 16944503814015840},
						   {0, 24157817, 24157817, 48315634, 72473451, 120789085, 193262536, 314051621, 507314157, 821365778, 1328679935, 2150045713, 3478725648, 5628771361, 9107497009, 14736268370, 23843765379, 38580033749, 62423799128, 101003832877, 163427632005, 264431464882, 427859096887, 692290561769, 1120149658656, 1812440220425, 2932589879081, 4745030099506, 7677619978587, 12422650078093, 20100270056680, 32522920134773, 52623190191453, 85146110326226, 137769300517679, 222915410843905, 360684711361584, 583600122205489, 944284833567073, 1527884955772562, 2472169789339635, 4000054745112197, 6472224534451832, 10472279279564029, 16944503814015861, 27416783093579890},
						   {0, 39088169, 39088169, 78176338, 117264507, 195440845, 312705352, 508146197, 820851549, 1328997746, 2149849295, 3478847041, 5628696336, 9107543377, 14736239713, 23843783090, 38580022803, 62423805893, 101003828696, 163427634589, 264431463285, 427859097874, 692290561159, 1120149659033, 1812440220192, 2932589879225, 4745030099417, 7677619978642, 12422650078059, 20100270056701, 32522920134760, 52623190191461, 85146110326221, 137769300517682, 222915410843903, 360684711361585, 583600122205488, 944284833567073, 1527884955772561, 2472169789339634, 4000054745112195, 6472224534451829, 10472279279564024, 16944503814015853, 27416783093579877, 44361286907595730},
						   {0, 63245986, 63245986, 126491972, 189737958, 316229930, 505967888, 822197818, 1328165706, 2150363524, 3478529230, 5628892754, 9107421984, 14736314738, 23843736722, 38580051460, 62423788182, 101003839642, 163427627824, 264431467466, 427859095290, 692290562756, 1120149658046, 1812440220802, 2932589878848, 4745030099650, 7677619978498, 12422650078148, 20100270056646, 32522920134794, 52623190191440, 85146110326234, 137769300517674, 222915410843908, 360684711361582, 583600122205490, 944284833567072, 1527884955772562, 2472169789339634, 4000054745112196, 6472224534451830, 10472279279564026, 16944503814015856, 27416783093579882, 44361286907595738, 71778070001175620},
						   {0, 102334155, 102334155, 204668310, 307002465, 511670775, 818673240, 1330344015, 2149017255, 3479361270, 5628378525, 9107739795, 14736118320, 23843858115, 38579976435, 62423834550, 101003810985, 163427645535, 264431456520, 427859102055, 692290558575, 1120149660630, 1812440219205, 2932589879835, 4745030099040, 7677619978875, 12422650077915, 20100270056790, 32522920134705, 52623190191495, 85146110326200, 137769300517695, 222915410843895, 360684711361590, 583600122205485, 944284833567075, 1527884955772560, 2472169789339635, 4000054745112195, 6472224534451830, 10472279279564025, 16944503814015855, 27416783093579880, 44361286907595735, 71778070001175615, 116139356908771350},
						   {0, 165580141, 165580141, 331160282, 496740423, 827900705, 1324641128, 2152541833, 3477182961, 5629724794, 9106907755, 14736632549, 23843540304, 38580172853, 62423713157, 101003886010, 163427599167, 264431485177, 427859084344, 692290569521, 1120149653865, 1812440223386, 2932589877251, 4745030100637, 7677619977888, 12422650078525, 20100270056413, 32522920134938, 52623190191351, 85146110326289, 137769300517640, 222915410843929, 360684711361569, 583600122205498, 944284833567067, 1527884955772565, 2472169789339632, 4000054745112197, 6472224534451829, 10472279279564026, 16944503814015855, 27416783093579881, 44361286907595736, 71778070001175617, 116139356908771353, 187917426909946970},
						   {0, 267914296, 267914296, 535828592, 803742888, 1339571480, 2143314368, 3482885848, 5626200216, 9109086064, 14735286280, 23844372344, 38579658624, 62424030968, 101003689592, 163427720560, 264431410152, 427859130712, 692290540864, 1120149671576, 1812440212440, 2932589884016, 4745030096456, 7677619980472, 12422650076928, 20100270057400, 32522920134328, 52623190191728, 85146110326056, 137769300517784, 222915410843840, 360684711361624, 583600122205464, 944284833567088, 1527884955772552, 2472169789339640, 4000054745112192, 6472224534451832, 10472279279564024, 16944503814015856, 27416783093579880, 44361286907595736, 71778070001175616, 116139356908771352, 187917426909946968, 304056783818718320},
						   {0, 433494437, 433494437, 866988874, 1300483311, 2167472185, 3467955496, 5635427681, 9103383177, 14738810858, 23842194035, 38581004893, 62423198928, 101004203821, 163427402749, 264431606570, 427859009319, 692290615889, 1120149625208, 1812440241097, 2932589866305, 4745030107402, 7677619973707, 12422650081109, 20100270054816, 32522920135925, 52623190190741, 85146110326666, 137769300517407, 222915410844073, 360684711361480, 583600122205553, 944284833567033, 1527884955772586, 2472169789339619, 4000054745112205, 6472224534451824, 10472279279564029, 16944503814015853, 27416783093579882, 44361286907595735, 71778070001175617, 116139356908771352, 187917426909946969, 304056783818718321, 491974210728665290},
						   {0, 701408733, 701408733, 1402817466, 2104226199, 3507043665, 5611269864, 9118313529, 14729583393, 23847896922, 38577480315, 62425377237, 101002857552, 163428234789, 264431092341, 427859327130, 692290419471, 1120149746601, 1812440166072, 2932589912673, 4745030078745, 7677619991418, 12422650070163, 20100270061581, 32522920131744, 52623190193325, 85146110325069, 137769300518394, 222915410843463, 360684711361857, 583600122205320, 944284833567177, 1527884955772497, 2472169789339674, 4000054745112171, 6472224534451845, 10472279279564016, 16944503814015861, 27416783093579877, 44361286907595738, 71778070001175615, 116139356908771353, 187917426909946968, 304056783818718321, 491974210728665289, 796030994547383610},
						   {0, 1134903170, 1134903170, 2269806340, 3404709510, 5674515850, 9079225360, 14753741210, 23832966570, 38586707780, 62419674350, 101006382130, 163426056480, 264432438610, 427858495090, 692290933700, 1120149428790, 1812440362490, 2932589791280, 4745030153770, 7677619945050, 12422650098820, 20100270043870, 32522920142690, 52623190186560, 85146110329250, 137769300515810, 222915410845060, 360684711360870, 583600122205930, 944284833566800, 1527884955772730, 2472169789339530, 4000054745112260, 6472224534451790, 10472279279564050, 16944503814015840, 27416783093579890, 44361286907595730, 71778070001175620, 116139356908771350, 187917426909946970, 304056783818718320, 491974210728665290, 796030994547383610, 1288005205276048900}};

bool isSumOfFib(long long n) {
	for(int i=0;i<N;++i) {
		for(int j=0;j<N;++j) {
			if( fibNums[i][j] == n )
				return true;
		}
	}

	return false;
}

int main()
{
	int t;
	long long number;

	scanf("%d",&t);
	while( t-- != 0 ) {
		scanf("%lld",&number);
		puts( isSumOfFib(number) ? "TAK" : "NIE" );
	}

	return 0;
}