CNPIIM.c

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#define gc getchar
#define ll long long int
#define M 1000000007
#define scan(t) t=input()
inline ll input() {
  char c = gc();
  while(c<'0' || c>'9') c = gc();
  ll ret = 0;
  while(c>='0' && c<='9') {
    ret = 10 * ret + c - 48;
    c = gc();
  }
  return ret;
}
int main()
{
	ll t,n;
	ll a[2501]={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};
    scan(t);
    while(t--)
    {
        scan(n);
        printf("%lld\n",a[n]);
    }
    return 0;
}