#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

constexpr long long a[]={0,1,1,1,1,2,2,3,3,3,4,5,6,7,7,8,9,11,12,14,15,16,18,19,22,24,27,30,31,33,37,39,43,48,50,55,61,63,66,73,79,81,88,98,102,109,121,127,129,136,149,161,165,175,194,206,210,224,247,255,263,274,296,321,333,339,360,396,416,428,449,490,511,527,543,563,607,651,671,691,723,786,832,860,882,923,1003,1023,1067,1099,1140,1213,1297,1343,1387,1425,1486,1610,1674,1738,1790,1863,1999,2047,2129,2203,2269,2348,2489,2633,2697,2805,2889,3003,3212,3344,3472,3590,3694,3834,4095,4099,4307,4435,4595,4752,5002,5259,5391,5601,5793,5963,6182,6584,6732,7004,7240,7484,7755,8191,8214,8603,8863,9191,9487,9797,10277,10679,10831,11311,11675,12079,12507,13193,13473,13994,14464,14984,15450,15979,16383,16861,17411,17835,18551,19159,19834,20698,21384,21687,22597,23327,24175,24937,25776,26660,27540,28242,29146,30226,31238,32341,32767,33891,34857,35681,37061,38311,39625,40916,42159,43043,44401,45653,46981,48777,50397,52175,53465,55275,56544,58278,60388,62486,64562,65535,66692,68819,70583,72643,74799,77207,80015,82738,84942,86232,89166,91401,93959,97449,100797,104187,106451,108851,111862,114984,118296,121780,125984,130412,131071,134913,138407,141507,145710,149679,154347,159935,165359,169722,171986,175543,180681,185567,190939,196579,203191,210427,213809,219855,224639,230673,237111,243638,251796,260732,262143,269546,276173,280837,287405,295665,303863,312719,322563,333603,341498,344880,354768,363046,372180,382821,393317,406143,420667,427502,439268,448159,456380,468086,481232,494802,509298,524287,525754,544030,555307,564735,579407,593719,609291,626459,645113,666875,682810,689645,708814,724332,737217,755491,776897,798665,822017,846850,859357,885528,900187,919503,942453,965899,992112,1019776,1048575,1051256,1087542,1110312,1128913,1156973,1180712,1205303,1236723,1271699,1307963,1346304,1371137,1385111,1429558,1455494,1484238,1521860,1559618,1601403,1646235,1693688,1718131,1770352,1799957,1837727,1881305,1917929,1960794,2013620,2070364,2097151,2129980,2193154,2230494,2270639,2329745,2374997,2426691,2487759,2551730,2621179,2694810,2742263,2769387,2857894,2910269,2966640,3038278,3098641,3166097,3250343,3342063,3405114,3476284,3564291,3615605,3700197,3785239,3859235,3948551,4047377,4153133,4194303,4267414,4388498,4460394,4539739,4657851,4747996,4847945,4956207,5059435,5179717,5320707,5439214,5502265,5606264,5757445,5846099,5970836,6114984,6234232,6375242,6535136,6704863,6815482,6962224,7130761,7229781,7397633,7568120,7714636,7886223,8054848,8225532,8388607,8430060,8662770,8844328,8978549,9170555,9373050,9546296,9756075,9974219,10182783,10422619,10688269,10899166,11009785,11229638,11519259,11690175,11937372,12225971,12462632,12734168,13011055,13284967,13568324,13750767,14101984,14346593,14584813,14928000,15219149,15517132,15871059,16208451,16558025,16777215,16957755,17393132,17714648,17972009,18360399,18749040,19087808,19505492,19940607,20348855,20789016,21236587,21673574,21956931,22180827,22764754,23190921,23563362,24098555,24592199,25063428,25627134,26182670,26740808,27199834,27646024,28292298,28724433,29201647,29879658,30439215,31025180,31731463,32403239,33083023,33554431,33800071,34521554,35241898,35707698,36282811,37111347,37775734,38491362,39317704,40109331,40934487,41835585,42740695,43518023,43977049,44603779,45685430,46439081,47173656,48240057,49188255,50112988,51236955,52343846,53431878,54343447,55036658,56195128,57198829,57888525,59047565,60302268,61339096,62589917,63909903,65172759,66561621,67108863,68018255,69481503,70717857,71623073,72896077,74409863,75640728,77053314,78679272,80213435,81844451,83640194,85426869,86986309,87897878,88836729,90716682,92440727,93596223,95330376,97413615,99114830,101081279,103227607,105282090,107496108,108944448,110758950,112999526,114694906,116226852,118581507,120848944,122814384,125293371,127867527,130326423,133081406,134217727,135984040,138858747,141329756,142934536,145031857,147915511,150329252,152643788,155632644,158752711,161704747,164991182,168400366,171843711,174604971,176053311,178777205,182481029,185412763,187849925,191477584,195258807,198455112,202346685,206546799,210539858,214925857,217857921,221410909,225845056,229227634,231771265,235748539,240356238,243925475,247974164,253046259,257867541,262786026,268218789,268435455,273682456,279339819,283549419,286812261,291776731,297175935,301639615,306431432,312326528,318073191,323748483,330214212,336873222,343621264,349143584,352075648,357394949,364703803,370557390,374705801,380780396,388271749,394254727,400617952,408678903,416620252,424490773,433209971,436835821,445526167,453944790,459602730,465589466,474257760,482588698,489489540,497909016,507585335,516528303,526095168,536761011,536870911,547413080,558547121,567001505,573486557,583240005,593931437,602328655,610454340,621136634,632197224,642228891,653664211,666546444,679406278,692709562,701645426,705271276,719208623,733284609,743152149,752401727,766034491,779764633,791129155,804340448,819911863,834601494,849843651,866975223,873744133,891034344,907690705,919077153,930881506,947943808,964488827,977034456,991234736,1009408383,1026451951,1042846843,1062343114,1073741823,1083166696,1103897051,1125919533,1138481247,1150797443,1173153413,1192887339,1208741615,1226659487,1248623189,1269254173,1289038171,1311925783,1336440166,1360696662,1386604662,1403846134,1410615044,1438447424,1466237826,1486078658,1504368063,1531183813,1558420264,1579363111,1601689076,1630545017,1658649175,1685075734,1716007325,1740288267,1762572974,1796606613,1827564959,1843752523,1870006066,1906438022,1936039488,1961143342,1992693978,2028387822,2060383328,2093378619,2131837646,2147483647,2171041660,2210540313,2253579885,2277590267,2301649388,2346138129,2385314979,2416960164,2452311871,2495672640,2535454720,2570597847,2611097459,2656996968,2701496018,2747418848,2789749148,2814030090,2845739670,2900503664,2953484492,2982233770,3020803509,3079591435,3128926827,3169884957,3219353465,3277011011,3329637501,3382416790,3443763429,3483923813,3531738322,3597144975,3657426019,3688205311,3740096812,3812375955,3871393637,3921328227,3983495684,4054092904,4114817831,4172286923,4241642476,4294967295,4315646143,4386571752,4463426173,4530037415,4576603064,4642346283,4728068623,4797237015,4852239836,4927241531,5015630923,5090070169,5162578935,5247741287,5337394339,5423016120,5514254436,5591247076,5631407460,5702779982,5807685288,5911005904,5965795578,6041746200,6158514084,6256708616,6338288391,6435807555,6549765544,6650272551,6742884770,6852739935,6951964263,7017142161,7133990600,7253175321,7344067505,7422342734,7542849947,7681553115,7779470785,7873043345,8006832966,8144557750,8259955126,8381932400,8524752298,8589934591,8667031840,8805432910,8958017865,9075170889,9163145782,9299924957,9465111307,9599211215,9705892390,9854122155,10029907721,10178036843,10321784075,10489900459,10664583375,10822559474,10984527246,11147707230,11246931558,11332788304,11520562352,11716601494,11874104920,11998945798,12185196230,12409621738,12576707800,12725283181,12934074497,13160188673,13350025295,13544511335,13772493585,13927328930,14090047960,14319687346,14549264941,14706578349,14865925764,15107610245,15376117211,15565006793,15747638590,16012636239,16286616337,16516325234,16757591630,17039666003,17179869183,17314855926,17565444244,17837267181,18099671493,18264073719,18466778904,18773737673,19060668999,19296447654,19541795745,19866749345,20189092523,20449751145,20732116147,21078632247,21420143799,21731957695,22069263633,22362428176,22517263521,22757079800,23125120256,23507282806,23781749238,24029071546,24407535202,24841228518,25164218008,25453530980,25866758394,26316524058,26694362077,27079375705,27529566462,27844452558,28137415400,28549971490,28984974411,29346603051,29596862023,29987341256,30490339167,30934773919,31295393452,31726991975,32276371083,32765800323,33175034326,33666190644,34238820920,34359738367,34770169094,35276469030,35841757218,36289757106,36607311481,37076767146,37674385197,38213861155,38647675002,39136681791,39783652413,40406235311,40911856598,41466167219,42153374731,42832849292,43451953707,44119041708,44709435645,45024321741,45452271326,46115415734,46822241592,47446274544,47860935742,48454120160,49264076840,49995442918,50591841106,51268787720,52143120428,52954892846,53624785471,54398306791,55317453167,55779882166,56502126789,57345732663,58204185394,58807020627,59364391281,60201887402,61181668003,61995610393,62676746548,63544216993,64624880931,65570453319,66365387578,67332925613,68469898789,68719476735,69527211369,70531329412,71648608170,72553888203,73161737141,74002242816,75100390145,76168844643,77043136567,77848276998,78944459327,80198850759,81290836370,82318833081,83545158803,84908920751,86129927172,87290976115,88637127711,89677191534,90139620533,91272295883,92622201693,94045942612,95096777733,95971702762,97278654548,98856053200,100209471548,101324421550,102680898784,104408533344,105976688630,107277244176,108799092832,110623273520,111552326027,112979165076,114650371120,116358043815,117578209944,118614008467,120117658550,121922631737,123615119187,124904072309,126302397158,128208536167,130194293677,131882677476,133587620801,135688279231,137438953471,137863813597,139754712643,141689282906,143954580878,145457073700,146641747322,148618028546,150826387087,152852963239,154461169014,156173590164,158460322551,160851663593,162886218096,164868638543,167305779715,169978986663,172342076208,174610169789,177268991621,179342750255,180271802762,182506376445,185181700532,188006651985,190132098147,191775745608,194119901366,197023021882,199783963830,201947208876,204150674156,207152995494,210393144436,213173513846,215906453882,219233438034,222347874222,223993740769,227045688758,230326410617,233631772412,235596694233,237914043205,241240230239,244872329699,247949740972,250432871776,253452244712,257316375751,261061135141,264210639646,267549537327,271714313059,274877906943,275955675293,279619320384,283409262621,287892265141,290895076282,293250967838,297156747565,301539744347,305584861929,308746106614,311893404158,316042533103,320638141069,324688036139,328249606034,332359210323,337347289171,342275821912,346761134647,351594733113,356672391505,359786827693,361857554366,366800401401,372015693523,377586353290,381053767933,384555790527,389858258785,395698716786,400802704211,404894040790,409625834876,415776698302,421912798734,427096857742,432418175870,439020092774,444856893606,448297751501,454229490173,460678254242,467235015396,471166879044,475757344283,482338448097,489546396332,495716960076,500521852222,506013305524,513065554985,520422104899,526635245015,532400280190,539512205817,547740433607,549755813887,555449335758,562667588529,570828171147,579020265727,583780568462,588903243124,597126812018,605647465935,613183047523,618967811138,625796020766,634730588484,643648457758,651235575987,658346285502,666942210627,676837833443,686123438380,694646395069,704132488929,713897999717,719734800549,724253426794,733848810557,744087516863,755127280537,762061955326,769008312121,779495195662,791086140679,801301822005,809267958836,817906709682,829108088088,841060245968,851323281154,860649886224,871871416140,885087722778,892031635799,902210470405,914262321642,927500562652,938807093420,945638122828,955703644525,969142505541,983233819225,994236815456,1003523601665,1015654279551,1030429305270,1044451161969,1056129616777,1067972120378,1082718908929,1098750632177,1099511627775,1113220296122,1127064570939,1143152581703,1158754893323,1168032552050,1178482916967,1194527064799,1211322532259,1226294159581,1237819299609,1251346760218,1269041591994,1286803100755,1301823674227,1315281264360,1330972264667,1349530192987,1367695490983,1383723561344,1400162092041,1419611849747,1434843536665,1441787449686,1457659806163,1476929910171,1498328733799,1517827359147,1529418691290,1544606887649,1566269317559,1588881285160,1607419862979,1622491412803,1641450300317,1665159893754,1688099619727,1707365192764,1726318405880,1749661119556,1775588465620,1785635066155,1807866691191,1831197059868,1857050581420,1878489693872,1892285978844,1912331727524,1938614581662,1966449812796,1988356114907,2006827611730,2030841955880,2060127732673,2088104922760,2111091633063,2133187974042,2160080352755,2190590438955,2199023255551,2219018772137,2244373447568,2272033508181,2304699572525,2326875172464,2343997920091,2371922127805,2404430472823,2437135827219,2463465481975,2485122335815,2513749393190,2549503136784,2583118100616,2610943464644,2638145692354,2671879605587,2709611055723,2744229236504,2775337313142,2809037314809,2848411751733,2875100093395,2885146693930,2921086987313,2958261630807,3000203163123,3037244587195,3060318530894,3090814644491,3133141646461,3177772345055,3214650274488,3244646911339,3282188716098,3329169324667,3374908023515,3412915307290,3448469238402,3491052617422,3540120631942,3566718746534,3602742333481,3644535539609,3691645357928,3739543109190,3768662622150,3801657726254,3848852037976,3902759206622,3954963186366,3992884173265,4029729223464,4080018710749,4138384421944,4190537963595,4233434877447,4279595992671,4337039499341,4397710675450,4398046511103,4451594429268,4501655719022,4558698434365,4624000217353,4660735159550,4693013385121,4752284047181,4815312212227,4878692856995,4929530566039,4972650258418,5029429226153,5099591459257,5166128459962,5221477886218,5275488867219,5342316448771,5417274247427,5485999656578,5546103281332,5608549591157,5681643056377,5739143887493,5765742002085,5821761105618,5888908987177,5963678866109,6044242681715,6095537794614,6145655646345,6220774165781,6307189679445,6392099013585,6456349655240,6514851559279,6593768103939,6687887558728,6773656064211,6844378342091,6917741685025,7008919104928,7107321731173,7142275747607,7226931742410,7310693033831,7407110186098,7499100310748,7545881853480,7614100372434,7710545677988,7815515375350,7915937444190,7989849096933,8063464902909,8162570872614,8277363804312,8380778734450,8466124797557,8557677583317,8671485773438,8792182270942,8796093022207,8898914963868,8994572519734,9099602208579,9221763688319,9305862634027,9368484335566,9466296645227,9580554345105,9703221975299,9812905303865,9897195520868,9994507684321,10123533372403,10262152865811,10384983186850,10486078878704,10594870270028,10732152525883,10878425522323,11007090941658,11123974334762,11254781184366,11406629780378,11505368242276,11540322258710,11678526171678,11812348752853,11965808620463,12123100528101,12206617013030,12307113757555,12462829725169,12630827587577,12794630301185,12919379662972,13036115161327,13192000098767,13376955263569,13546907194412,13687602683775,13833166450536,14013802222209,14209456518369,14282092678785,14445018245200,14603122110891,14781245264956,14960907575812,15071604636112,15190245441184,15355205632404,15544233211214,15747464657014,15908443098479,16042851167213,16215281850102,16430723051848,16654251879396,16841332842090,17000930437983,17188638373967,17420040084611,17592186044415,17652081586534,17851469283749,18041716019787,18263700289294,18513951511551,18647643989883,18767254001120,18989219205509,19219458938951,19464908931211,19668982381581,19820717385464,20017659435543,20278345100519,20546765031767,20784479398118,20982844565881,21198686033941,21469363903079,21757733998019,22013031991969,22245280267092,22504652223974,22805984493151,23005549540576,23078185700992,23343933209068,23597694630625,23880847473535,24182671264131,24377467270139,24558729776750,24821502277631,25124787556319,25450686632313,25721348402344,25940046688081,26209789534423,26554256424251,26916404745207,27226316028940,27487009316687,27783508643995,28152192610494,28470611566738,28659172528192,28975443618511,29296497204153,29670330069672,30019319753827,30187966248593,30445780172798,30801567958362,31185267559414,31588009459312,31875599394611,32127831143019,32480489160712,32909172688096,33341395332952,33703859061090,34018959727208,34390686132708,34846319166648,35184372088831,35304641192431,35700634675744,36078446717628,36518454446183,37015441011520,37287642219361,37523203946192,37947055319959,38378939895581,38841755049347,39254275900243,39567712711323,39913935409154,40365735488845,40872252213333,41359129730792,41764199569557,42155328538183,42640512586271,43208508303647,43757737587297,44227246466923,44675647690654,45203548728606,45744378654909,46062797611153,46311254114726,46826912902260,47338213223940,47934030358966,48533271265378,48835610238476,49213034173918,49790787163871,50404726498365,51052918390523,51544581776192,51948548528483,52498148596255,53187517788615,53888160364719,54488338459208,55001804293089,55589372166649,56315683069727,56942106086850,57317673184400,57945914942836,58583098941602,59324438939334,60020990552096,60365827920353,60867137155260,61544749950584,62259787369116,63024426313478,63631743170382,64126442488073,64735437686785,65490523045164,66322938845646,67080478133136,67704246257638,68365118072606,69194769010522,70124913048854,70368744177663,70984053616237,71714255783610,72459156334649,73355741339100,74214990221647,74721970139345,75286697733237,76123410106413,77008543293612,77953350112793,78721237513971,79281390411274,80014602132280,80976054723285,81992735957677,82928517785134,83672412919211,84429037689195,85407321284351,86528913121567,87592019425809,88507298186416,89392490425797,90435691333297,91500055158558,92126478175681,92622314376831,93646549618580,94661545659230,95842893385517,97036431563616,97653470139714,98390341101452,99491805270543,100638727264697,101866181362825,102886019070625,103694155199396,104649373095939,105856258534009,107195191058979,108439607863928,109468445827195,110520446610789,111835281596793,113333421352501,114126481764960,115211300083160,116389903474264,117662705063255,119100119994009,120277787832800,121033224254071,122113610635497,123461623330353,124942573652578,126486621378171,127556847752447,128494424585192,129805389296151,131380781221650,133045654348200,134473099561326,135620961447694,136927186285450,138594839072966,140417073486286,140737488355327,142080357885017,143509102479505,144981862592446,146751374403024,148442161245408,149444151360081,150568229319667,152229648560182,153985984598564,155863883937613,157402259483969,158520607294974,159935091052036,161751592639659,163663153578175,165497924533207,167012461558698,168429592886181,170139896141103,172179197379655,174275669192115,176143854121566,177833563899801,179715215621311,181960194645647,183702165530164,184495225942623,186195353699397,188104159257874,190121861397904,192455861333109,194492778054447,195755194393416,197400308368734,199585033436766,201951116946190,204439971490964,206278085266418,207775814996466,209819991428431,212356835944935,215038390305877,217401617346460,219293374366905,221356223974645,224002160357317,226945986607853,228329507781136,230587656071433,232901592905302,235417553925743,238251429561582,240568639421089,242066465736912,244214778938247,246891194219412,249828877984081,252900315501229,255055729623683,256910948396426,259426896322579,262390319904356,265529334941000,268383943603832,270706616758094,273078965982120,275996154675112,279374388438634,281474976710655,282715277056043,285612299948761,288354010510590,291550497218104,295293615998148,297828647295124,299706526025783,302585257173661,305766864321129,309221981391913,312733649165909,315526002308518,317868805028913,320861931699087,324527607089344,328437738324361,331996819243411,334772509851610,337581204292617,341200772650081,345402490293135,349511489867203,353022578794154,356220560652355,359951063047611,364419233843603,367683474963180,369066996136463,372668013956450,376410695384807,380399416518189,385002803964606,389010800666497,391510617096993,394783008257914,399120842779594,403814862582645,408764199438842,412457989107652,415431555691400,419361987374615,424141912544015,429192488519175,433881868137039,437719078316792,441508558868301,446136050816215,451553585818289,455750645902770,458859131177609,463445863848562,468069226131901,473510691863751,478995781528312,482323873237747,485901879725180,490689416431535,495888725719033,501677842725022,507226427220356,511281196701934,515269113397647,520446965135853,526478724035534,532877709815325,538274904509829,542548324848076,547401195721048,553557608595016,560440880599012,562949953421311,566913107213663,572315953161059,577576784627000,583953223404928,591365220451456,596012982744316,599654652207896,605569606861752,611828249310550,618650846079771,625571443385695,631077266403409,635725396035240,641674202477326,648949720763675,656715178083874,663819929062525,669368937504078,674858452013979,681752307278971,689671247485015,697576432123007,704588484895133,710798044298912,717504713543413,725510439254849,733028562528944,737225622613425,741574408233652,749058163797323,756423236642491,765061189081855,774289397526460,780152520532871,785608405750963,793274673605196,801655590040162,810899824116935,819960076386265,826807199010452,833137918426560,841308896834940,851006331124878,861315448139686,870271723753240,877320834699686,884982400013665,894758381245097,905843370892147,912461443288514,919935686007817,928536513813414,937527847674611,948372457248531,959048695414636,965079978880779,972322666164346,981980302246559,992227665828739,1003653650044377};
constexpr long long d[]={0,1,1,1,1,5,5,11,11,11,20,30,41,53,53,67,82,114,131,167,186,206,248,270,339,387,462,540,567,623,739,799,923,1083,1149,1319,1529,1601,1712,1978,2212,2292,2579,2999,3171,3479,4019,4295,4389,4725,5362,5962,6166,6686,7693,8341,8561,9345,10656,11120,11592,12252,13594,15144,15900,16284,17649,20025,21365,22181,23630,26500,27991,29143,30311,31791,35091,38435,39975,41535,44063,49103,52829,55125,56951,60395,67195,68915,72743,75559,79208,85778,93422,97654,101746,105318,111113,123017,129225,135497,140645,147945,161681,166577,175023,182719,189649,198023,213110,228662,235638,247518,256842,269610,293227,308275,322995,336683,348851,365371,396430,396910,422078,437694,457374,476842,508092,540474,557238,584118,608886,630986,659675,712739,732423,768871,800731,833915,871042,931210,934407,988867,1025527,1072103,1114431,1159071,1228671,1287363,1309707,1380747,1434983,1495583,1560211,1664483,1707323,1787557,1860407,1941527,2014689,2098271,2162507,2238987,2327537,2396225,2512933,2612645,2724020,2867444,2982006,3032910,3186700,3310800,3455808,3586872,3732019,3885835,4039835,4163387,4323395,4515635,4696783,4895323,4972429,5176997,5353775,5505391,5760691,5993191,6238909,6481617,6716544,6884504,7143882,7384266,7640570,7988994,8304894,8653382,8907512,9265892,9518423,9865223,10289333,10713129,11134557,11333049,11570234,12008396,12373544,12802024,13252628,13758308,14350796,14928072,15397524,15673584,16304394,16787154,17342240,18103060,18836272,19582072,20082416,20615216,21286669,21985997,22731197,23518581,24472889,25482473,25633384,26517044,27324158,28043358,29022657,29951403,31048383,32367151,33652639,34691033,35232129,36085809,37324067,38506479,39811875,41188035,42807975,44588031,45423385,46922793,48114009,49622509,51238447,52883251,54947225,57216969,57576774,59471942,61175081,62378393,64079505,66227105,68366783,70687055,73276027,76190587,78282762,79182374,81822470,84040974,86498020,89371090,92215506,95704178,99669230,101542020,104777670,107231586,109508803,112763071,116430805,120230405,124303781,128530679,128945840,134136224,137350169,140046577,144257441,148379297,152879605,157858325,163286639,169641143,174310098,176319588,181974443,186567771,190394616,195840268,202240662,208771062,215800014,223299580,227089201,235045185,239516180,245426876,252472526,259693894,267793711,276369551,285326040,286162512,297520030,304669810,310529125,319396085,326921348,334741286,344764266,355956586,367597330,379943132,387964191,392491767,406937042,415392178,424791466,437131482,449553864,463342914,478182306,493936702,502076221,519518035,529435710,542126430,556812216,569191128,583722363,601683203,621032907,630194061,641454408,663186264,676068564,689958734,710468516,726216212,744257418,765631218,788085039,812531087,838522830,855321192,864950212,896458704,915156579,935337397,961055439,982786119,1007137735,1037634787,1070929147,1093879711,1119856761,1152067323,1170899561,1202029417,1233409915,1260788435,1293924671,1330687943,1370134931,1385532511,1412949136,1458476720,1485581512,1515573922,1560338370,1594593470,1632674039,1674030123,1713566447,1759754735,1814035885,1859779587,1884180324,1924531936,1983341345,2017916405,2066688572,2123194588,2170059052,2225616992,2288775122,2355987014,2399902757,2458306073,2525552336,2565160336,2632468988,2701004762,2760050710,2829371858,2897664983,2966962687,3033334212,3050247036,3145425426,3219864206,3275029037,3354135509,3437765944,3509489788,3596548073,3687295977,3774267165,3874518613,3985825963,4074402703,4120973302,4213751268,4336260951,4408729335,4513788060,4636731234,4737785481,4854002889,4972787412,5090569572,5212696439,5291511815,5443588776,5549749082,5653374782,5803004314,5930236427,6060752981,6216126934,6364579414,6518741548,6615623528,6695602748,6888910136,7031984756,7146767762,7320378092,7494489260,7646596092,7834553892,8030790757,8215318853,8414711786,8617909020,8816738105,8945948897,9048269369,9315707935,9511318588,9682641448,9929365421,10157428949,10375607976,10637167560,10895491800,11155584108,11369949250,11578766170,11881868676,12084972126,12309739920,12629761112,12894431573,13172178983,13507663408,13827428784,14151685752,14377018776,14494680336,14840992176,15187477640,15411993240,15689772819,16090784243,16413011938,16760807146,17163235700,17549549676,17953050960,18394588980,18838997990,19221443366,19447743184,19757347804,20292765049,20666575945,21031659720,21562727418,22035878220,22498244720,23061352187,23617011469,24164291565,24623722341,24973793896,25559979716,26068856123,26419221691,27009173051,27649071581,28178890689,28819311041,29496463859,30145571843,30860835773,31143212645,31613368309,32371330773,33012998499,33483710819,34146945903,34937142195,35580884590,36321079654,37174707604,37981677342,38841222774,39789375078,40734526153,41561029353,42045072492,42544541224,43546556173,44467196203,45085386563,46014892571,47133591914,48048845584,49108761595,50267778715,51379254018,52579251774,53365700394,54352789482,55573903402,56499580882,57337555344,58627906284,59872729197,60953721197,62319643034,63740577146,65100346634,66626607216,67257265371,68239335399,69840547198,71219370220,72116442240,73290942000,74908671894,76265194336,77568278104,79253992888,81016830743,82687683119,84551091764,86487508276,88446771581,90020689781,90847691921,92405759289,94528050441,96210865757,97612233907,99701765491,101883531162,103730995452,105984216219,108420282339,110740249618,113292901036,115002294348,117077239340,119671215335,121653406043,123146517440,125485154552,128199089263,130304939093,132697714292,135700394532,138559414758,141480994848,144713488833,144842621769,147975081366,151358184440,153879734840,155837440040,158821086510,162071407318,164763006358,167657263826,171223796906,174706274684,178151176928,182082340160,186137677250,190253982870,193628120390,195422543558,198683275071,203170911427,206770867432,209326288608,213074313723,217703969877,221407433259,225352632759,230358483330,235298002408,240201336991,245642116543,247908272793,253348429389,258626906010,262180092330,265945749274,271406774494,276663596372,281024928516,286354456824,292489243070,298168027750,304252553890,311046695881,311116812081,317853258072,324979044312,330398304456,334561707840,340833174904,347718457112,353134662722,358383855232,365295299450,372462561770,378973113653,386406071653,394792405336,403177017104,411864061556,417708116612,420083048362,429225947994,438473870796,444966712116,451062184018,460059808258,469135432120,476658745684,485417832943,495757252503,505525857118,515677133680,527103892204,531625524084,543192675243,554352437113,561992743721,569925268937,581408198183,592559540989,601027840564,610627229844,622930788863,634486327967,645618459635,658875923915,666638444744,673066208130,687225040595,702288418283,710893192373,719342102829,734700654219,748277595307,759201191471,771564523151,786741441233,801018082161,814728392775,830612395503,847649891688,864532412904,882590288904,894624836360,899356304450,918838970450,938320042252,952248306316,965105758031,983984046031,1003185743986,1017971393968,1033755851223,1054185857451,1074111705473,1092874562363,1114866923564,1132154954268,1148043950359,1172343968605,1194479185995,1206069481819,1224893272150,1251051416558,1272334870612,1290409645492,1313157654048,1338928609416,1362061360254,1385949950938,1413832745513,1425191742239,1442318417690,1471073437074,1502449285062,1519976863922,1537564081373,1570129839785,1598846470835,1622074036625,1648057541270,1679971067254,1709290460214,1735226087940,1765155301208,1799120937868,1832094733918,1866169473778,1897620886678,1915685907526,1939309544626,1980163484150,2019740162666,2041244622610,2070133357121,2114224301621,2151275181013,2182075694773,2219325481297,2262799270981,2302532270931,2342433413415,2388872819138,2419314390210,2455605602541,2505314658821,2551188533305,2574642353809,2614235569072,2669456834324,2714605361054,2752855256994,2800537696513,2854756361473,2901453830336,2945705031176,2999178162539,3040344922807,3056329672311,3111226093677,3170788269952,3222478593744,3258660103017,3309808327399,3376586030259,3430537376019,3473494579220,3532145904710,3601354798646,3659715167510,3716634548820,3783572157492,3854129109416,3921599072844,3993586104168,4054410289768,4086177153512,4142704190936,4225894098594,4307930667698,4351488458528,4411945153640,4505009157188,4583368393724,4648550633949,4726565965149,4817846314338,4898452933952,4972820545809,5061144098469,5141019682509,5193553068297,5287849758570,5384151013138,5457682789994,5521085725484,5618817075227,5731444047643,5811051113353,5887219177193,5996257718308,6108641142052,6202920798244,6302698208376,6419667704838,6473117185098,6536414026527,6650179706067,6775757124032,6872291215808,6944870502533,7057850101083,7194459212533,7305493936357,7393932630432,7516963335382,7663041140728,7786284570232,7906026014488,8046235078744,8192095313604,8324163332368,8459730357532,8596475184124,8679724395316,8751844061956,8909762036324,9074826993888,9207602382006,9312968083038,9470349698078,9660213677846,9801735572360,9927727495448,10104991322732,10297188372332,10458739337654,10624441443734,10818910302984,10951139687614,11090264458264,11286835772680,11483583771595,11618558675659,11755438105144,11963286758804,12194471256530,12357294076214,12514905317025,12743863285761,12980856070531,13179783975333,13388961940665,13633802496429,13755639059849,13873077526259,14091339951237,14328369552301,14557448516677,14701136062201,14878503099076,15147398980720,15399037753622,15606051412712,15821712384701,16107671552701,16391655892519,16621556797123,16870885093889,17177205326289,17479443049809,17755710161665,18054900528671,18315230642855,18452879264560,18666315752870,18994239799166,19335128793766,19580227317542,19801333460894,20140058433014,20528647644150,20818369216680,21078172265536,21449663710722,21854452808322,22194884863441,22542167155897,22948689409468,23233346440252,23498477812262,23872253629802,24266801279149,24595160084269,24822645489817,25177981591847,25636212688768,26041537182592,26370782816221,26765263866243,27267945750063,27716262933903,28091530514654,28542412014578,29068659238222,29179903289462,29557909989029,30024718530021,30546479527545,30960431424057,31254169220932,31688885166722,32242877099999,32743510789023,33146523852886,33601300166656,34203629815738,34783877076674,35255621737445,35773347857459,36415886881179,37051875070275,37631975907130,38257704452068,38812084358911,39108077289151,39510777848636,40135459880972,40801996665066,41391083771754,41782938603864,42344091063292,43111120039252,43804455081196,44370436961608,45013536244908,45845026650216,46617833992152,47256241663777,47994181003057,48871965792137,49314047915181,50005236019392,50813410446684,51636666615713,52215388439393,52751021637887,53556692906289,54500221625052,55284862089012,55942158478587,56780134928457,57825136956503,58740451028087,59510742325058,60449254219008,61553255172904,61795844936416,62581770735298,63559781709180,64649128498230,65532681810438,66126550222864,66948564773014,68023651008105,69070736416145,69928416793589,70719064696831,71796611926238,73030933095326,74106538922161,75120143679207,76330527166821,77677923971445,78885499321814,80034937775384,81368974007020,82400717319436,82859909315443,83985788613343,85328944894293,86746990849617,87794673465254,88667848644196,89973493478410,91550892130410,92905663896758,94022843798762,95383390464464,97117935562704,98693931625134,100002290504410,101534792101002,103373566234506,104310980214069,105752087653559,107441676964043,109169841731383,110405870020060,111456169722382,112982374556627,114816227314619,116537487051269,117849641329465,119274534350596,121218796139776,123246254557486,124971782800064,126715939821539,128867014053859,130661455149859,131097361639135,133039314959377,135028053189741,137359044802929,138906612409589,140128010913871,142167533137039,144448767509892,146544247251060,148208740228185,149982808539585,152354150024904,154836362026500,156950264155117,159011981419997,161549045380049,164334527019865,166799229415300,169167119113864,171945587928304,174114739459468,175087457434297,177429290654081,180235705621344,183201904646994,185435748563256,187164865692228,189633261705402,192693150729266,195605944484406,197890331252982,200219394053942,203395850029546,206827167759124,209774359333724,212674008711920,216207265881344,219517911549188,221269113555196,224519438163481,228016687665175,231543508700440,233642045205268,236119291256336,239678311382716,243568289904376,246867274789032,249531674141724,252774480674988,256928421541913,260957782645553,264349798997438,267949130697556,272442923712384,275859605107104,277024672693454,280988736681916,285093244124587,289952818856267,293210868944252,295769367174068,300014949737317,304783650236133,309188783282931,312634539989581,316068241610085,320599090418025,325622089924863,330052675131443,333952594166468,338456720467212,343928642963468,349340171913086,354269530608851,359586488921451,365176990811043,368609099490219,370893111010538,376350014137178,382112911931988,388274061634290,392112489644091,395992730678243,401873167976365,408356076357475,414026606386650,418576172662498,423842659480216,430694721336780,437536473318460,443321883171388,449265795520364,456646738619036,463178118750044,467031879592444,473681358643756,480916871929174,488280114705116,492699529445468,497863802839343,505274125733907,513397483394752,520357879297984,525782602530818,531987944762078,539964038902469,548291653405117,555331141156545,561868691044995,569940726631640,579287993401080,581579480779440,588058708668638,596280298574807,605583362759327,614930542675107,620366808398477,626222025537143,635629788351879,645385937086844,654021713586692,660656837453097,668495622106041,678761440414023,689016990079123,697749763160702,705941300521982,715852402191107,727271950920771,737996824623006,747849362555490,758824773151510,770133234644014,776898086808302,782139693252502,793279933801345,805177310528917,818016555681779,826088517136175,834181022802350,846408729011156,859935361845995,871867277634763,881179691590202,891287030080022,904403844193448,918411773228808,930450313501986,941399747854166,954585045505466,970127422111754,978300407737471,990291074903339,1004500207511762,1020121331903562,1033474344740570,1041548621500826,1053456133668377,1069367745111321,1086065951826861,1099115505356827,1110138920586910,1124550165915478,1142117671495369,1158803680967179,1172712720643507,1186828984935899,1204421903677242,1223563781235354,1224473170974964,1240868738317976,1257440335273925,1276713772169197,1295420943801577,1306554134273977,1319105022539294,1338390088233358,1358595035587738,1376620874883426,1390508668617166,1406822786111620,1428180448065252,1449636350648540,1467796223976188,1484079908037118,1503081709408895,1525573918532735,1547608425001883,1567066502420137,1587039317216992,1610690222587488,1629227185566694,1637684871626272,1657033274171735,1680542801061495,1706670764711283,1730498084886539,1744674284097428,1763264636440844,1789801113080594,1817523385359420,1840270220343333,1858778083527205,1882078556281911,1911241356209421,1939480158882184,1963215344863768,1986584656635796,2015389565311980,2047409837701020,2059827435962280,2087327956131812,2116210952553938,2148243465756866,2174827965197346,2191949154847598,2216845974708158,2249515562401692,2284142589932388,2311415936060583,2334431421102041,2364377308257091,2400925957694755,2435869468113418,2464602855992168,2492245378556897,2525914636705573,2564143774714173,2574718526725557,2599812900040987,2631658372382323,2666427068572864,2707520977517616,2735440057840817,2757014719850837,2792227145778191,2833252677190907,2874559539793055,2907840223404639,2935236143512239,2971477998148989,3016777991282587,3059401765421563,3094712152373095,3129258981564795,3172134785283938,3220129189856930,3264198133991143,3303829823627955,3346797325753380,3397039107268404,3431120119570778,3443959675054508,3489927310291365,3537510853963685,3591237956860481,3638725062520785,3668328932286602,3707485942145150,3761876139676600,3819271218068484,3866733113248755,3905368781512843,3953760167847194,4014365152901204,4073413813113972,4122519223751272,4168490456679088,4223593349130968,4287136427934368,4321607584445600,4368330176715859,4422577758270003,4483773412266384,4546040488906984,4583924975267944,4626884600811352,4688378788985118,4758673736899502,4826799930465422,4876324739355516,4924481219965609,4990259869334389,5066660585288644,5134981724851454,5191219578911426,5251782962085314,5327206286343024,5406928211750250,5407369835633945,5477838895939085,5543769614545103,5618951913367177,5705084965128349,5753575088828389,5796214624807680,5874570440051000,5957956702406858,6041872676079690,6109232640562990,6166409352657544,6241755042841889,6334930488404001,6423358162340946,6496972899261426,6568861514973757,6657875853601021,6757794599209469,6849474295016903,6929712634063493,7013140903989693,7110866866988833,7187802979022041,7223417854460729,7298483453194949,7388528762365568,7488869939892312,7597067144251170,7666007775987426,7733416286565621,7834525813726477,7950927510631885,8065385293052605,8152059408645200,8231036979097850,8337653230933510,8464902733808238,8580947521726737,8676705485976257,8776112815651827,8899749397040295,9033281760854760,9080749315172132,9195796812109409,9309712168441969,9440935912677356,9566226462450656,9629989705194372,9723039765047628,9854687607128838,9998076213725330,10135353181829610,10236464322782034,10337244361163178,10473019539659028,10630400649016986,10772285933166322,10889466077812233,11015259605446473,11171745866862848,11337824247428352,11343209351920257,11484897987529115,11616809757068329,11761750727674429,11930455731195369,12046680474163825,12133286287392262,12268658523963086,12426905438294116,12596922773743000,12749053550464042,12866048371664206,13001214966700423,13180560673134403,13373380388464931,13544360195351219,13685186494103841,13836841693609497,14028350440527222,14232547543557462,14412293134368457,14575696117927849,14758694900523845,14971282934940645,15109615520059743,15158621051100211,15352521140994315,15540408044964015,15756019158956065,15977171581095093,16094679275390196,16236178691681396,16455582490049522,16692459476044802,16923585104945690,17099731203788934,17264678462964549,17485099764504709,17746811322699539,17987463256773227,18186828765200598,18393238186467696,18649560346471683,18927389447018883,19030605430970019,19262285586412149,19487267387290442,19740914758679002,19996933551648802,20154787559636602,20324087988474346,20559651141536506,20829771551655996,21120392519149996,21350752668886411,21543225023313499,21790318191893436,22099260875197200,22420024742728580,22688673005157164,22918014750455405,23187938762400397,23520925824017113,23768816006134873,23855125482328352,24142642541712382,24417168581815216,24737713866983324,25099326883144689,25292646206812761,25465721893072700,25787127509027972,26120744882785430,26476647371562430,26772757948049300,26993077173687416,27279233972452203,27658270929327307,28048821929293147,28394934046700203,28683952096130894,28998648956562374,29393567967634716,29814588306247116,30187578675408066,30527125653637892,30906586826556258,31347737268631386,31640100063109011,31746584674278867,32136436268626359,32508958035472035,32924909561706825,33368590533882945,33655135458720713,33921953868452105,34309017762249818,34756060263035930,35236761400127080,35636258172692836,35959275540726385,36357955467619861,36867421997675473,37403401512690353,37862380123898926,38248727576339980,38688436078737744,39235563085022260,39708415235044600,39988616823765244,40458911935069597,40936639670504893,41493276807262684,42013271436653634,42264723360349740,42649381735263600,43180572899110652,43753820103082340,44355919243429850,44786153786637154,45163744714003930,45692026424508044,46334623032056660,46982956999340660,47527015055275798,48000296255785034,48559001043251534,49244273126297294,49753042774182709,49934168044204309,50530930223557000,51100670782718072,51764642445107567,52515092158766437,52926388183814188,53282557514782660,53923844643292131,54577717890783839,55278882848739329,55904264458697665,56379748101106025,56905314156413483,57591598477464112,58361503898685872,59102044602741011,59718560897341341,60314250316558739,61053670805844851,61919864274843251,62757988161693151,63474928220882053,64160085290743021,64967245977771629,65794715765015219,66282215187024783,66662850550498619,67453355471788241,68237690165245361,69152269467510271,70072703499759103,70537398501410729,71117876514120525,72007038365658192,72952504940778952,73951368646594430,74709513587296028,75332834286081041,76181416790721009,77246492192917209,78329685615573993,79258161127748476,80053006238596264,80963148874740704,82088930774511604,83060512874069377,83643393009466977,84619052460318085,85609236394400449,86762020090873709,87845854400331381,88382766182707530,89163805970692636,90220204318602752,91335662691512672,92529264083661754,93477893014145802,94251108047696835,95203576538482403,96385285124345538,97688848267900350,98875912331397180,99853980750616316,100890888628301108,102193440600829228,103654696885048800,104037999419536548,105005881166413450,106155219377858552,107328437745744977,108741455712759753,110096491200536372,110896505510663816,111788210381419284,113110215931037364,114509611499998983,116004295887943325,117219861644008099,118107143833336051,119269284411130561,120794148220464491,122407621339444595,123893642881446311,125075692249494664,126278725633769224,127835174833662420,129620749038510292,131314277381167798,132773231725575356,134185113347388051,135850061995758051,137549851024699868,138550875006062422,139343717091701272,140982493478499672,142607502139580322,144500021197092096,146413262896584793,147402992772645985,148585670666235475,150354622121795621,152197725766401099,154171471956190923,155812390828041123,157113489995362433,158652346026693206,160597845352862046,162757543515638656,164766032238826342,166427605549502547,168127638815790451,170253726988158919,172677717112894463,173961681920665584,175719087596149584,177629603693129168,179694087870472570,182027012303086312,183939544873282896,185167129057848271,186923837314046947,189117053968577659,191528041093159959,194043294838150956,195787763828220836,197316951642427931,199456446050713019,202029061065052886,204749463753835586,207083336677296596,208961238723394644,211099528782801216,213831144048752424,216817786252183904,217343266637411144,219546915535632434,221892914159781730,224312659025343793,227221736441934025,230003080797655705,231652356526407463,233503712925845605,236241731834214325,239137929961506243,242236463870937093,244776321897970849,246623832481751109,248961974132174595,251966467758103037,255130101111347017,258168481812880009,260678069664118596,263027673405085410,265865066505001008,269250306560997328,272732546241493388,275837469594240950,278647456955445755,281778525420038395,285516415495557835,288418538989163157,289740570696732310,292576383795031342,295762180272129455,299131742845979555,303031856737707110,306437581495784246,308549604030879383,311303524825561715,314962939314515315,318928495276309939,323102304347895937,326186659263107749,328701347479858341,332135563885559541,336399999517802765,340910373952907209,344887685062208398,348073403884637778,351549305473679678,356010354214864670,360976589099518902,363311972840020606,367125985302332239,371036538551570849,375291028637136580,380085946212976168,384008982505121519,386546300284125681,390187691160388506,394726891477244346,399712140825887639,404927441730004943,408589490324054289,411743362237717389,416022989660103642,421066736596288096,426412479203692828,431276732365158556,435236890093175266,439284117869363622,444263758968300966,450033782236396542,453623687593280431,455744601183893911,460701407353334409,465395215835185657,470870797565157139,477286503154152555,481634081828466395,484856521730277239,489799303111183765,495265304190533789,501204650435211485,507244719006484605,512050358764914694,516084665049434884,521241822302144686,527561446674947754,534306423055352079,540449396721632379,545243014401992052,550096438396052148,556354672086107404,563623643608590824,570736321871302532,576817527892781664,582359630453043997,588828321606417901,596580597937464021,602247320521049693,604650496799042264,610909065770179670,617417588774092493,624357963546177173,632372461090389170,639354391345083292,643711571383437820,649418621568084044,656988142808415644,665183901384542690,673830392872318849,680287137213398729,685487905168373981,692366160614000231,700735809585619631,709584418694099951,717804901164215543,724535367819502305,731185906187400600,739311782047937584,748830391046581602,756208822675099200,761676648273541001,769749297774418281,777891038755378260,787478901374897960,797149114453519003,803019868228962343,809335049679281588,817789839502704518,826977019013713484,837212177880302036,847027623852547882,854204565834940942,861267166303048665,870442319583149697,881136628112284110,892488428885633344,902068449468377944,909658043989104616,918281595530375860,929227697620290964,941473038515399848,945939188139092068,952997565043270980,962625436521530652,972005499025303455,983381065805127007,996611480533179487,1004912383988227447,1011420047319644907,1021995986240739435,1033192697581639057,1045405145798544647,1057799935573454531,1067666370421198019,1076000466851071002,1086672625608173286,1099732180932169741,1113678942279247145,1126446179787882992,1136423296965795286,1146298933569107185,1158707873046092785,1172969884357178029,1187215027074839613,1199857758222982791,1211059803387400107,1223165341373724412,1237623682008577828,1251208930764867493,1258797215397609141,1266664168584599784,1280209766154844294,1293547913077443542,1309199882897571110,1325930624807639975,1336566329941269529,1346468761612106509,1360390704035393637,1375618829197726859,1392424846749300173,1408905445627211443,1421367208803231783,1432895448859964451,1447782971520032811,1465461394230589785,1484265223665599577,1500610426660335627,1513482103248546023,1527479783077185656,1545350276768243352,1565624722832697802,1577735795318049412,1591421133737093205,1607177850276946909,1623658965244521010,1643547979203090290,1663138876237892965,1674212312681731513,1687517129221644092,1705267864340751586,1724112765968380606,1745136576925154526};
void solve();
int de=0;
long long calcdp(long long n)
{
	if(a[de]>n||n>=a[de+1])de=prev(upper_bound(a,a+1842,n))-a;
    return d[de]+de*(n-a[de]);
}
main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    int t;
    cin>>t;
    while(t--)solve();
}
void solve()
{
    long long n;
    cin>>n;
    cout<<calcdp(n)<<endl;
}