Read problems statements in Mandarin Chinese  and Russian. 

Lira loves Linear Algebra and she is especially keen about matrix :).
Today, she learnt some properties about matrices, namely, she learnt about what the trace of a matrix is, as her teacher gave her many exercises for her to practice.
As we know she is pretty clever, she rapidly came up with some definitions of her own and devised a somewhat harder version of the problem initially proposed by her teacher.
Namely, she defines a Positive Invertible Integer Matrix as being an invertible 2x2 matrix composed only of positive (i.e. greater than 0) integer elements and whose determinant is greater than 0.
Now, she is interested in counting how many such matrices are there, such that their trace is equal to N .
It's your turn to solve Lira's problem :D

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. 

Each test case consist of single integer N, the trace of the matrix.

------ Output ------ 

For each test case, output a single line containing the number of Positive Invertible Integer Matrices such that their trace is equal to N and determinant is positive. 

Read here for additional info:
http://en.wikipedia.org/wiki/Trace_(linear_{algebra})
http://en.wikipedia.org/wiki/Determinant 

------ Constraints: ------ 

$1 ≤ T ≤ 50$
$3 ≤ N ≤ 2500$
 
----- Sample Input 1 ------ 
1
3
----- Sample Output 1 ------ 
2
----- explanation 1 ------ 
The only two matrices that exist with trace equal to 3 and that satisfy all the given conditions are:

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Number theory

Dynamic programming

Mathematics


Solutions:
a = [0, 0, 0, 2, 11, 30, 68, 124, 213, 330, 498, 698, 967, 1286, 1686, 2152, 2699, 3340, 4100, 4918, 5911, 6974, 8220, 9546, 11051, 12722, 14548, 16550, 18731, 21072, 23688, 26414, 29443, 32664, 36146, 39802, 43793, 47976, 52544, 57272, 62349, 67682, 73412, 79386, 85723, 92404, 99418, 106802, 114547, 122596, 131252, 140078, 149525, 159108, 169344, 179914, 191011, 202568, 214552, 226926, 239975, 253322, 267436, 281942, 296839, 312452, 328606, 345230, 362553, 380332, 398966, 417648, 437375, 457786, 478808, 500240, 522537, 545332, 569084, 593082, 618271, 643942, 670310, 697428, 725267, 754016, 783422, 813710, 844611, 876216, 909138, 942226, 976825, 1011858, 1047744, 1084658, 1122187, 1160828, 1200430, 1240816, 1282359, 1324238, 1367894, 1411792, 1457075, 1503044, 1550478, 1598410, 1647753, 1697626, 1749160, 1801192, 1854589, 1909012, 1964594, 2021162, 2078895, 2137780, 2197698, 2258586, 2320819, 2384300, 2449036, 2514968, 2581973, 2649926, 2719522, 2790000, 2862029, 2935256, 3010052, 3085168, 3162755, 3240750, 3320618, 3401552, 3483841, 3567500, 3652808, 3738934, 3827297, 3916204, 4006964, 4099166, 4192283, 4287438, 4384436, 4482120, 4581725, 4682234, 4784922, 4888738, 4994277, 5101528, 5210042, 5320148, 5431919, 5545698, 5660662, 5776826, 5895415, 6014812, 6137324, 6259616, 6385263, 6511822, 6640020, 6769934, 6901749, 7035038, 7170924, 7307720, 7446913, 7587352, 7730096, 7873958, 8019963, 8168492, 8318244, 8469406, 8623411, 8778102, 8936452, 9095856, 9256659, 9420004, 9585262, 9752484, 9921241, 10092186, 10266028, 10440754, 10617877, 10797376, 10978628, 11161994, 11347909, 11534510, 11724710, 11915970, 12110819, 12306162, 12504730, 12705006, 12908081, 13112580, 13319686, 13528720, 13740181, 13953626, 14170332, 14387640, 14609331, 14832276, 15057142, 15284314, 15514281, 15746158, 15981558, 16218248, 16457999, 16699020, 16943538, 17190562, 17438841, 17691272, 17944642, 18201414, 18460255, 18721304, 18986676, 19252224, 19521579, 19792476, 20068090, 20344200, 20623803, 20906158, 21191134, 21477198, 21766717, 22060086, 22356142, 22654072, 22954709, 23258276, 23564332, 23872914, 24185069, 24499148, 24817558, 25135592, 25459667, 25784746, 26113692, 26445136, 26779569, 27116514, 27456782, 27798992, 28145971, 28493934, 28845580, 29200176, 29557211, 29918712, 30282348, 30649572, 31019371, 31390296, 31767252, 32145278, 32528397, 32912894, 33300906, 33692204, 34086601, 34483954, 34884852, 35288296, 35695011, 36105178, 36519644, 36935686, 37356003, 37778914, 38205210, 38634230, 39067775, 39502892, 39944692, 40386938, 40832815, 41282652, 41736190, 42191456, 42651527, 43115510, 43581908, 44050718, 44525297, 45001840, 45483546, 45966900, 46454557, 46945166, 47439416, 47937606, 48439785, 48944378, 49454686, 49965658, 50481593, 51001858, 51525206, 52051602, 52583527, 53117046, 53655842, 54197260, 54741921, 55291862, 55844554, 56401298, 56961853, 57526152, 58094964, 58667166, 59242843, 59821464, 60405890, 60991778, 61584575, 62180270, 62778896, 63381888, 63987921, 64599400, 65214736, 65833062, 66457297, 67081930, 67715838, 68348230, 68988899, 69631316, 70279148, 70930252, 71586065, 72243962, 72908808, 73576430, 74248519, 74924616, 75605834, 76290664, 76979311, 77672078, 78369822, 79069828, 79776409, 80486302, 81201346, 81920542, 82644159, 83370414, 84103088, 84839294, 85579369, 86324532, 87074746, 87827998, 88586629, 89348526, 90116528, 90888734, 91663777, 92445336, 93230678, 94018836, 94815509, 95612922, 96417738, 97225308, 98037047, 98856154, 99677908, 100504478, 101336099, 102171254, 103013614, 103855762, 104708317, 105564182, 106423834, 107287506, 108157059, 109029790, 109910626, 110792688, 111682025, 112574662, 113474590, 114377398, 115285221, 116197444, 117115782, 118037818, 118965745, 119897754, 120838070, 121779080, 122728061, 123679566, 124638144, 125600704, 126569139, 127541868, 128518974, 129500712, 130491517, 131485030, 132482328, 133488342, 134495755, 135511478, 136530262, 137553534, 138583981, 139619446, 140661378, 141703560, 142755221, 143811462, 144874050, 145941022, 147012905, 148092262, 149174954, 150260024, 151356743, 152454192, 153561000, 154669990, 155786575, 156906686, 158033342, 159166818, 160303427, 161443468, 162594826, 163748370, 164910073, 166074520, 167246994, 168423438, 169602639, 170792444, 171986538, 173186252, 174391333, 175598680, 176818056, 178040050, 179268125, 180501724, 181742554, 182985148, 184238501, 185493018, 186759822, 188025982, 189301055, 190581174, 191867190, 193158790, 194458907, 195762956, 197071164, 198387120, 199708069, 201039060, 202371664, 203712444, 205059143, 206409224, 207768856, 209132002, 210504929, 211880510, 213263636, 214649838, 216046177, 217446756, 218855082, 220268258, 221687321, 223113338, 224548656, 225985454, 227431379, 228880116, 230338668, 231802086, 233269849, 234747036, 236231318, 237722018, 239215949, 240717184, 242228516, 243738840, 245262667, 246790782, 248323846, 249864732, 251412165, 252965580, 254526468, 256092104, 257666815, 259244500, 260835254, 262424874, 264027619, 265632278, 267246228, 268864828, 270489895, 272123992, 273764986, 275412086, 277067061, 278724662, 280391028, 282067524, 283746365, 285433312, 287129310, 288827186, 290536339, 292250020, 293973670, 295702354, 297436473, 299178726, 300930074, 302684776, 304449891, 306219104, 307996748, 309779974, 311571477, 313369166, 315176850, 316988172, 318810537, 320636236, 322468884, 324307916, 326157353, 328014764, 329875024, 331746328, 333624051, 335508710, 337397338, 339298984, 341205001, 343116202, 345039408, 346963438, 348901569, 350845460, 352794182, 354749736, 356714083, 358687200, 360668536, 362653870, 364651389, 366649324, 368664446, 370679744, 372701611, 374733520, 376775436, 378820702, 380876509, 382936512, 385010922, 387084834, 389172037, 391263076, 393367846, 395471312, 397588769, 399712404, 401842982, 403982200, 406126987, 408281508, 410448292, 412617570, 414793571, 416981348, 419175272, 421373912, 423584839, 425800040, 428029644, 430256894, 432501035, 434750296, 437006732, 439272450, 441544327, 443824670, 446113662, 448411034, 450718425, 453029596, 455350822, 457679864, 460014849, 462362480, 464717466, 467080272, 469448201, 471824596, 474212986, 476604132, 479011299, 481423624, 483840940, 486268358, 488704367, 491148790, 493600924, 496060322, 498531761, 501008778, 503494412, 505988716, 508492357, 511003812, 513524648, 516047398, 518587813, 521128854, 523689946, 526246472, 528821727, 531398682, 533987170, 536583478, 539186353, 541802316, 544423008, 547052634, 549692627, 552340926, 554997748, 557664118, 560337467, 563020802, 565715378, 568412820, 571126661, 573839802, 576569548, 579301890, 582045719, 584801206, 587563708, 590337216, 593114767, 595902836, 598705514, 601508978, 604327027, 607148012, 609982490, 612824638, 615679551, 618536958, 621410036, 624289374, 627174911, 630072808, 632980260, 635892378, 638818645, 641755490, 644694706, 647646972, 650607287, 653581758, 656558228, 659548220, 662548787, 665548964, 668570678, 671594526, 674631533, 677675112, 680732244, 683796734, 686868031, 689947500, 693042844, 696140504, 699254331, 702369880, 705501472, 708640580, 711790839, 714949134, 718118330, 721291474, 724476453, 727673410, 730883520, 734097620, 737324373, 740556698, 743800598, 747055330, 750318689, 753592610, 756876630, 760169716, 763473289, 766784718, 770106276, 773437386, 776779707, 780131024, 783495480, 786861964, 790250199, 793637936, 797039958, 800448884, 803868849, 807303256, 810742864, 814194918, 817655053, 821121610, 824611232, 828096252, 831597915, 835110088, 838631342, 842160022, 845704267, 849252254, 852816544, 856388464, 859969323, 863562352, 867168932, 870778702, 874401559, 878035846, 881676318, 885334326, 888992017, 892666750, 896357264, 900049422, 903757939, 907471682, 911199010, 914936260, 918682817, 922439478, 926210384, 929983218, 933776039, 937570996, 941383018, 945205334, 949036697, 952878746, 956730292, 960592888, 964469325, 968351264, 972250286, 976145852, 980064791, 983996386, 987932584, 991882152, 995838883, 999806592, 1003790136, 1007778282, 1011782813, 1015796136, 1019819884, 1023854844, 1027902277, 1031953412, 1036027392, 1040102732, 1044189675, 1048288450, 1052402564, 1056520174, 1060658841, 1064801636, 1068956950, 1073119980, 1077298371, 1081487756, 1085687996, 1089893636, 1094120277, 1098352082, 1102597034, 1106849860, 1111115023, 1115391518, 1119682030, 1123978892, 1128292289, 1132612714, 1136949728, 1141292718, 1145649599, 1150016402, 1154396576, 1158783982, 1163187149, 1167602734, 1172020234, 1176456968, 1180899797, 1185360856, 1189833246, 1194319274, 1198810907, 1203313700, 1207831740, 1212353614, 1216895057, 1221444284, 1226014214, 1230578102, 1235167289, 1239763496, 1244373010, 1248993656, 1253623569, 1258269710, 1262927266, 1267588704, 1272270609, 1276958248, 1281666744, 1286377248, 1291097745, 1295842104, 1300589184, 1305354312, 1310126795, 1314907974, 1319708374, 1324516372, 1329339497, 1334171022, 1339014078, 1343872374, 1348741681, 1353621780, 1358512436, 1363423074, 1368338449, 1373257390, 1378207372, 1383155126, 1388127455, 1393099286, 1398093280, 1403092934, 1408109365, 1413130942, 1418174714, 1423222478, 1428286515, 1433359394, 1438446994, 1443546930, 1448660839, 1453784036, 1458917338, 1464065556, 1469229427, 1474397428, 1479594284, 1484789650, 1489997613, 1495224446, 1500461612, 1505704910, 1510967135, 1516239952, 1521528614, 1526821424, 1532132499, 1537460138, 1542796822, 1548141222, 1553506025, 1558878236, 1564268904, 1569660156, 1575078443, 1580502582, 1585936358, 1591389054, 1596851039, 1602326250, 1607812792, 1613319396, 1618834379, 1624355678, 1629897204, 1635450492, 1641017161, 1646591046, 1652187168, 1657788330, 1663400577, 1669034962, 1674677622, 1680334198, 1686008379, 1691683576, 1697377740, 1703087876, 1708808603, 1714543602, 1720288930, 1726049318, 1731826991, 1737608408, 1743415158, 1749225376, 1755048583, 1760886392, 1766742024, 1772607610, 1778487249, 1784383054, 1790286670, 1796201350, 1802133113, 1808077322, 1814042028, 1820013252, 1825999833, 1831996446, 1838012158, 1844035588, 1850074357, 1856130064, 1862198538, 1868269978, 1874366383, 1880473160, 1886596954, 1892727994, 1898876493, 1905034940, 1911214000, 1917397746, 1923603787, 1929817982, 1936046480, 1942290124, 1948545619, 1954817070, 1961104286, 1967395982, 1973712645, 1980026286, 1986375114, 1992722426, 1999092851, 2005481704, 2011870736, 2018277368, 2024699573, 2031133808, 2037590422, 2044048790, 2050527229, 2057017486, 2063529198, 2070043604, 2076583171, 2083130478, 2089688356, 2096264324, 2102852661, 2109455504, 2116083104, 2122710044, 2129356929, 2136018078, 2142694792, 2149384854, 2156084869, 2162806546, 2169538172, 2176280250, 2183042587, 2189814282, 2196605140, 2203411088, 2210226163, 2217055862, 2223904854, 2230766750, 2237641939, 2244531312, 2251441318, 2258352708, 2265287467, 2272234380, 2279192438, 2286173164, 2293162229, 2300170538, 2307188698, 2314219424, 2321272981, 2328334160, 2335421796, 2342504148, 2349616301, 2356738252, 2363876262, 2371026402, 2378198699, 2385371026, 2392571952, 2399778344, 2407010531, 2414247088, 2421501128, 2428774424, 2436053759, 2443357608, 2450671678, 2458002960, 2465350571, 2472704628, 2480082930, 2487464266, 2494875811, 2502291156, 2509728110, 2517178886, 2524644481, 2532115854, 2539622234, 2547123884, 2554648493, 2562189102, 2569746008, 2577318444, 2584902065, 2592504332, 2600118002, 2607739420, 2615389337, 2623050010, 2630737830, 2638423496, 2646131407, 2653856144, 2661595812, 2669343860, 2677114075, 2684898404, 2692696100, 2700507324, 2708346097, 2716188140, 2724048602, 2731924626, 2739824367, 2747727094, 2755653304, 2763581664, 2771544989, 2779511986, 2787497436, 2795499146, 2803509087, 2811547272, 2819593068, 2827667396, 2835741215, 2843832460, 2851946376, 2860071672, 2868212001, 2876371834, 2884550162, 2892738262, 2900943289, 2909159498, 2917402436, 2925649046, 2933916555, 2942200394, 2950508912, 2958826128, 2967157705, 2975504826, 2983871422, 2992248076, 3000647317, 3009060108, 3017492078, 3025931462, 3034391409, 3042869564, 3051368278, 3059869744, 3068395075, 3076940398, 3085494774, 3094070474, 3102663193, 3111265392, 3119887434, 3128531510, 3137186311, 3145854658, 3154543194, 3163245048, 3171969921, 3180702228, 3189458186, 3198221820, 3207007835, 3215814866, 3224635958, 3233466032, 3242320911, 3251186286, 3260074784, 3268970542, 3277888485, 3286822254, 3295778194, 3304741224, 3313725247, 3322728056, 3331747736, 3340774756, 3349831943, 3358891346, 3367981834, 3377072366, 3386200661, 3395330854, 3404481132, 3413647434, 3422825597, 3432035886, 3441251794, 3450486860, 3459744617, 3469005996, 3478294182, 3487597762, 3496913429, 3506255126, 3515603688, 3524971112, 3534364383, 3543753068, 3553187882, 3562625586, 3572078889, 3581552838, 3591043530, 3600553214, 3610077505, 3619612176, 3629171058, 3638742880, 3648329983, 3657942756, 3667574058, 3677221490, 3686886575, 3696554262, 3706254602, 3715967352, 3725696121, 3735442280, 3745213208, 3754990936, 3764797299, 3774607422, 3784444000, 3794295452, 3804162935, 3814051642, 3823958468, 3833870402, 3843819521, 3853774946, 3863752794, 3873736580, 3883749599, 3893774886, 3903828796, 3913888122, 3923962065, 3934062880, 3944180908, 3954306946, 3964460997, 3974636338, 3984814952, 3995026492, 4005244173, 4015484746, 4025739016, 4036013920, 4046309745, 4056611540, 4066951402, 4077294908, 4087660523, 4098044754, 4108444296, 4118861316, 4129291725, 4139749672, 4150226260, 4160712312, 4171228123, 4181752636, 4192301648, 4202848788, 4213440203, 4224040930, 4234655616, 4245280674, 4255941459, 4266604244, 4277303624, 4288017828, 4298739445, 4309482642, 4320249284, 4331024952, 4341825263, 4352638676, 4363486228, 4374330008, 4385202637, 4396094768, 4407007128, 4417931138, 4428880517, 4439844890, 4450827200, 4461826768, 4472853827, 4483885734, 4494948096, 4506023292, 4517116817, 4528234382, 4539356806, 4550515056, 4561679877, 4572857356, 4584071888, 4595292890, 4606542993, 4617802410, 4629085510, 4640386594, 4651700381, 4663033888, 4674397298, 4685766306, 4697166731, 4708567286, 4720008006, 4731456334, 4742925135, 4754417472, 4765923050, 4777442572, 4788991157, 4800552188, 4812140932, 4823737882, 4835359215, 4846996330, 4858659238, 4870332442, 4882036813, 4893755386, 4905484792, 4917236172, 4929001053, 4940804200, 4952620652, 4964450976, 4976298095, 4988169502, 5000057552, 5011968356, 5023894541, 5035835648, 5047809216, 5059784460, 5071795863, 5083816234, 5095864934, 5107927060, 5120007965, 5132105290, 5144237132, 5156372832, 5168537731, 5180716510, 5192902448, 5205131122, 5217359843, 5229627736, 5241907206, 5254201766, 5266518501, 5278841946, 5291218752, 5303572548, 5315983379, 5328394754, 5340830426, 5353285678, 5365764123, 5378255520, 5390763990, 5403296500, 5415855413, 5428421548, 5441022362, 5453628856, 5466260927, 5478916122, 5491593708, 5504280034, 5516995733, 5529726564, 5542484984, 5555252230, 5568048879, 5580859282, 5593691916, 5606546944, 5619411103, 5632308312, 5645224318, 5658148320, 5671109461, 5684082056, 5697078664, 5710093978, 5723124395, 5736171788, 5749250110, 5762342560, 5775466619, 5788599392, 5801759552, 5814923566, 5828123773, 5841341812, 5854584392, 5867833968, 5881112787, 5894413690, 5907737418, 5921064822, 5934435543, 5947810364, 5961209364, 5974627188, 5988079583, 6001535090, 6015019086, 6028522420, 6042046305, 6055593062, 6069155484, 6082744716, 6096353467, 6109981702, 6123625354, 6137303534, 6150980725, 6164694554, 6178427180, 6192182712, 6205959849, 6219740820, 6233563810, 6247394634, 6261249869, 6275132292, 6289027520, 6302948346, 6316884703, 6330838464, 6344831974, 6358833876, 6372863285, 6386902792, 6400976138, 6415058044, 6429161209, 6443295864, 6457447262, 6471612314, 6485795827, 6500015886, 6514256296, 6528514510, 6542796133, 6557091444, 6571411556, 6585752098, 6600116623, 6614498638, 6628912074, 6643320358, 6657779863, 6672240586, 6686742416, 6701249562, 6715783261, 6730332980, 6744915450, 6759501228, 6774141795, 6788765402, 6803437928, 6818117324, 6832817799, 6847546144, 6862306472, 6877076088, 6891861455, 6906672550, 6921508406, 6936360110, 6951238091, 6966152740, 6981067016, 6996006722, 7010974505, 7025962836, 7040976768, 7056000262, 7071057471, 7086122786, 7101225682, 7116336376, 7131484837, 7146641742, 7161824410, 7177031456, 7192258125, 7207510684, 7222788556, 7238077116, 7253396549, 7268724944, 7284089646, 7299466810, 7314872037, 7330299190, 7345747968, 7361210018, 7376714765, 7392226006, 7407761534, 7423320360, 7438901823, 7454497872, 7470135622, 7485783456, 7501453705, 7517137984, 7532861902, 7548588772, 7564348613, 7580136504, 7595938332, 7611769638, 7627615027, 7643491018, 7659383706, 7675287472, 7691235231, 7707200636, 7723182276, 7739191588, 7755218183, 7771271536, 7787351162, 7803446452, 7819552329, 7835699892, 7851874882, 7868043894, 7884270609, 7900500194, 7916755054, 7933033936, 7949328199, 7965654984, 7981996938, 7998373306, 8014764355, 8031170000, 8047620492, 8064088702, 8080567459, 8097070614, 8113600314, 8130151704, 8146734195, 8163313906, 8179957184, 8196591222, 8213260903, 8229945606, 8246662854, 8263400030, 8280166991, 8296947394, 8313753072, 8330576036, 8347428617, 8364303778, 8381198684, 8398129274, 8415075903, 8432036870, 8449027290, 8466044390, 8483091213, 8500147402, 8517238056, 8534338100, 8551478059, 8568632332, 8585806624, 8603003904, 8620236761, 8637484664, 8654756228, 8672049078, 8689371021, 8706707828, 8724084558, 8741464716, 8758869845, 8776315872, 8793786478, 8811261542, 8828776297, 8846299826, 8863866972, 8881438166, 8899038141, 8916670780, 8934316064, 8951985032, 8969688235, 8987401792, 9005154004, 9022920212, 9040716837, 9058525756, 9076378884, 9094232466, 9112131607, 9130040664, 9147976436, 9165935286, 9183914635, 9201915412, 9219960668, 9238011710, 9256096289, 9274197982, 9292332054, 9310479906, 9328651563, 9346860410, 9365082730, 9383325102, 9401605173, 9419897462, 9438215878, 9456569852, 9474936963, 9493338050, 9511752600, 9530196170, 9548663989, 9567153882, 9585670192, 9604202160, 9622766037, 9641361308, 9659975268, 9678607498, 9697283647, 9715960670, 9734678656, 9753394090, 9772168013, 9790952606, 9809767222, 9828600080, 9847457497, 9866335658, 9885246928, 9904181660, 9923134041, 9942115358, 9961127538, 9980143916, 9999212883, 10018299334, 10037394762, 10056521814, 10075672885, 10094858354, 10114071712, 10133292404, 10152551249, 10171823716, 10191141344, 10210454996, 10229810327, 10249191438, 10268593014, 10288023408, 10307477751, 10326957710, 10346466062, 10365988134, 10385544293, 10405112618, 10424729834, 10444357406, 10464007713, 10483688728, 10503389540, 10523120972, 10542859943, 10562647566, 10582460418, 10602297632, 10622141839, 10642032142, 10661942614, 10681870766, 10701827929, 10721796916, 10741829828, 10761839592, 10781904345, 10801984338, 10822103090, 10842234270, 10862394213, 10882577588, 10902795876, 10923021046, 10943291315, 10963574444, 10983892294, 11004218694, 11024594431, 11044992220, 11065402084, 11085847880, 11106315841, 11126791342, 11147317096, 11167860636, 11188442783, 11209034778, 11229648802, 11250293976, 11270972865, 11291669372, 11312395298, 11333148526, 11353922653, 11374722580, 11395558206, 11416411576, 11437293557, 11458189896, 11479128746, 11500082586, 11521063591, 11542074872, 11563129804, 11584179460, 11605270381, 11626386488, 11647523330, 11668688458, 11689879179, 11711100370, 11732346128, 11753615846, 11774915977, 11796234228, 11817593764, 11838968516, 11860372937, 11881795858, 11903260776, 11924731368, 11946240101, 11967775622, 11989344036, 12010914006, 12032536895, 12054183772, 12075844670, 12097541070, 12119261983, 12141007596, 12162784930, 12184566690, 12206406107, 12228252614, 12250122580, 12272044010, 12293972345, 12315923116, 12337910366, 12359928610, 12381971157, 12404020572, 12426129422, 12448240350, 12470394811, 12492562516, 12514758184, 12536990520, 12559230039, 12581515318, 12603823728, 12626160400, 12648531997, 12670895832, 12693325334, 12715752434, 12738229191, 12760720940, 12783246232, 12805794472, 12828372863, 12850982004, 12873613496, 12896266106, 12918945325, 12941663296, 12964396994, 12987167764, 13009959455, 13032777670, 13055640356, 13078484158, 13101391487, 13124322864, 13147296126, 13170270528, 13193288217, 13216322512, 13239395578, 13262486492, 13285600859, 13308751950, 13331933228, 13355130312, 13378363525, 13401606654, 13424905814, 13448225050, 13471555571, 13494918234, 13518325980, 13541731566, 13565201927, 13588672056, 13612170438, 13635710296, 13659267843, 13682857958, 13706470216, 13730119430, 13753797521, 13777494144, 13801223470, 13824972750, 13848759985, 13872571514, 13896411188, 13920260568, 13944169249, 13968083300, 13992041940, 14016016638, 14040025735, 14064060506, 14088130430, 14112214174, 14136326211, 14160471100, 14184649166, 14208847684, 14233077947, 14257330580, 14281629678, 14305937202, 14330282399, 14354642572, 14379058808, 14403477800, 14427933293, 14452422320, 14476924334, 14501468336, 14526031525, 14550611826, 14575258960, 14599915764, 14624590353, 14649307726, 14674036560, 14698808100, 14723611153, 14748418166, 14773282134, 14798143938, 14823056561, 14847997872, 14872970836, 14897963804, 14922989853, 14948043436, 14973115476, 14998224332, 15023363785, 15048534572, 15073727448, 15098946162, 15124194037, 15149491292, 15174785390, 15200133970, 15225491451, 15250875116, 15276311618, 15301752072, 15327253689, 15352765076, 15378306070, 15403875638, 15429461667, 15455099622, 15480752478, 15506424248, 15532151343, 15557884500, 15583671346, 15609456626, 15635278941, 15661152350, 15687039060, 15712943794, 15738900857, 15764865016, 15790891834, 15816900186, 15842973423, 15869058628, 15895181784, 15921335458, 15947518869, 15973726224, 15999955134, 16026219464, 16052512879, 16078844830, 16105199162, 16131588250, 16158006287, 16184442692, 16210919090, 16237407364, 16263957085, 16290514354, 16317105364, 16343709892, 16370373971, 16397053922, 16423749906, 16450495500, 16477259903, 16504049234, 16530895922, 16557734408, 16584638761, 16611534976, 16638490382, 16665474124, 16692462689, 16719495984, 16746573778, 16773669214, 16800781595, 16827931674, 16855132496, 16882331206, 16909587021, 16936851538, 16964163616, 16991490290, 17018854213, 17046239568, 17073664784, 17101127704, 17128608743, 17156104042, 17183663168, 17211234562, 17238835951, 17266464770, 17294146488, 17321820196, 17349548331, 17377295416, 17405098964, 17432899814, 17460747943, 17488620662, 17516521618, 17544450448, 17572425447, 17600424912, 17628442122, 17656489986, 17684583923, 17712696444, 17740850230, 17769033680, 17797240639, 17825476118, 17853738104, 17882043836, 17910372801, 17938741918, 17967130214, 17995549806, 18023995317, 18052479814, 18080998176, 18109534864, 18138116441, 18166711096, 18195359370, 18224006588, 18252715047, 18281440374, 18310206524, 18338980964, 18367813869, 18396668104, 18425549136, 18454468966, 18483398125, 18512374114, 18541387558, 18570404150, 18599486567, 18628592906, 18657703644, 18686859232, 18716046853, 18745279774, 18774527482, 18803818674, 18833145303, 18862478966, 18891859618, 18921264244, 18950697327, 18980169810, 19009667936, 19039205800, 19068767351, 19098357214, 19128001662, 19157639736, 19187337709, 19217050890, 19246809278, 19276589068, 19306412337, 19336240588, 19366131864, 19396026832, 19425958873, 19455938600, 19485944316, 19515986918, 19546043477, 19576132726, 19606263326, 19636431128, 19666609365, 19696834394, 19727104970, 19757353614, 19787701785, 19818040942, 19848429620, 19878829056, 19909273441, 19939761128, 19970275822, 20000795696, 20031376997, 20061975182, 20092600638, 20123267014, 20153960463, 20184710080, 20215464924, 20246254032, 20277085067, 20307927424, 20338826526, 20369735954, 20400704429, 20431680344, 20462712824, 20493755800, 20524842691, 20555932006, 20587086902, 20618265034, 20649470177, 20680709572, 20711997328, 20743295138, 20774640263, 20806004856, 20837411096, 20868837110, 20900293333, 20931786142, 20963341648, 20994901062, 21026482153, 21058124702, 21089778936, 21121473748, 21153202421, 21184959842, 21216751208, 21248561574, 21280419055, 21312299434, 21344228444, 21376177872, 21408172329, 21440178784, 21472231412, 21504305276, 21536430445, 21568572538, 21600756848, 21632962082, 21665200653, 21697479592, 21729800518, 21762150104, 21794517499, 21826929924, 21859367972, 21891837396, 21924342881, 21956891346, 21989463742, 22022066148, 22054703515, 22087374828, 22120072666, 22152827802, 22185583989, 22218369222, 22251223676, 22284083800, 22317003671, 22349930050, 22382893566, 22415888758, 22448928827, 22482002710, 22515097314, 22548220344, 22581409651, 22614580132, 22647835194, 22681080768, 22714386301, 22747719762, 22781091458, 22814485296, 22847925521, 22881375740, 22914889334, 22948412082, 22981987341, 23015588956, 23049215580, 23082866676, 23116574277, 23150316704, 23184063670, 23217861044, 23251693689, 23285546546, 23319464186, 23353413406, 23387373951, 23421373318, 23455404876, 23489469900, 23523570055, 23557708714, 23591878154, 23626076336, 23660314657, 23694578900, 23728881648, 23763219812, 23797592885, 23831989974, 23866440090, 23900902530, 23935425443, 23969948060, 24004530098, 24039130364, 24073761697, 24108443134, 24143155988, 24177905376, 24212695275, 24247484040, 24282340990, 24317210598, 24352137889, 24387076928, 24422063206, 24457072792, 24492119935, 24527206344, 24562329910, 24597473268, 24632662189, 24667875578, 24703139552, 24738429770, 24773751911, 24809101090, 24844497316, 24879931178, 24915382113, 24950868552, 24986418640, 25021963892, 25057576457, 25093191060, 25128882680, 25164573576, 25200304261, 25236074556, 25271888990, 25307716812, 25343599443, 25379494642, 25415444250, 25451432394, 25487422517, 25523485744, 25559560472, 25595677296, 25631832535, 25668014074, 25704238576, 25740473940, 25776781233, 25813097992, 25849462522, 25885862050, 25922292871, 25958750250, 25995244404, 26031769900, 26068339841, 26104949822, 26141570498, 26178260834, 26214967497, 26251713234, 26288500116, 26325297518, 26362161505, 26399023274, 26435956496, 26472901262, 26509899053, 26546916512, 26583976300, 26621058530, 26658178401, 26695366964, 26732562478, 26769792688, 26807069131, 26844352060, 26881712512, 26919083490, 26956495377, 26993943104, 27031429818, 27068922558, 27106486265, 27144064390, 27181708024, 27219369872, 27257048349, 27294782010, 27332558482, 27370349612, 27408176237, 27446051340, 27483962544, 27521888684, 27559862781, 27597883870, 27635942300, 27674036422, 27712155453, 27750318000, 27788508500, 27826719644, 27864989115, 27903280246, 27941630410, 27979988616, 28018398369, 28056846838, 28095317506, 28133833890, 28172384151, 28210963240, 28249590004, 28288243646, 28326951403, 28365666962, 28404447892, 28443239914, 28482065093, 28520952318, 28559867844, 28598813120, 28637783477, 28676790442, 28715864554, 28754936440, 28794079573, 28833240452, 28872441752, 28911670514, 28950953491, 28990247594, 29029604862, 29068968486, 29108379923, 29147830628, 29187338384, 29226838420, 29266438961, 29306021590, 29345642418, 29385319430, 29425026497, 29464771352, 29504556500, 29544368818, 29584229615, 29624113694, 29664035752, 29703999968, 29744000851, 29784050836, 29824106944, 29864194866, 29904365393, 29944525240, 29984774644, 30025036222, 30065303909, 30105644886, 30146018242, 30186402768, 30226854249, 30267324378, 30307852176, 30348384192, 30388959193, 30429602642, 30470267284, 30510968386, 30551705975, 30592462588, 30633275182, 30674108380, 30715002867, 30755925012, 30796892560, 30837867184, 30878893491, 30919979362, 30961073922, 31002212626, 31043409001, 31084616424, 31125884168, 31167156566, 31208485157, 31249843792, 31291264530, 31332690232, 31374164615, 31415673140, 31457231434, 31498818978, 31540464387, 31582110194, 31623820450, 31665556220, 31707339699, 31749152170, 31790992178, 31832896552, 31874825979, 31916765322, 31958784276, 32000800204, 32042896931, 32084994136, 32127151474, 32169342044, 32211571521, 32253838444, 32296131360, 32338469650, 32380837031, 32423268800, 32465724690, 32508217744, 32550736097, 32593318632, 32635903024, 32678556708, 32721226259, 32763948030, 32806709878, 32849478660, 32892340257, 32935197744, 32978112642, 33021041010, 33064031575, 33107048486, 33150116138, 33193204452, 33236338661, 33279515518, 33322732668, 33365987512, 33409254183, 33452585598, 33495954966, 33539369830, 33582811939, 33626269714, 33669799540, 33713341902, 33756937901, 33800578504, 33844238068, 33887955796, 33931699859, 33975479128, 34019300774, 34063169634, 34107069375, 34151003346, 34195006626, 34238999882, 34283063915, 34327145264, 34371295780, 34415434136, 34459653165, 34503884880, 34548202428, 34592509102, 34636878789, 34681283850, 34725735624, 34770193946, 34814716337, 34859263280, 34903871430, 34948492262, 34993176971, 35037883380, 35082618080, 35127427896, 35172239553, 35217112242, 35262023698, 35306965738, 35351949141, 35396971286, 35442048274, 35487125012, 35532273341, 35577442954, 35622671628, 35667936540, 35713215171, 35758549622, 35803936994, 35849329914, 35894783061, 35940278442, 35985808660, 36031380044, 36076994073, 36122628006, 36168336746, 36214050002, 36259825493, 36305618022, 36351463320, 36397335366, 36443278941, 36489242850, 36535233644, 36581274504, 36627343961, 36673465620, 36719630852, 36765827488, 36812076035]
import sys
for j in range(int(sys.stdin.readline())):
	print(a[int(sys.stdin.readline())])


import sys
result = {3: 2, 4: 11, 5: 30, 6: 68, 7: 124, 8: 213, 9: 330, 10: 498, 11: 698, 12: 967, 13: 1286, 14: 1686, 15: 2152, 16: 2699, 17: 3340, 18: 4100, 19: 4918, 20: 5911, 21: 6974, 22: 8220, 23: 9546, 24: 11051, 25: 12722, 26: 14548, 27: 16550, 28: 18731, 29: 21072, 30: 23688, 31: 26414, 32: 29443, 33: 32664, 34: 36146, 35: 39802, 36: 43793, 37: 47976, 38: 52544, 39: 57272, 40: 62349, 41: 67682, 42: 73412, 43: 79386, 44: 85723, 45: 92404, 46: 99418, 47: 106802, 48: 114547, 49: 122596, 50: 131252, 51: 140078, 52: 149525, 53: 159108, 54: 169344, 55: 179914, 56: 191011, 57: 202568, 58: 214552, 59: 226926, 60: 239975, 61: 253322, 62: 267436, 63: 281942, 64: 296839, 65: 312452, 66: 328606, 67: 345230, 68: 362553, 69: 380332, 70: 398966, 71: 417648, 72: 437375, 73: 457786, 74: 478808, 75: 500240, 76: 522537, 77: 545332, 78: 569084, 79: 593082, 80: 618271, 81: 643942, 82: 670310, 83: 697428, 84: 725267, 85: 754016, 86: 783422, 87: 813710, 88: 844611, 89: 876216, 90: 909138, 91: 942226, 92: 976825, 93: 1011858, 94: 1047744, 95: 1084658, 96: 1122187, 97: 1160828, 98: 1200430, 99: 1240816, 100: 1282359, 101: 1324238, 102: 1367894, 103: 1411792, 104: 1457075, 105: 1503044, 106: 1550478, 107: 1598410, 108: 1647753, 109: 1697626, 110: 1749160, 111: 1801192, 112: 1854589, 113: 1909012, 114: 1964594, 115: 2021162, 116: 2078895, 117: 2137780, 118: 2197698, 119: 2258586, 120: 2320819, 121: 2384300, 122: 2449036, 123: 2514968, 124: 2581973, 125: 2649926, 126: 2719522, 127: 2790000, 128: 2862029, 129: 2935256, 130: 3010052, 131: 3085168, 132: 3162755, 133: 3240750, 134: 3320618, 135: 3401552, 136: 3483841, 137: 3567500, 138: 3652808, 139: 3738934, 140: 3827297, 141: 3916204, 142: 4006964, 143: 4099166, 144: 4192283, 145: 4287438, 146: 4384436, 147: 4482120, 148: 4581725, 149: 4682234, 150: 4784922, 151: 4888738, 152: 4994277, 153: 5101528, 154: 5210042, 155: 5320148, 156: 5431919, 157: 5545698, 158: 5660662, 159: 5776826, 160: 5895415, 161: 6014812, 162: 6137324, 163: 6259616, 164: 6385263, 165: 6511822, 166: 6640020, 167: 6769934, 168: 6901749, 169: 7035038, 170: 7170924, 171: 7307720, 172: 7446913, 173: 7587352, 174: 7730096, 175: 7873958, 176: 8019963, 177: 8168492, 178: 8318244, 179: 8469406, 180: 8623411, 181: 8778102, 182: 8936452, 183: 9095856, 184: 9256659, 185: 9420004, 186: 9585262, 187: 9752484, 188: 9921241, 189: 10092186, 190: 10266028, 191: 10440754, 192: 10617877, 193: 10797376, 194: 10978628, 195: 11161994, 196: 11347909, 197: 11534510, 198: 11724710, 199: 11915970, 200: 12110819, 201: 12306162, 202: 12504730, 203: 12705006, 204: 12908081, 205: 13112580, 206: 13319686, 207: 13528720, 208: 13740181, 209: 13953626, 210: 14170332, 211: 14387640, 212: 14609331, 213: 14832276, 214: 15057142, 215: 15284314, 216: 15514281, 217: 15746158, 218: 15981558, 219: 16218248, 220: 16457999, 221: 16699020, 222: 16943538, 223: 17190562, 224: 17438841, 225: 17691272, 226: 17944642, 227: 18201414, 228: 18460255, 229: 18721304, 230: 18986676, 231: 19252224, 232: 19521579, 233: 19792476, 234: 20068090, 235: 20344200, 236: 20623803, 237: 20906158, 238: 21191134, 239: 21477198, 240: 21766717, 241: 22060086, 242: 22356142, 243: 22654072, 244: 22954709, 245: 23258276, 246: 23564332, 247: 23872914, 248: 24185069, 249: 24499148, 250: 24817558, 251: 25135592, 252: 25459667, 253: 25784746, 254: 26113692, 255: 26445136, 256: 26779569, 257: 27116514, 258: 27456782, 259: 27798992, 260: 28145971, 261: 28493934, 262: 28845580, 263: 29200176, 264: 29557211, 265: 29918712, 266: 30282348, 267: 30649572, 268: 31019371, 269: 31390296, 270: 31767252, 271: 32145278, 272: 32528397, 273: 32912894, 274: 33300906, 275: 33692204, 276: 34086601, 277: 34483954, 278: 34884852, 279: 35288296, 280: 35695011, 281: 36105178, 282: 36519644, 283: 36935686, 284: 37356003, 285: 37778914, 286: 38205210, 287: 38634230, 288: 39067775, 289: 39502892, 290: 39944692, 291: 40386938, 292: 40832815, 293: 41282652, 294: 41736190, 295: 42191456, 296: 42651527, 297: 43115510, 298: 43581908, 299: 44050718, 300: 44525297, 301: 45001840, 302: 45483546, 303: 45966900, 304: 46454557, 305: 46945166, 306: 47439416, 307: 47937606, 308: 48439785, 309: 48944378, 310: 49454686, 311: 49965658, 312: 50481593, 313: 51001858, 314: 51525206, 315: 52051602, 316: 52583527, 317: 53117046, 318: 53655842, 319: 54197260, 320: 54741921, 321: 55291862, 322: 55844554, 323: 56401298, 324: 56961853, 325: 57526152, 326: 58094964, 327: 58667166, 328: 59242843, 329: 59821464, 330: 60405890, 331: 60991778, 332: 61584575, 333: 62180270, 334: 62778896, 335: 63381888, 336: 63987921, 337: 64599400, 338: 65214736, 339: 65833062, 340: 66457297, 341: 67081930, 342: 67715838, 343: 68348230, 344: 68988899, 345: 69631316, 346: 70279148, 347: 70930252, 348: 71586065, 349: 72243962, 350: 72908808, 351: 73576430, 352: 74248519, 353: 74924616, 354: 75605834, 355: 76290664, 356: 76979311, 357: 77672078, 358: 78369822, 359: 79069828, 360: 79776409, 361: 80486302, 362: 81201346, 363: 81920542, 364: 82644159, 365: 83370414, 366: 84103088, 367: 84839294, 368: 85579369, 369: 86324532, 370: 87074746, 371: 87827998, 372: 88586629, 373: 89348526, 374: 90116528, 375: 90888734, 376: 91663777, 377: 92445336, 378: 93230678, 379: 94018836, 380: 94815509, 381: 95612922, 382: 96417738, 383: 97225308, 384: 98037047, 385: 98856154, 386: 99677908, 387: 100504478, 388: 101336099, 389: 102171254, 390: 103013614, 391: 103855762, 392: 104708317, 393: 105564182, 394: 106423834, 395: 107287506, 396: 108157059, 397: 109029790, 398: 109910626, 399: 110792688, 400: 111682025, 401: 112574662, 402: 113474590, 403: 114377398, 404: 115285221, 405: 116197444, 406: 117115782, 407: 118037818, 408: 118965745, 409: 119897754, 410: 120838070, 411: 121779080, 412: 122728061, 413: 123679566, 414: 124638144, 415: 125600704, 416: 126569139, 417: 127541868, 418: 128518974, 419: 129500712, 420: 130491517, 421: 131485030, 422: 132482328, 423: 133488342, 424: 134495755, 425: 135511478, 426: 136530262, 427: 137553534, 428: 138583981, 429: 139619446, 430: 140661378, 431: 141703560, 432: 142755221, 433: 143811462, 434: 144874050, 435: 145941022, 436: 147012905, 437: 148092262, 438: 149174954, 439: 150260024, 440: 151356743, 441: 152454192, 442: 153561000, 443: 154669990, 444: 155786575, 445: 156906686, 446: 158033342, 447: 159166818, 448: 160303427, 449: 161443468, 450: 162594826, 451: 163748370, 452: 164910073, 453: 166074520, 454: 167246994, 455: 168423438, 456: 169602639, 457: 170792444, 458: 171986538, 459: 173186252, 460: 174391333, 461: 175598680, 462: 176818056, 463: 178040050, 464: 179268125, 465: 180501724, 466: 181742554, 467: 182985148, 468: 184238501, 469: 185493018, 470: 186759822, 471: 188025982, 472: 189301055, 473: 190581174, 474: 191867190, 475: 193158790, 476: 194458907, 477: 195762956, 478: 197071164, 479: 198387120, 480: 199708069, 481: 201039060, 482: 202371664, 483: 203712444, 484: 205059143, 485: 206409224, 486: 207768856, 487: 209132002, 488: 210504929, 489: 211880510, 490: 213263636, 491: 214649838, 492: 216046177, 493: 217446756, 494: 218855082, 495: 220268258, 496: 221687321, 497: 223113338, 498: 224548656, 499: 225985454, 500: 227431379, 501: 228880116, 502: 230338668, 503: 231802086, 504: 233269849, 505: 234747036, 506: 236231318, 507: 237722018, 508: 239215949, 509: 240717184, 510: 242228516, 511: 243738840, 512: 245262667, 513: 246790782, 514: 248323846, 515: 249864732, 516: 251412165, 517: 252965580, 518: 254526468, 519: 256092104, 520: 257666815, 521: 259244500, 522: 260835254, 523: 262424874, 524: 264027619, 525: 265632278, 526: 267246228, 527: 268864828, 528: 270489895, 529: 272123992, 530: 273764986, 531: 275412086, 532: 277067061, 533: 278724662, 534: 280391028, 535: 282067524, 536: 283746365, 537: 285433312, 538: 287129310, 539: 288827186, 540: 290536339, 541: 292250020, 542: 293973670, 543: 295702354, 544: 297436473, 545: 299178726, 546: 300930074, 547: 302684776, 548: 304449891, 549: 306219104, 550: 307996748, 551: 309779974, 552: 311571477, 553: 313369166, 554: 315176850, 555: 316988172, 556: 318810537, 557: 320636236, 558: 322468884, 559: 324307916, 560: 326157353, 561: 328014764, 562: 329875024, 563: 331746328, 564: 333624051, 565: 335508710, 566: 337397338, 567: 339298984, 568: 341205001, 569: 343116202, 570: 345039408, 571: 346963438, 572: 348901569, 573: 350845460, 574: 352794182, 575: 354749736, 576: 356714083, 577: 358687200, 578: 360668536, 579: 362653870, 580: 364651389, 581: 366649324, 582: 368664446, 583: 370679744, 584: 372701611, 585: 374733520, 586: 376775436, 587: 378820702, 588: 380876509, 589: 382936512, 590: 385010922, 591: 387084834, 592: 389172037, 593: 391263076, 594: 393367846, 595: 395471312, 596: 397588769, 597: 399712404, 598: 401842982, 599: 403982200, 600: 406126987, 601: 408281508, 602: 410448292, 603: 412617570, 604: 414793571, 605: 416981348, 606: 419175272, 607: 421373912, 608: 423584839, 609: 425800040, 610: 428029644, 611: 430256894, 612: 432501035, 613: 434750296, 614: 437006732, 615: 439272450, 616: 441544327, 617: 443824670, 618: 446113662, 619: 448411034, 620: 450718425, 621: 453029596, 622: 455350822, 623: 457679864, 624: 460014849, 625: 462362480, 626: 464717466, 627: 467080272, 628: 469448201, 629: 471824596, 630: 474212986, 631: 476604132, 632: 479011299, 633: 481423624, 634: 483840940, 635: 486268358, 636: 488704367, 637: 491148790, 638: 493600924, 639: 496060322, 640: 498531761, 641: 501008778, 642: 503494412, 643: 505988716, 644: 508492357, 645: 511003812, 646: 513524648, 647: 516047398, 648: 518587813, 649: 521128854, 650: 523689946, 651: 526246472, 652: 528821727, 653: 531398682, 654: 533987170, 655: 536583478, 656: 539186353, 657: 541802316, 658: 544423008, 659: 547052634, 660: 549692627, 661: 552340926, 662: 554997748, 663: 557664118, 664: 560337467, 665: 563020802, 666: 565715378, 667: 568412820, 668: 571126661, 669: 573839802, 670: 576569548, 671: 579301890, 672: 582045719, 673: 584801206, 674: 587563708, 675: 590337216, 676: 593114767, 677: 595902836, 678: 598705514, 679: 601508978, 680: 604327027, 681: 607148012, 682: 609982490, 683: 612824638, 684: 615679551, 685: 618536958, 686: 621410036, 687: 624289374, 688: 627174911, 689: 630072808, 690: 632980260, 691: 635892378, 692: 638818645, 693: 641755490, 694: 644694706, 695: 647646972, 696: 650607287, 697: 653581758, 698: 656558228, 699: 659548220, 700: 662548787, 701: 665548964, 702: 668570678, 703: 671594526, 704: 674631533, 705: 677675112, 706: 680732244, 707: 683796734, 708: 686868031, 709: 689947500, 710: 693042844, 711: 696140504, 712: 699254331, 713: 702369880, 714: 705501472, 715: 708640580, 716: 711790839, 717: 714949134, 718: 718118330, 719: 721291474, 720: 724476453, 721: 727673410, 722: 730883520, 723: 734097620, 724: 737324373, 725: 740556698, 726: 743800598, 727: 747055330, 728: 750318689, 729: 753592610, 730: 756876630, 731: 760169716, 732: 763473289, 733: 766784718, 734: 770106276, 735: 773437386, 736: 776779707, 737: 780131024, 738: 783495480, 739: 786861964, 740: 790250199, 741: 793637936, 742: 797039958, 743: 800448884, 744: 803868849, 745: 807303256, 746: 810742864, 747: 814194918, 748: 817655053, 749: 821121610, 750: 824611232, 751: 828096252, 752: 831597915, 753: 835110088, 754: 838631342, 755: 842160022, 756: 845704267, 757: 849252254, 758: 852816544, 759: 856388464, 760: 859969323, 761: 863562352, 762: 867168932, 763: 870778702, 764: 874401559, 765: 878035846, 766: 881676318, 767: 885334326, 768: 888992017, 769: 892666750, 770: 896357264, 771: 900049422, 772: 903757939, 773: 907471682, 774: 911199010, 775: 914936260, 776: 918682817, 777: 922439478, 778: 926210384, 779: 929983218, 780: 933776039, 781: 937570996, 782: 941383018, 783: 945205334, 784: 949036697, 785: 952878746, 786: 956730292, 787: 960592888, 788: 964469325, 789: 968351264, 790: 972250286, 791: 976145852, 792: 980064791, 793: 983996386, 794: 987932584, 795: 991882152, 796: 995838883, 797: 999806592, 798: 1003790136, 799: 1007778282, 800: 1011782813, 801: 1015796136, 802: 1019819884, 803: 1023854844, 804: 1027902277, 805: 1031953412, 806: 1036027392, 807: 1040102732, 808: 1044189675, 809: 1048288450, 810: 1052402564, 811: 1056520174, 812: 1060658841, 813: 1064801636, 814: 1068956950, 815: 1073119980, 816: 1077298371, 817: 1081487756, 818: 1085687996, 819: 1089893636, 820: 1094120277, 821: 1098352082, 822: 1102597034, 823: 1106849860, 824: 1111115023, 825: 1115391518, 826: 1119682030, 827: 1123978892, 828: 1128292289, 829: 1132612714, 830: 1136949728, 831: 1141292718, 832: 1145649599, 833: 1150016402, 834: 1154396576, 835: 1158783982, 836: 1163187149, 837: 1167602734, 838: 1172020234, 839: 1176456968, 840: 1180899797, 841: 1185360856, 842: 1189833246, 843: 1194319274, 844: 1198810907, 845: 1203313700, 846: 1207831740, 847: 1212353614, 848: 1216895057, 849: 1221444284, 850: 1226014214, 851: 1230578102, 852: 1235167289, 853: 1239763496, 854: 1244373010, 855: 1248993656, 856: 1253623569, 857: 1258269710, 858: 1262927266, 859: 1267588704, 860: 1272270609, 861: 1276958248, 862: 1281666744, 863: 1286377248, 864: 1291097745, 865: 1295842104, 866: 1300589184, 867: 1305354312, 868: 1310126795, 869: 1314907974, 870: 1319708374, 871: 1324516372, 872: 1329339497, 873: 1334171022, 874: 1339014078, 875: 1343872374, 876: 1348741681, 877: 1353621780, 878: 1358512436, 879: 1363423074, 880: 1368338449, 881: 1373257390, 882: 1378207372, 883: 1383155126, 884: 1388127455, 885: 1393099286, 886: 1398093280, 887: 1403092934, 888: 1408109365, 889: 1413130942, 890: 1418174714, 891: 1423222478, 892: 1428286515, 893: 1433359394, 894: 1438446994, 895: 1443546930, 896: 1448660839, 897: 1453784036, 898: 1458917338, 899: 1464065556, 900: 1469229427, 901: 1474397428, 902: 1479594284, 903: 1484789650, 904: 1489997613, 905: 1495224446, 906: 1500461612, 907: 1505704910, 908: 1510967135, 909: 1516239952, 910: 1521528614, 911: 1526821424, 912: 1532132499, 913: 1537460138, 914: 1542796822, 915: 1548141222, 916: 1553506025, 917: 1558878236, 918: 1564268904, 919: 1569660156, 920: 1575078443, 921: 1580502582, 922: 1585936358, 923: 1591389054, 924: 1596851039, 925: 1602326250, 926: 1607812792, 927: 1613319396, 928: 1618834379, 929: 1624355678, 930: 1629897204, 931: 1635450492, 932: 1641017161, 933: 1646591046, 934: 1652187168, 935: 1657788330, 936: 1663400577, 937: 1669034962, 938: 1674677622, 939: 1680334198, 940: 1686008379, 941: 1691683576, 942: 1697377740, 943: 1703087876, 944: 1708808603, 945: 1714543602, 946: 1720288930, 947: 1726049318, 948: 1731826991, 949: 1737608408, 950: 1743415158, 951: 1749225376, 952: 1755048583, 953: 1760886392, 954: 1766742024, 955: 1772607610, 956: 1778487249, 957: 1784383054, 958: 1790286670, 959: 1796201350, 960: 1802133113, 961: 1808077322, 962: 1814042028, 963: 1820013252, 964: 1825999833, 965: 1831996446, 966: 1838012158, 967: 1844035588, 968: 1850074357, 969: 1856130064, 970: 1862198538, 971: 1868269978, 972: 1874366383, 973: 1880473160, 974: 1886596954, 975: 1892727994, 976: 1898876493, 977: 1905034940, 978: 1911214000, 979: 1917397746, 980: 1923603787, 981: 1929817982, 982: 1936046480, 983: 1942290124, 984: 1948545619, 985: 1954817070, 986: 1961104286, 987: 1967395982, 988: 1973712645, 989: 1980026286, 990: 1986375114, 991: 1992722426, 992: 1999092851, 993: 2005481704, 994: 2011870736, 995: 2018277368, 996: 2024699573, 997: 2031133808, 998: 2037590422, 999: 2044048790, 1000: 2050527229, 1001: 2057017486, 1002: 2063529198, 1003: 2070043604, 1004: 2076583171, 1005: 2083130478, 1006: 2089688356, 1007: 2096264324, 1008: 2102852661, 1009: 2109455504, 1010: 2116083104, 1011: 2122710044, 1012: 2129356929, 1013: 2136018078, 1014: 2142694792, 1015: 2149384854, 1016: 2156084869, 1017: 2162806546, 1018: 2169538172, 1019: 2176280250, 1020: 2183042587, 1021: 2189814282, 1022: 2196605140, 1023: 2203411088, 1024: 2210226163, 1025: 2217055862, 1026: 2223904854, 1027: 2230766750, 1028: 2237641939, 1029: 2244531312, 1030: 2251441318, 1031: 2258352708, 1032: 2265287467, 1033: 2272234380, 1034: 2279192438, 1035: 2286173164, 1036: 2293162229, 1037: 2300170538, 1038: 2307188698, 1039: 2314219424, 1040: 2321272981, 1041: 2328334160, 1042: 2335421796, 1043: 2342504148, 1044: 2349616301, 1045: 2356738252, 1046: 2363876262, 1047: 2371026402, 1048: 2378198699, 1049: 2385371026, 1050: 2392571952, 1051: 2399778344, 1052: 2407010531, 1053: 2414247088, 1054: 2421501128, 1055: 2428774424, 1056: 2436053759, 1057: 2443357608, 1058: 2450671678, 1059: 2458002960, 1060: 2465350571, 1061: 2472704628, 1062: 2480082930, 1063: 2487464266, 1064: 2494875811, 1065: 2502291156, 1066: 2509728110, 1067: 2517178886, 1068: 2524644481, 1069: 2532115854, 1070: 2539622234, 1071: 2547123884, 1072: 2554648493, 1073: 2562189102, 1074: 2569746008, 1075: 2577318444, 1076: 2584902065, 1077: 2592504332, 1078: 2600118002, 1079: 2607739420, 1080: 2615389337, 1081: 2623050010, 1082: 2630737830, 1083: 2638423496, 1084: 2646131407, 1085: 2653856144, 1086: 2661595812, 1087: 2669343860, 1088: 2677114075, 1089: 2684898404, 1090: 2692696100, 1091: 2700507324, 1092: 2708346097, 1093: 2716188140, 1094: 2724048602, 1095: 2731924626, 1096: 2739824367, 1097: 2747727094, 1098: 2755653304, 1099: 2763581664, 1100: 2771544989, 1101: 2779511986, 1102: 2787497436, 1103: 2795499146, 1104: 2803509087, 1105: 2811547272, 1106: 2819593068, 1107: 2827667396, 1108: 2835741215, 1109: 2843832460, 1110: 2851946376, 1111: 2860071672, 1112: 2868212001, 1113: 2876371834, 1114: 2884550162, 1115: 2892738262, 1116: 2900943289, 1117: 2909159498, 1118: 2917402436, 1119: 2925649046, 1120: 2933916555, 1121: 2942200394, 1122: 2950508912, 1123: 2958826128, 1124: 2967157705, 1125: 2975504826, 1126: 2983871422, 1127: 2992248076, 1128: 3000647317, 1129: 3009060108, 1130: 3017492078, 1131: 3025931462, 1132: 3034391409, 1133: 3042869564, 1134: 3051368278, 1135: 3059869744, 1136: 3068395075, 1137: 3076940398, 1138: 3085494774, 1139: 3094070474, 1140: 3102663193, 1141: 3111265392, 1142: 3119887434, 1143: 3128531510, 1144: 3137186311, 1145: 3145854658, 1146: 3154543194, 1147: 3163245048, 1148: 3171969921, 1149: 3180702228, 1150: 3189458186, 1151: 3198221820, 1152: 3207007835, 1153: 3215814866, 1154: 3224635958, 1155: 3233466032, 1156: 3242320911, 1157: 3251186286, 1158: 3260074784, 1159: 3268970542, 1160: 3277888485, 1161: 3286822254, 1162: 3295778194, 1163: 3304741224, 1164: 3313725247, 1165: 3322728056, 1166: 3331747736, 1167: 3340774756, 1168: 3349831943, 1169: 3358891346, 1170: 3367981834, 1171: 3377072366, 1172: 3386200661, 1173: 3395330854, 1174: 3404481132, 1175: 3413647434, 1176: 3422825597, 1177: 3432035886, 1178: 3441251794, 1179: 3450486860, 1180: 3459744617, 1181: 3469005996, 1182: 3478294182, 1183: 3487597762, 1184: 3496913429, 1185: 3506255126, 1186: 3515603688, 1187: 3524971112, 1188: 3534364383, 1189: 3543753068, 1190: 3553187882, 1191: 3562625586, 1192: 3572078889, 1193: 3581552838, 1194: 3591043530, 1195: 3600553214, 1196: 3610077505, 1197: 3619612176, 1198: 3629171058, 1199: 3638742880, 1200: 3648329983, 1201: 3657942756, 1202: 3667574058, 1203: 3677221490, 1204: 3686886575, 1205: 3696554262, 1206: 3706254602, 1207: 3715967352, 1208: 3725696121, 1209: 3735442280, 1210: 3745213208, 1211: 3754990936, 1212: 3764797299, 1213: 3774607422, 1214: 3784444000, 1215: 3794295452, 1216: 3804162935, 1217: 3814051642, 1218: 3823958468, 1219: 3833870402, 1220: 3843819521, 1221: 3853774946, 1222: 3863752794, 1223: 3873736580, 1224: 3883749599, 1225: 3893774886, 1226: 3903828796, 1227: 3913888122, 1228: 3923962065, 1229: 3934062880, 1230: 3944180908, 1231: 3954306946, 1232: 3964460997, 1233: 3974636338, 1234: 3984814952, 1235: 3995026492, 1236: 4005244173, 1237: 4015484746, 1238: 4025739016, 1239: 4036013920, 1240: 4046309745, 1241: 4056611540, 1242: 4066951402, 1243: 4077294908, 1244: 4087660523, 1245: 4098044754, 1246: 4108444296, 1247: 4118861316, 1248: 4129291725, 1249: 4139749672, 1250: 4150226260, 1251: 4160712312, 1252: 4171228123, 1253: 4181752636, 1254: 4192301648, 1255: 4202848788, 1256: 4213440203, 1257: 4224040930, 1258: 4234655616, 1259: 4245280674, 1260: 4255941459, 1261: 4266604244, 1262: 4277303624, 1263: 4288017828, 1264: 4298739445, 1265: 4309482642, 1266: 4320249284, 1267: 4331024952, 1268: 4341825263, 1269: 4352638676, 1270: 4363486228, 1271: 4374330008, 1272: 4385202637, 1273: 4396094768, 1274: 4407007128, 1275: 4417931138, 1276: 4428880517, 1277: 4439844890, 1278: 4450827200, 1279: 4461826768, 1280: 4472853827, 1281: 4483885734, 1282: 4494948096, 1283: 4506023292, 1284: 4517116817, 1285: 4528234382, 1286: 4539356806, 1287: 4550515056, 1288: 4561679877, 1289: 4572857356, 1290: 4584071888, 1291: 4595292890, 1292: 4606542993, 1293: 4617802410, 1294: 4629085510, 1295: 4640386594, 1296: 4651700381, 1297: 4663033888, 1298: 4674397298, 1299: 4685766306, 1300: 4697166731, 1301: 4708567286, 1302: 4720008006, 1303: 4731456334, 1304: 4742925135, 1305: 4754417472, 1306: 4765923050, 1307: 4777442572, 1308: 4788991157, 1309: 4800552188, 1310: 4812140932, 1311: 4823737882, 1312: 4835359215, 1313: 4846996330, 1314: 4858659238, 1315: 4870332442, 1316: 4882036813, 1317: 4893755386, 1318: 4905484792, 1319: 4917236172, 1320: 4929001053, 1321: 4940804200, 1322: 4952620652, 1323: 4964450976, 1324: 4976298095, 1325: 4988169502, 1326: 5000057552, 1327: 5011968356, 1328: 5023894541, 1329: 5035835648, 1330: 5047809216, 1331: 5059784460, 1332: 5071795863, 1333: 5083816234, 1334: 5095864934, 1335: 5107927060, 1336: 5120007965, 1337: 5132105290, 1338: 5144237132, 1339: 5156372832, 1340: 5168537731, 1341: 5180716510, 1342: 5192902448, 1343: 5205131122, 1344: 5217359843, 1345: 5229627736, 1346: 5241907206, 1347: 5254201766, 1348: 5266518501, 1349: 5278841946, 1350: 5291218752, 1351: 5303572548, 1352: 5315983379, 1353: 5328394754, 1354: 5340830426, 1355: 5353285678, 1356: 5365764123, 1357: 5378255520, 1358: 5390763990, 1359: 5403296500, 1360: 5415855413, 1361: 5428421548, 1362: 5441022362, 1363: 5453628856, 1364: 5466260927, 1365: 5478916122, 1366: 5491593708, 1367: 5504280034, 1368: 5516995733, 1369: 5529726564, 1370: 5542484984, 1371: 5555252230, 1372: 5568048879, 1373: 5580859282, 1374: 5593691916, 1375: 5606546944, 1376: 5619411103, 1377: 5632308312, 1378: 5645224318, 1379: 5658148320, 1380: 5671109461, 1381: 5684082056, 1382: 5697078664, 1383: 5710093978, 1384: 5723124395, 1385: 5736171788, 1386: 5749250110, 1387: 5762342560, 1388: 5775466619, 1389: 5788599392, 1390: 5801759552, 1391: 5814923566, 1392: 5828123773, 1393: 5841341812, 1394: 5854584392, 1395: 5867833968, 1396: 5881112787, 1397: 5894413690, 1398: 5907737418, 1399: 5921064822, 1400: 5934435543, 1401: 5947810364, 1402: 5961209364, 1403: 5974627188, 1404: 5988079583, 1405: 6001535090, 1406: 6015019086, 1407: 6028522420, 1408: 6042046305, 1409: 6055593062, 1410: 6069155484, 1411: 6082744716, 1412: 6096353467, 1413: 6109981702, 1414: 6123625354, 1415: 6137303534, 1416: 6150980725, 1417: 6164694554, 1418: 6178427180, 1419: 6192182712, 1420: 6205959849, 1421: 6219740820, 1422: 6233563810, 1423: 6247394634, 1424: 6261249869, 1425: 6275132292, 1426: 6289027520, 1427: 6302948346, 1428: 6316884703, 1429: 6330838464, 1430: 6344831974, 1431: 6358833876, 1432: 6372863285, 1433: 6386902792, 1434: 6400976138, 1435: 6415058044, 1436: 6429161209, 1437: 6443295864, 1438: 6457447262, 1439: 6471612314, 1440: 6485795827, 1441: 6500015886, 1442: 6514256296, 1443: 6528514510, 1444: 6542796133, 1445: 6557091444, 1446: 6571411556, 1447: 6585752098, 1448: 6600116623, 1449: 6614498638, 1450: 6628912074, 1451: 6643320358, 1452: 6657779863, 1453: 6672240586, 1454: 6686742416, 1455: 6701249562, 1456: 6715783261, 1457: 6730332980, 1458: 6744915450, 1459: 6759501228, 1460: 6774141795, 1461: 6788765402, 1462: 6803437928, 1463: 6818117324, 1464: 6832817799, 1465: 6847546144, 1466: 6862306472, 1467: 6877076088, 1468: 6891861455, 1469: 6906672550, 1470: 6921508406, 1471: 6936360110, 1472: 6951238091, 1473: 6966152740, 1474: 6981067016, 1475: 6996006722, 1476: 7010974505, 1477: 7025962836, 1478: 7040976768, 1479: 7056000262, 1480: 7071057471, 1481: 7086122786, 1482: 7101225682, 1483: 7116336376, 1484: 7131484837, 1485: 7146641742, 1486: 7161824410, 1487: 7177031456, 1488: 7192258125, 1489: 7207510684, 1490: 7222788556, 1491: 7238077116, 1492: 7253396549, 1493: 7268724944, 1494: 7284089646, 1495: 7299466810, 1496: 7314872037, 1497: 7330299190, 1498: 7345747968, 1499: 7361210018, 1500: 7376714765, 1501: 7392226006, 1502: 7407761534, 1503: 7423320360, 1504: 7438901823, 1505: 7454497872, 1506: 7470135622, 1507: 7485783456, 1508: 7501453705, 1509: 7517137984, 1510: 7532861902, 1511: 7548588772, 1512: 7564348613, 1513: 7580136504, 1514: 7595938332, 1515: 7611769638, 1516: 7627615027, 1517: 7643491018, 1518: 7659383706, 1519: 7675287472, 1520: 7691235231, 1521: 7707200636, 1522: 7723182276, 1523: 7739191588, 1524: 7755218183, 1525: 7771271536, 1526: 7787351162, 1527: 7803446452, 1528: 7819552329, 1529: 7835699892, 1530: 7851874882, 1531: 7868043894, 1532: 7884270609, 1533: 7900500194, 1534: 7916755054, 1535: 7933033936, 1536: 7949328199, 1537: 7965654984, 1538: 7981996938, 1539: 7998373306, 1540: 8014764355, 1541: 8031170000, 1542: 8047620492, 1543: 8064088702, 1544: 8080567459, 1545: 8097070614, 1546: 8113600314, 1547: 8130151704, 1548: 8146734195, 1549: 8163313906, 1550: 8179957184, 1551: 8196591222, 1552: 8213260903, 1553: 8229945606, 1554: 8246662854, 1555: 8263400030, 1556: 8280166991, 1557: 8296947394, 1558: 8313753072, 1559: 8330576036, 1560: 8347428617, 1561: 8364303778, 1562: 8381198684, 1563: 8398129274, 1564: 8415075903, 1565: 8432036870, 1566: 8449027290, 1567: 8466044390, 1568: 8483091213, 1569: 8500147402, 1570: 8517238056, 1571: 8534338100, 1572: 8551478059, 1573: 8568632332, 1574: 8585806624, 1575: 8603003904, 1576: 8620236761, 1577: 8637484664, 1578: 8654756228, 1579: 8672049078, 1580: 8689371021, 1581: 8706707828, 1582: 8724084558, 1583: 8741464716, 1584: 8758869845, 1585: 8776315872, 1586: 8793786478, 1587: 8811261542, 1588: 8828776297, 1589: 8846299826, 1590: 8863866972, 1591: 8881438166, 1592: 8899038141, 1593: 8916670780, 1594: 8934316064, 1595: 8951985032, 1596: 8969688235, 1597: 8987401792, 1598: 9005154004, 1599: 9022920212, 1600: 9040716837, 1601: 9058525756, 1602: 9076378884, 1603: 9094232466, 1604: 9112131607, 1605: 9130040664, 1606: 9147976436, 1607: 9165935286, 1608: 9183914635, 1609: 9201915412, 1610: 9219960668, 1611: 9238011710, 1612: 9256096289, 1613: 9274197982, 1614: 9292332054, 1615: 9310479906, 1616: 9328651563, 1617: 9346860410, 1618: 9365082730, 1619: 9383325102, 1620: 9401605173, 1621: 9419897462, 1622: 9438215878, 1623: 9456569852, 1624: 9474936963, 1625: 9493338050, 1626: 9511752600, 1627: 9530196170, 1628: 9548663989, 1629: 9567153882, 1630: 9585670192, 1631: 9604202160, 1632: 9622766037, 1633: 9641361308, 1634: 9659975268, 1635: 9678607498, 1636: 9697283647, 1637: 9715960670, 1638: 9734678656, 1639: 9753394090, 1640: 9772168013, 1641: 9790952606, 1642: 9809767222, 1643: 9828600080, 1644: 9847457497, 1645: 9866335658, 1646: 9885246928, 1647: 9904181660, 1648: 9923134041, 1649: 9942115358, 1650: 9961127538, 1651: 9980143916, 1652: 9999212883, 1653: 10018299334, 1654: 10037394762, 1655: 10056521814, 1656: 10075672885, 1657: 10094858354, 1658: 10114071712, 1659: 10133292404, 1660: 10152551249, 1661: 10171823716, 1662: 10191141344, 1663: 10210454996, 1664: 10229810327, 1665: 10249191438, 1666: 10268593014, 1667: 10288023408, 1668: 10307477751, 1669: 10326957710, 1670: 10346466062, 1671: 10365988134, 1672: 10385544293, 1673: 10405112618, 1674: 10424729834, 1675: 10444357406, 1676: 10464007713, 1677: 10483688728, 1678: 10503389540, 1679: 10523120972, 1680: 10542859943, 1681: 10562647566, 1682: 10582460418, 1683: 10602297632, 1684: 10622141839, 1685: 10642032142, 1686: 10661942614, 1687: 10681870766, 1688: 10701827929, 1689: 10721796916, 1690: 10741829828, 1691: 10761839592, 1692: 10781904345, 1693: 10801984338, 1694: 10822103090, 1695: 10842234270, 1696: 10862394213, 1697: 10882577588, 1698: 10902795876, 1699: 10923021046, 1700: 10943291315, 1701: 10963574444, 1702: 10983892294, 1703: 11004218694, 1704: 11024594431, 1705: 11044992220, 1706: 11065402084, 1707: 11085847880, 1708: 11106315841, 1709: 11126791342, 1710: 11147317096, 1711: 11167860636, 1712: 11188442783, 1713: 11209034778, 1714: 11229648802, 1715: 11250293976, 1716: 11270972865, 1717: 11291669372, 1718: 11312395298, 1719: 11333148526, 1720: 11353922653, 1721: 11374722580, 1722: 11395558206, 1723: 11416411576, 1724: 11437293557, 1725: 11458189896, 1726: 11479128746, 1727: 11500082586, 1728: 11521063591, 1729: 11542074872, 1730: 11563129804, 1731: 11584179460, 1732: 11605270381, 1733: 11626386488, 1734: 11647523330, 1735: 11668688458, 1736: 11689879179, 1737: 11711100370, 1738: 11732346128, 1739: 11753615846, 1740: 11774915977, 1741: 11796234228, 1742: 11817593764, 1743: 11838968516, 1744: 11860372937, 1745: 11881795858, 1746: 11903260776, 1747: 11924731368, 1748: 11946240101, 1749: 11967775622, 1750: 11989344036, 1751: 12010914006, 1752: 12032536895, 1753: 12054183772, 1754: 12075844670, 1755: 12097541070, 1756: 12119261983, 1757: 12141007596, 1758: 12162784930, 1759: 12184566690, 1760: 12206406107, 1761: 12228252614, 1762: 12250122580, 1763: 12272044010, 1764: 12293972345, 1765: 12315923116, 1766: 12337910366, 1767: 12359928610, 1768: 12381971157, 1769: 12404020572, 1770: 12426129422, 1771: 12448240350, 1772: 12470394811, 1773: 12492562516, 1774: 12514758184, 1775: 12536990520, 1776: 12559230039, 1777: 12581515318, 1778: 12603823728, 1779: 12626160400, 1780: 12648531997, 1781: 12670895832, 1782: 12693325334, 1783: 12715752434, 1784: 12738229191, 1785: 12760720940, 1786: 12783246232, 1787: 12805794472, 1788: 12828372863, 1789: 12850982004, 1790: 12873613496, 1791: 12896266106, 1792: 12918945325, 1793: 12941663296, 1794: 12964396994, 1795: 12987167764, 1796: 13009959455, 1797: 13032777670, 1798: 13055640356, 1799: 13078484158, 1800: 13101391487, 1801: 13124322864, 1802: 13147296126, 1803: 13170270528, 1804: 13193288217, 1805: 13216322512, 1806: 13239395578, 1807: 13262486492, 1808: 13285600859, 1809: 13308751950, 1810: 13331933228, 1811: 13355130312, 1812: 13378363525, 1813: 13401606654, 1814: 13424905814, 1815: 13448225050, 1816: 13471555571, 1817: 13494918234, 1818: 13518325980, 1819: 13541731566, 1820: 13565201927, 1821: 13588672056, 1822: 13612170438, 1823: 13635710296, 1824: 13659267843, 1825: 13682857958, 1826: 13706470216, 1827: 13730119430, 1828: 13753797521, 1829: 13777494144, 1830: 13801223470, 1831: 13824972750, 1832: 13848759985, 1833: 13872571514, 1834: 13896411188, 1835: 13920260568, 1836: 13944169249, 1837: 13968083300, 1838: 13992041940, 1839: 14016016638, 1840: 14040025735, 1841: 14064060506, 1842: 14088130430, 1843: 14112214174, 1844: 14136326211, 1845: 14160471100, 1846: 14184649166, 1847: 14208847684, 1848: 14233077947, 1849: 14257330580, 1850: 14281629678, 1851: 14305937202, 1852: 14330282399, 1853: 14354642572, 1854: 14379058808, 1855: 14403477800, 1856: 14427933293, 1857: 14452422320, 1858: 14476924334, 1859: 14501468336, 1860: 14526031525, 1861: 14550611826, 1862: 14575258960, 1863: 14599915764, 1864: 14624590353, 1865: 14649307726, 1866: 14674036560, 1867: 14698808100, 1868: 14723611153, 1869: 14748418166, 1870: 14773282134, 1871: 14798143938, 1872: 14823056561, 1873: 14847997872, 1874: 14872970836, 1875: 14897963804, 1876: 14922989853, 1877: 14948043436, 1878: 14973115476, 1879: 14998224332, 1880: 15023363785, 1881: 15048534572, 1882: 15073727448, 1883: 15098946162, 1884: 15124194037, 1885: 15149491292, 1886: 15174785390, 1887: 15200133970, 1888: 15225491451, 1889: 15250875116, 1890: 15276311618, 1891: 15301752072, 1892: 15327253689, 1893: 15352765076, 1894: 15378306070, 1895: 15403875638, 1896: 15429461667, 1897: 15455099622, 1898: 15480752478, 1899: 15506424248, 1900: 15532151343, 1901: 15557884500, 1902: 15583671346, 1903: 15609456626, 1904: 15635278941, 1905: 15661152350, 1906: 15687039060, 1907: 15712943794, 1908: 15738900857, 1909: 15764865016, 1910: 15790891834, 1911: 15816900186, 1912: 15842973423, 1913: 15869058628, 1914: 15895181784, 1915: 15921335458, 1916: 15947518869, 1917: 15973726224, 1918: 15999955134, 1919: 16026219464, 1920: 16052512879, 1921: 16078844830, 1922: 16105199162, 1923: 16131588250, 1924: 16158006287, 1925: 16184442692, 1926: 16210919090, 1927: 16237407364, 1928: 16263957085, 1929: 16290514354, 1930: 16317105364, 1931: 16343709892, 1932: 16370373971, 1933: 16397053922, 1934: 16423749906, 1935: 16450495500, 1936: 16477259903, 1937: 16504049234, 1938: 16530895922, 1939: 16557734408, 1940: 16584638761, 1941: 16611534976, 1942: 16638490382, 1943: 16665474124, 1944: 16692462689, 1945: 16719495984, 1946: 16746573778, 1947: 16773669214, 1948: 16800781595, 1949: 16827931674, 1950: 16855132496, 1951: 16882331206, 1952: 16909587021, 1953: 16936851538, 1954: 16964163616, 1955: 16991490290, 1956: 17018854213, 1957: 17046239568, 1958: 17073664784, 1959: 17101127704, 1960: 17128608743, 1961: 17156104042, 1962: 17183663168, 1963: 17211234562, 1964: 17238835951, 1965: 17266464770, 1966: 17294146488, 1967: 17321820196, 1968: 17349548331, 1969: 17377295416, 1970: 17405098964, 1971: 17432899814, 1972: 17460747943, 1973: 17488620662, 1974: 17516521618, 1975: 17544450448, 1976: 17572425447, 1977: 17600424912, 1978: 17628442122, 1979: 17656489986, 1980: 17684583923, 1981: 17712696444, 1982: 17740850230, 1983: 17769033680, 1984: 17797240639, 1985: 17825476118, 1986: 17853738104, 1987: 17882043836, 1988: 17910372801, 1989: 17938741918, 1990: 17967130214, 1991: 17995549806, 1992: 18023995317, 1993: 18052479814, 1994: 18080998176, 1995: 18109534864, 1996: 18138116441, 1997: 18166711096, 1998: 18195359370, 1999: 18224006588, 2000: 18252715047, 2001: 18281440374, 2002: 18310206524, 2003: 18338980964, 2004: 18367813869, 2005: 18396668104, 2006: 18425549136, 2007: 18454468966, 2008: 18483398125, 2009: 18512374114, 2010: 18541387558, 2011: 18570404150, 2012: 18599486567, 2013: 18628592906, 2014: 18657703644, 2015: 18686859232, 2016: 18716046853, 2017: 18745279774, 2018: 18774527482, 2019: 18803818674, 2020: 18833145303, 2021: 18862478966, 2022: 18891859618, 2023: 18921264244, 2024: 18950697327, 2025: 18980169810, 2026: 19009667936, 2027: 19039205800, 2028: 19068767351, 2029: 19098357214, 2030: 19128001662, 2031: 19157639736, 2032: 19187337709, 2033: 19217050890, 2034: 19246809278, 2035: 19276589068, 2036: 19306412337, 2037: 19336240588, 2038: 19366131864, 2039: 19396026832, 2040: 19425958873, 2041: 19455938600, 2042: 19485944316, 2043: 19515986918, 2044: 19546043477, 2045: 19576132726, 2046: 19606263326, 2047: 19636431128, 2048: 19666609365, 2049: 19696834394, 2050: 19727104970, 2051: 19757353614, 2052: 19787701785, 2053: 19818040942, 2054: 19848429620, 2055: 19878829056, 2056: 19909273441, 2057: 19939761128, 2058: 19970275822, 2059: 20000795696, 2060: 20031376997, 2061: 20061975182, 2062: 20092600638, 2063: 20123267014, 2064: 20153960463, 2065: 20184710080, 2066: 20215464924, 2067: 20246254032, 2068: 20277085067, 2069: 20307927424, 2070: 20338826526, 2071: 20369735954, 2072: 20400704429, 2073: 20431680344, 2074: 20462712824, 2075: 20493755800, 2076: 20524842691, 2077: 20555932006, 2078: 20587086902, 2079: 20618265034, 2080: 20649470177, 2081: 20680709572, 2082: 20711997328, 2083: 20743295138, 2084: 20774640263, 2085: 20806004856, 2086: 20837411096, 2087: 20868837110, 2088: 20900293333, 2089: 20931786142, 2090: 20963341648, 2091: 20994901062, 2092: 21026482153, 2093: 21058124702, 2094: 21089778936, 2095: 21121473748, 2096: 21153202421, 2097: 21184959842, 2098: 21216751208, 2099: 21248561574, 2100: 21280419055, 2101: 21312299434, 2102: 21344228444, 2103: 21376177872, 2104: 21408172329, 2105: 21440178784, 2106: 21472231412, 2107: 21504305276, 2108: 21536430445, 2109: 21568572538, 2110: 21600756848, 2111: 21632962082, 2112: 21665200653, 2113: 21697479592, 2114: 21729800518, 2115: 21762150104, 2116: 21794517499, 2117: 21826929924, 2118: 21859367972, 2119: 21891837396, 2120: 21924342881, 2121: 21956891346, 2122: 21989463742, 2123: 22022066148, 2124: 22054703515, 2125: 22087374828, 2126: 22120072666, 2127: 22152827802, 2128: 22185583989, 2129: 22218369222, 2130: 22251223676, 2131: 22284083800, 2132: 22317003671, 2133: 22349930050, 2134: 22382893566, 2135: 22415888758, 2136: 22448928827, 2137: 22482002710, 2138: 22515097314, 2139: 22548220344, 2140: 22581409651, 2141: 22614580132, 2142: 22647835194, 2143: 22681080768, 2144: 22714386301, 2145: 22747719762, 2146: 22781091458, 2147: 22814485296, 2148: 22847925521, 2149: 22881375740, 2150: 22914889334, 2151: 22948412082, 2152: 22981987341, 2153: 23015588956, 2154: 23049215580, 2155: 23082866676, 2156: 23116574277, 2157: 23150316704, 2158: 23184063670, 2159: 23217861044, 2160: 23251693689, 2161: 23285546546, 2162: 23319464186, 2163: 23353413406, 2164: 23387373951, 2165: 23421373318, 2166: 23455404876, 2167: 23489469900, 2168: 23523570055, 2169: 23557708714, 2170: 23591878154, 2171: 23626076336, 2172: 23660314657, 2173: 23694578900, 2174: 23728881648, 2175: 23763219812, 2176: 23797592885, 2177: 23831989974, 2178: 23866440090, 2179: 23900902530, 2180: 23935425443, 2181: 23969948060, 2182: 24004530098, 2183: 24039130364, 2184: 24073761697, 2185: 24108443134, 2186: 24143155988, 2187: 24177905376, 2188: 24212695275, 2189: 24247484040, 2190: 24282340990, 2191: 24317210598, 2192: 24352137889, 2193: 24387076928, 2194: 24422063206, 2195: 24457072792, 2196: 24492119935, 2197: 24527206344, 2198: 24562329910, 2199: 24597473268, 2200: 24632662189, 2201: 24667875578, 2202: 24703139552, 2203: 24738429770, 2204: 24773751911, 2205: 24809101090, 2206: 24844497316, 2207: 24879931178, 2208: 24915382113, 2209: 24950868552, 2210: 24986418640, 2211: 25021963892, 2212: 25057576457, 2213: 25093191060, 2214: 25128882680, 2215: 25164573576, 2216: 25200304261, 2217: 25236074556, 2218: 25271888990, 2219: 25307716812, 2220: 25343599443, 2221: 25379494642, 2222: 25415444250, 2223: 25451432394, 2224: 25487422517, 2225: 25523485744, 2226: 25559560472, 2227: 25595677296, 2228: 25631832535, 2229: 25668014074, 2230: 25704238576, 2231: 25740473940, 2232: 25776781233, 2233: 25813097992, 2234: 25849462522, 2235: 25885862050, 2236: 25922292871, 2237: 25958750250, 2238: 25995244404, 2239: 26031769900, 2240: 26068339841, 2241: 26104949822, 2242: 26141570498, 2243: 26178260834, 2244: 26214967497, 2245: 26251713234, 2246: 26288500116, 2247: 26325297518, 2248: 26362161505, 2249: 26399023274, 2250: 26435956496, 2251: 26472901262, 2252: 26509899053, 2253: 26546916512, 2254: 26583976300, 2255: 26621058530, 2256: 26658178401, 2257: 26695366964, 2258: 26732562478, 2259: 26769792688, 2260: 26807069131, 2261: 26844352060, 2262: 26881712512, 2263: 26919083490, 2264: 26956495377, 2265: 26993943104, 2266: 27031429818, 2267: 27068922558, 2268: 27106486265, 2269: 27144064390, 2270: 27181708024, 2271: 27219369872, 2272: 27257048349, 2273: 27294782010, 2274: 27332558482, 2275: 27370349612, 2276: 27408176237, 2277: 27446051340, 2278: 27483962544, 2279: 27521888684, 2280: 27559862781, 2281: 27597883870, 2282: 27635942300, 2283: 27674036422, 2284: 27712155453, 2285: 27750318000, 2286: 27788508500, 2287: 27826719644, 2288: 27864989115, 2289: 27903280246, 2290: 27941630410, 2291: 27979988616, 2292: 28018398369, 2293: 28056846838, 2294: 28095317506, 2295: 28133833890, 2296: 28172384151, 2297: 28210963240, 2298: 28249590004, 2299: 28288243646, 2300: 28326951403, 2301: 28365666962, 2302: 28404447892, 2303: 28443239914, 2304: 28482065093, 2305: 28520952318, 2306: 28559867844, 2307: 28598813120, 2308: 28637783477, 2309: 28676790442, 2310: 28715864554, 2311: 28754936440, 2312: 28794079573, 2313: 28833240452, 2314: 28872441752, 2315: 28911670514, 2316: 28950953491, 2317: 28990247594, 2318: 29029604862, 2319: 29068968486, 2320: 29108379923, 2321: 29147830628, 2322: 29187338384, 2323: 29226838420, 2324: 29266438961, 2325: 29306021590, 2326: 29345642418, 2327: 29385319430, 2328: 29425026497, 2329: 29464771352, 2330: 29504556500, 2331: 29544368818, 2332: 29584229615, 2333: 29624113694, 2334: 29664035752, 2335: 29703999968, 2336: 29744000851, 2337: 29784050836, 2338: 29824106944, 2339: 29864194866, 2340: 29904365393, 2341: 29944525240, 2342: 29984774644, 2343: 30025036222, 2344: 30065303909, 2345: 30105644886, 2346: 30146018242, 2347: 30186402768, 2348: 30226854249, 2349: 30267324378, 2350: 30307852176, 2351: 30348384192, 2352: 30388959193, 2353: 30429602642, 2354: 30470267284, 2355: 30510968386, 2356: 30551705975, 2357: 30592462588, 2358: 30633275182, 2359: 30674108380, 2360: 30715002867, 2361: 30755925012, 2362: 30796892560, 2363: 30837867184, 2364: 30878893491, 2365: 30919979362, 2366: 30961073922, 2367: 31002212626, 2368: 31043409001, 2369: 31084616424, 2370: 31125884168, 2371: 31167156566, 2372: 31208485157, 2373: 31249843792, 2374: 31291264530, 2375: 31332690232, 2376: 31374164615, 2377: 31415673140, 2378: 31457231434, 2379: 31498818978, 2380: 31540464387, 2381: 31582110194, 2382: 31623820450, 2383: 31665556220, 2384: 31707339699, 2385: 31749152170, 2386: 31790992178, 2387: 31832896552, 2388: 31874825979, 2389: 31916765322, 2390: 31958784276, 2391: 32000800204, 2392: 32042896931, 2393: 32084994136, 2394: 32127151474, 2395: 32169342044, 2396: 32211571521, 2397: 32253838444, 2398: 32296131360, 2399: 32338469650, 2400: 32380837031, 2401: 32423268800, 2402: 32465724690, 2403: 32508217744, 2404: 32550736097, 2405: 32593318632, 2406: 32635903024, 2407: 32678556708, 2408: 32721226259, 2409: 32763948030, 2410: 32806709878, 2411: 32849478660, 2412: 32892340257, 2413: 32935197744, 2414: 32978112642, 2415: 33021041010, 2416: 33064031575, 2417: 33107048486, 2418: 33150116138, 2419: 33193204452, 2420: 33236338661, 2421: 33279515518, 2422: 33322732668, 2423: 33365987512, 2424: 33409254183, 2425: 33452585598, 2426: 33495954966, 2427: 33539369830, 2428: 33582811939, 2429: 33626269714, 2430: 33669799540, 2431: 33713341902, 2432: 33756937901, 2433: 33800578504, 2434: 33844238068, 2435: 33887955796, 2436: 33931699859, 2437: 33975479128, 2438: 34019300774, 2439: 34063169634, 2440: 34107069375, 2441: 34151003346, 2442: 34195006626, 2443: 34238999882, 2444: 34283063915, 2445: 34327145264, 2446: 34371295780, 2447: 34415434136, 2448: 34459653165, 2449: 34503884880, 2450: 34548202428, 2451: 34592509102, 2452: 34636878789, 2453: 34681283850, 2454: 34725735624, 2455: 34770193946, 2456: 34814716337, 2457: 34859263280, 2458: 34903871430, 2459: 34948492262, 2460: 34993176971, 2461: 35037883380, 2462: 35082618080, 2463: 35127427896, 2464: 35172239553, 2465: 35217112242, 2466: 35262023698, 2467: 35306965738, 2468: 35351949141, 2469: 35396971286, 2470: 35442048274, 2471: 35487125012, 2472: 35532273341, 2473: 35577442954, 2474: 35622671628, 2475: 35667936540, 2476: 35713215171, 2477: 35758549622, 2478: 35803936994, 2479: 35849329914, 2480: 35894783061, 2481: 35940278442, 2482: 35985808660, 2483: 36031380044, 2484: 36076994073, 2485: 36122628006, 2486: 36168336746, 2487: 36214050002, 2488: 36259825493, 2489: 36305618022, 2490: 36351463320, 2491: 36397335366, 2492: 36443278941, 2493: 36489242850, 2494: 36535233644, 2495: 36581274504, 2496: 36627343961, 2497: 36673465620, 2498: 36719630852, 2499: 36765827488, 2500: 36812076035}
cases = int(input())
for _ in range(cases):
	print(result[int(input())])