/**
____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|
**/
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const ll maxn = 1.6 + 10, maxnum = 150;
vector < vector < ll > > st;
ll gcd[maxnum][maxnum];
vector < pair < ll, ll > > p;
void precompute()
{
p.push_back({(ll)0,(ll)0});
p.push_back({(ll)500000,(ll)6415551});
p.push_back({(ll)1000000,(ll)16875563});
p.push_back({(ll)1500000,(ll)27398715});
p.push_back({(ll)2000000,(ll)37996375});
p.push_back({(ll)2500000,(ll)47466703});
p.push_back({(ll)3000000,(ll)58218911});
p.push_back({(ll)3500000,(ll)71702511});
p.push_back({(ll)4000000,(ll)85307503});
p.push_back({(ll)4500000,(ll)102168543});
p.push_back({(ll)5000000,(ll)115369951});
p.push_back({(ll)5500000,(ll)133960639});
p.push_back({(ll)6000000,(ll)145427647});
p.push_back({(ll)6500000,(ll)163659647});
p.push_back({(ll)7000000,(ll)177042815});
p.push_back({(ll)7500000,(ll)195509247});
p.push_back({(ll)8000000,(ll)216122559});
p.push_back({(ll)8500000,(ll)239768959});
p.push_back({(ll)9000000,(ll)265554303});
p.push_back({(ll)9500000,(ll)274333407});
p.push_back({(ll)10000000,(ll)284435415});
p.push_back({(ll)10500000,(ll)294690527});
p.push_back({(ll)11000000,(ll)306146687});
p.push_back({(ll)11500000,(ll)315099055});
p.push_back({(ll)12000000,(ll)325960347});
p.push_back({(ll)12500000,(ll)339810053});
p.push_back({(ll)13000000,(ll)352927583});
p.push_back({(ll)13500000,(ll)369956363});
p.push_back({(ll)14000000,(ll)382573487});
p.push_back({(ll)14500000,(ll)400829151});
p.push_back({(ll)15000000,(ll)413083375});
p.push_back({(ll)15500000,(ll)430289115});
p.push_back({(ll)16000000,(ll)444714719});
p.push_back({(ll)16500000,(ll)462230715});
p.push_back({(ll)17000000,(ll)482943919});
p.push_back({(ll)17500000,(ll)507589687});
p.push_back({(ll)18000000,(ll)531634543});
p.push_back({(ll)18500000,(ll)549603639});
p.push_back({(ll)19000000,(ll)572835271});
p.push_back({(ll)19500000,(ll)591206111});
p.push_back({(ll)20000000,(ll)616833207});
p.push_back({(ll)20500000,(ll)647032575});
p.push_back({(ll)21000000,(ll)678626151});
p.push_back({(ll)21500000,(ll)711878335});
p.push_back({(ll)22000000,(ll)752552943});
p.push_back({(ll)22500000,(ll)805651231});
p.push_back({(ll)23000000,(ll)822161563});
p.push_back({(ll)23500000,(ll)843482731});
p.push_back({(ll)24000000,(ll)863457079});
p.push_back({(ll)24500000,(ll)891401143});
p.push_back({(ll)25000000,(ll)921961143});
p.push_back({(ll)25500000,(ll)954081007});
p.push_back({(ll)26000000,(ll)986877423});
p.push_back({(ll)26500000,(ll)1030753663});
p.push_back({(ll)27000000,(ll)1075004959});
p.push_back({(ll)27500000,(ll)1081891135});
p.push_back({(ll)28000000,(ll)1092852607});
p.push_back({(ll)28500000,(ll)1105360703});
p.push_back({(ll)29000000,(ll)1113627215});
p.push_back({(ll)29500000,(ll)1124345895});
p.push_back({(ll)30000000,(ll)1136479039});
p.push_back({(ll)30500000,(ll)1147864327});
p.push_back({(ll)31000000,(ll)1162610431});
p.push_back({(ll)31500000,(ll)1178677551});
p.push_back({(ll)32000000,(ll)1193154399});
p.push_back({(ll)32500000,(ll)1210258439});
p.push_back({(ll)33000000,(ll)1223833215});
p.push_back({(ll)33500000,(ll)1242246975});
p.push_back({(ll)34000000,(ll)1256156415});
p.push_back({(ll)34500000,(ll)1275608991});
p.push_back({(ll)35000000,(ll)1295885951});
p.push_back({(ll)35500000,(ll)1318396767});
p.push_back({(ll)36000000,(ll)1343045023});
p.push_back({(ll)36500000,(ll)1349767503});
p.push_back({(ll)37000000,(ll)1360744639});
p.push_back({(ll)37500000,(ll)1372723239});
p.push_back({(ll)38000000,(ll)1381436783});
p.push_back({(ll)38500000,(ll)1392250783});
p.push_back({(ll)39000000,(ll)1403603775});
p.push_back({(ll)39500000,(ll)1415848495});
p.push_back({(ll)40000000,(ll)1430406463});
p.push_back({(ll)40500000,(ll)1446351887});
p.push_back({(ll)41000000,(ll)1460534079});
p.push_back({(ll)41500000,(ll)1477976287});
p.push_back({(ll)42000000,(ll)1491402959});
p.push_back({(ll)42500000,(ll)1510266687});
p.push_back({(ll)43000000,(ll)1523149631});
p.push_back({(ll)43500000,(ll)1543530911});
p.push_back({(ll)44000000,(ll)1562765119});
p.push_back({(ll)44500000,(ll)1585478047});
p.push_back({(ll)45000000,(ll)1611914303});
p.push_back({(ll)45500000,(ll)1628776287});
p.push_back({(ll)46000000,(ll)1649817455});
p.push_back({(ll)46500000,(ll)1671615167});
p.push_back({(ll)47000000,(ll)1698972831});
p.push_back({(ll)47500000,(ll)1729577279});
p.push_back({(ll)48000000,(ll)1761883295});
p.push_back({(ll)48500000,(ll)1795240223});
p.push_back({(ll)49000000,(ll)1842813439});
p.push_back({(ll)49500000,(ll)1882658863});
p.push_back({(ll)50000000,(ll)1901206079});
p.push_back({(ll)50500000,(ll)1920994935});
p.push_back({(ll)51000000,(ll)1946481871});
p.push_back({(ll)51500000,(ll)1974952319});
p.push_back({(ll)52000000,(ll)2003982143});
p.push_back({(ll)52500000,(ll)2036655551});
p.push_back({(ll)53000000,(ll)2070011519});
p.push_back({(ll)53500000,(ll)2118481055});
p.push_back({(ll)54000000,(ll)2150901447});
p.push_back({(ll)54500000,(ll)2162578879});
p.push_back({(ll)55000000,(ll)2176517631});
p.push_back({(ll)55500000,(ll)2187445535});
p.push_back({(ll)56000000,(ll)2201334879});
p.push_back({(ll)56500000,(ll)2217529215});
p.push_back({(ll)57000000,(ll)2234282879});
p.push_back({(ll)57500000,(ll)2252930943});
p.push_back({(ll)58000000,(ll)2271519199});
p.push_back({(ll)58500000,(ll)2288950847});
p.push_back({(ll)59000000,(ll)2311617791});
p.push_back({(ll)59500000,(ll)2328804095});
p.push_back({(ll)60000000,(ll)2351859151});
p.push_back({(ll)60500000,(ll)2381624831});
p.push_back({(ll)61000000,(ll)2406329471});
p.push_back({(ll)61500000,(ll)2421732607});
p.push_back({(ll)62000000,(ll)2435126231});
p.push_back({(ll)62500000,(ll)2450469759});
p.push_back({(ll)63000000,(ll)2459301631});
p.push_back({(ll)63500000,(ll)2473415167});
p.push_back({(ll)64000000,(ll)2489588799});
p.push_back({(ll)64500000,(ll)2508047487});
p.push_back({(ll)65000000,(ll)2525897215});
p.push_back({(ll)65500000,(ll)2550304127});
p.push_back({(ll)66000000,(ll)2565647071});
p.push_back({(ll)66500000,(ll)2586302079});
p.push_back({(ll)67000000,(ll)2604318975});
p.push_back({(ll)67500000,(ll)2626520767});
p.push_back({(ll)68000000,(ll)2655912223});
p.push_back({(ll)68500000,(ll)2686501087});
p.push_back({(ll)69000000,(ll)2708542783});
p.push_back({(ll)69500000,(ll)2734727487});
p.push_back({(ll)70000000,(ll)2765834239});
p.push_back({(ll)70500000,(ll)2804160063});
p.push_back({(ll)71000000,(ll)2843599615});
p.push_back({(ll)71500000,(ll)2888099135});
p.push_back({(ll)72000000,(ll)2952562687});
p.push_back({(ll)72500000,(ll)2973086335});
p.push_back({(ll)73000000,(ll)2997065455});
p.push_back({(ll)73500000,(ll)3026760255});
p.push_back({(ll)74000000,(ll)3065024959});
p.push_back({(ll)74500000,(ll)3105941151});
p.push_back({(ll)75000000,(ll)3146055935});
p.push_back({(ll)75500000,(ll)3206650111});
p.push_back({(ll)76000000,(ll)3227129983});
p.push_back({(ll)76500000,(ll)3240473711});
p.push_back({(ll)77000000,(ll)3255846975});
p.push_back({(ll)77500000,(ll)3264840895});
p.push_back({(ll)78000000,(ll)3278828671});
p.push_back({(ll)78500000,(ll)3294933183});
p.push_back({(ll)79000000,(ll)3313567167});
p.push_back({(ll)79500000,(ll)3331425695});
p.push_back({(ll)80000000,(ll)3355677279});
p.push_back({(ll)80500000,(ll)3371116031});
p.push_back({(ll)81000000,(ll)3391663775});
p.push_back({(ll)81500000,(ll)3409895679});
p.push_back({(ll)82000000,(ll)3432176127});
p.push_back({(ll)82500000,(ll)3461385343});
p.push_back({(ll)83000000,(ll)3490534749});
p.push_back({(ll)83500000,(ll)3498415007});
p.push_back({(ll)84000000,(ll)3512710399});
p.push_back({(ll)84500000,(ll)3526894463});
p.push_back({(ll)85000000,(ll)3540038895});
p.push_back({(ll)85500000,(ll)3555702463});
p.push_back({(ll)86000000,(ll)3569993471});
p.push_back({(ll)86500000,(ll)3591398015});
p.push_back({(ll)87000000,(ll)3608216127});
p.push_back({(ll)87500000,(ll)3627815423});
p.push_back({(ll)88000000,(ll)3645338751});
p.push_back({(ll)88500000,(ll)3664056351});
p.push_back({(ll)89000000,(ll)3685690367});
p.push_back({(ll)89500000,(ll)3711275135});
p.push_back({(ll)90000000,(ll)3739951615});
p.push_back({(ll)90500000,(ll)3764683919});
p.push_back({(ll)91000000,(ll)3793916223});
p.push_back({(ll)91500000,(ll)3816256767});
p.push_back({(ll)92000000,(ll)3855889919});
p.push_back({(ll)92500000,(ll)3893864703});
p.push_back({(ll)93000000,(ll)3931024255});
p.push_back({(ll)93500000,(ll)3980723327});
p.push_back({(ll)94000000,(ll)4030969519});
p.push_back({(ll)94500000,(ll)4060193567});
p.push_back({(ll)95000000,(ll)4081131839});
p.push_back({(ll)95500000,(ll)4114966079});
p.push_back({(ll)96000000,(ll)4153263103});
p.push_back({(ll)96500000,(ll)4196393983});
p.push_back({(ll)97000000,(ll)4237406719});
p.push_back({(ll)97500000,(ll)4296171263});
p.push_back({(ll)98000000,(ll)4309730503});
p.push_back({(ll)98500000,(ll)4328880199});
p.push_back({(ll)99000000,(ll)4342780815});
p.push_back({(ll)99500000,(ll)4363019743});
p.push_back({(ll)100000000,(ll)4380394855});
p.push_back({(ll)100500000,(ll)4401418143});
p.push_back({(ll)101000000,(ll)4425291175});
p.push_back({(ll)101500000,(ll)4448075679});
p.push_back({(ll)102000000,(ll)4474012751});
p.push_back({(ll)102500000,(ll)4502914087});
p.push_back({(ll)103000000,(ll)4535825871});
p.push_back({(ll)103500000,(ll)4565910567});
p.push_back({(ll)104000000,(ll)4580588719});
p.push_back({(ll)104500000,(ll)4598386855});
p.push_back({(ll)105000000,(ll)4614042983});
p.push_back({(ll)105500000,(ll)4633060647});
p.push_back({(ll)106000000,(ll)4651819319});
p.push_back({(ll)106500000,(ll)4672504999});
p.push_back({(ll)107000000,(ll)4697763879});
p.push_back({(ll)107500000,(ll)4719499711});
p.push_back({(ll)108000000,(ll)4746253487});
p.push_back({(ll)108500000,(ll)4775073023});
p.push_back({(ll)109000000,(ll)4807990479});
p.push_back({(ll)109500000,(ll)4840298551});
p.push_back({(ll)110000000,(ll)4872027431});
p.push_back({(ll)110500000,(ll)4906571735});
p.push_back({(ll)111000000,(ll)4947543783});
p.push_back({(ll)111500000,(ll)5000444591});
p.push_back({(ll)112000000,(ll)5057146687});
p.push_back({(ll)112500000,(ll)5108816047});
p.push_back({(ll)113000000,(ll)5140583783});
p.push_back({(ll)113500000,(ll)5175178599});
p.push_back({(ll)114000000,(ll)5216671591});
p.push_back({(ll)114500000,(ll)5269107527});
p.push_back({(ll)115000000,(ll)5326560895});
p.push_back({(ll)115500000,(ll)5373179191});
p.push_back({(ll)116000000,(ll)5387726527});
p.push_back({(ll)116500000,(ll)5405676647});
p.push_back({(ll)117000000,(ll)5421278695});
p.push_back({(ll)117500000,(ll)5440550695});
p.push_back({(ll)118000000,(ll)5459722143});
p.push_back({(ll)118500000,(ll)5480574399});
p.push_back({(ll)119000000,(ll)5504816221});
p.push_back({(ll)119500000,(ll)5528963519});
p.push_back({(ll)120000000,(ll)5555339615});
p.push_back({(ll)120500000,(ll)5585321039});
p.push_back({(ll)121000000,(ll)5618560335});
p.push_back({(ll)121500000,(ll)5642529655});
p.push_back({(ll)122000000,(ll)5658462999});
p.push_back({(ll)122500000,(ll)5675431507});
p.push_back({(ll)123000000,(ll)5692072999});
p.push_back({(ll)123500000,(ll)5710395343});
p.push_back({(ll)124000000,(ll)5731341215});
p.push_back({(ll)124500000,(ll)5751778407});
p.push_back({(ll)125000000,(ll)5775854989});
p.push_back({(ll)125500000,(ll)5802685151});
p.push_back({(ll)126000000,(ll)5826908319});
p.push_back({(ll)126500000,(ll)5857744335});
p.push_back({(ll)127000000,(ll)5891323223});
p.push_back({(ll)127500000,(ll)5922692149});
p.push_back({(ll)128000000,(ll)5954479791});
p.push_back({(ll)128500000,(ll)5991388693});
p.push_back({(ll)129000000,(ll)6034755007});
p.push_back({(ll)129500000,(ll)6084724655});
p.push_back({(ll)130000000,(ll)6147849583});
p.push_back({(ll)130500000,(ll)6191216311});
p.push_back({(ll)131000000,(ll)6223427063});
p.push_back({(ll)131500000,(ll)6260119383});
p.push_back({(ll)132000000,(ll)6304068279});
p.push_back({(ll)132500000,(ll)6353837551});
p.push_back({(ll)133000000,(ll)6416709103});
p.push_back({(ll)133500000,(ll)6450948303});
p.push_back({(ll)134000000,(ll)6476249263});
p.push_back({(ll)134500000,(ll)6494145695});
p.push_back({(ll)135000000,(ll)6516168535});
p.push_back({(ll)135500000,(ll)6544983631});
p.push_back({(ll)136000000,(ll)6572783015});
p.push_back({(ll)136500000,(ll)6600451231});
p.push_back({(ll)137000000,(ll)6632674511});
p.push_back({(ll)137500000,(ll)6672721631});
p.push_back({(ll)138000000,(ll)6711830847});
p.push_back({(ll)138500000,(ll)6729325853});
p.push_back({(ll)139000000,(ll)6749723215});
p.push_back({(ll)139500000,(ll)6772757991});
p.push_back({(ll)140000000,(ll)6796613279});
p.push_back({(ll)140500000,(ll)6822313167});
p.push_back({(ll)141000000,(ll)6850822351});
p.push_back({(ll)141500000,(ll)6883347631});
p.push_back({(ll)142000000,(ll)6917049629});
p.push_back({(ll)142500000,(ll)6955309519});
p.push_back({(ll)143000000,(ll)6996517047});
p.push_back({(ll)143500000,(ll)7035970647});
p.push_back({(ll)144000000,(ll)7085106095});
p.push_back({(ll)144500000,(ll)7147523247});
p.push_back({(ll)145000000,(ll)7218689695});
p.push_back({(ll)145500000,(ll)7270192311});
p.push_back({(ll)146000000,(ll)7315146927});
p.push_back({(ll)146500000,(ll)7360366055});
p.push_back({(ll)147000000,(ll)7421137103});
p.push_back({(ll)147500000,(ll)7499512127});
p.push_back({(ll)148000000,(ll)7528903847});
p.push_back({(ll)148500000,(ll)7551279831});
p.push_back({(ll)149000000,(ll)7570981287});
p.push_back({(ll)149500000,(ll)7593627823});
p.push_back({(ll)150000000,(ll)7621435687});
p.push_back({(ll)150500000,(ll)7651167407});
p.push_back({(ll)151000000,(ll)7682352831});
p.push_back({(ll)151500000,(ll)7713830591});
p.push_back({(ll)152000000,(ll)7752447439});
p.push_back({(ll)152500000,(ll)7787169367});
p.push_back({(ll)153000000,(ll)7805967407});
p.push_back({(ll)153500000,(ll)7825362255});
p.push_back({(ll)154000000,(ll)7852021095});
p.push_back({(ll)154500000,(ll)7873794647});
p.push_back({(ll)155000000,(ll)7902098007});
p.push_back({(ll)155500000,(ll)7928394191});
p.push_back({(ll)156000000,(ll)7959786703});
p.push_back({(ll)156500000,(ll)7994958239});
p.push_back({(ll)157000000,(ll)8036845727});
p.push_back({(ll)157500000,(ll)8075403479});
p.push_back({(ll)158000000,(ll)8120382823});
p.push_back({(ll)158500000,(ll)8165271015});
p.push_back({(ll)159000000,(ll)8226312559});
p.push_back({(ll)159500000,(ll)8304504559});
p.push_back({(ll)160000000,(ll)8355116887});
p.push_back({(ll)160500000,(ll)8392913959});
p.push_back({(ll)161000000,(ll)8442467927});
p.push_back({(ll)161500000,(ll)8506069151});
p.push_back({(ll)162000000,(ll)8588431039});
p.push_back({(ll)162500000,(ll)8596660699});
p.push_back({(ll)163000000,(ll)8607801947});
p.push_back({(ll)163500000,(ll)8620578551});
p.push_back({(ll)164000000,(ll)8629292591});
p.push_back({(ll)164500000,(ll)8640234735});
p.push_back({(ll)165000000,(ll)8651627103});
p.push_back({(ll)165500000,(ll)8664212855});
p.push_back({(ll)166000000,(ll)8680212179});
p.push_back({(ll)166500000,(ll)8695971183});
p.push_back({(ll)167000000,(ll)8711099999});
p.push_back({(ll)167500000,(ll)8727885023});
p.push_back({(ll)168000000,(ll)8743205051});
p.push_back({(ll)168500000,(ll)8760718175});
p.push_back({(ll)169000000,(ll)8775807059});
p.push_back({(ll)169500000,(ll)8795563887});
p.push_back({(ll)170000000,(ll)8819775359});
p.push_back({(ll)170500000,(ll)8842471007});
p.push_back({(ll)171000000,(ll)8861488731});
p.push_back({(ll)171500000,(ll)8870200983});
p.push_back({(ll)172000000,(ll)8881514571});
p.push_back({(ll)172500000,(ll)8894239063});
p.push_back({(ll)173000000,(ll)8902247087});
p.push_back({(ll)173500000,(ll)8913413943});
p.push_back({(ll)174000000,(ll)8927631967});
p.push_back({(ll)174500000,(ll)8940754223});
p.push_back({(ll)175000000,(ll)8959296779});
p.push_back({(ll)175500000,(ll)8971424047});
p.push_back({(ll)176000000,(ll)8988944991});
p.push_back({(ll)176500000,(ll)9002222831});
p.push_back({(ll)177000000,(ll)9020668511});
p.push_back({(ll)177500000,(ll)9035013487});
p.push_back({(ll)178000000,(ll)9053292927});
p.push_back({(ll)178500000,(ll)9074853359});
p.push_back({(ll)179000000,(ll)9099084399});
p.push_back({(ll)179500000,(ll)9125832815});
p.push_back({(ll)180000000,(ll)9142144763});
p.push_back({(ll)180500000,(ll)9164725819});
p.push_back({(ll)181000000,(ll)9183942519});
p.push_back({(ll)181500000,(ll)9212116351});
p.push_back({(ll)182000000,(ll)9242917871});
p.push_back({(ll)182500000,(ll)9274636027});
p.push_back({(ll)183000000,(ll)9307697851});
p.push_back({(ll)183500000,(ll)9351504223});
p.push_back({(ll)184000000,(ll)9397735287});
p.push_back({(ll)184500000,(ll)9416328119});
p.push_back({(ll)185000000,(ll)9436216167});
p.push_back({(ll)185500000,(ll)9461458679});
p.push_back({(ll)186000000,(ll)9489765751});
p.push_back({(ll)186500000,(ll)9519334071});
p.push_back({(ll)187000000,(ll)9552098015});
p.push_back({(ll)187500000,(ll)9585111519});
p.push_back({(ll)188000000,(ll)9634335855});
p.push_back({(ll)188500000,(ll)9666757643});
p.push_back({(ll)189000000,(ll)9675461815});
p.push_back({(ll)189500000,(ll)9686791607});
p.push_back({(ll)190000000,(ll)9699525083});
p.push_back({(ll)190500000,(ll)9707459759});
p.push_back({(ll)191000000,(ll)9718682039});
p.push_back({(ll)191500000,(ll)9732915063});
p.push_back({(ll)192000000,(ll)9745990831});
p.push_back({(ll)192500000,(ll)9764545335});
p.push_back({(ll)193000000,(ll)9776563695});
p.push_back({(ll)193500000,(ll)9794087647});
p.push_back({(ll)194000000,(ll)9807360367});
p.push_back({(ll)194500000,(ll)9825841855});
p.push_back({(ll)195000000,(ll)9840232635});
p.push_back({(ll)195500000,(ll)9858303455});
p.push_back({(ll)196000000,(ll)9880027999});
p.push_back({(ll)196500000,(ll)9904235375});
p.push_back({(ll)197000000,(ll)9930896735});
p.push_back({(ll)197500000,(ll)9938769207});
p.push_back({(ll)198000000,(ll)9949810111});
p.push_back({(ll)198500000,(ll)9962494203});
p.push_back({(ll)199000000,(ll)9971340567});
p.push_back({(ll)199500000,(ll)9982071487});
p.push_back({(ll)200000000,(ll)9993530939});
p.push_back({(ll)200500000,(ll)10006295391});
p.push_back({(ll)201000000,(ll)10022304175});
p.push_back({(ll)201500000,(ll)10038052311});
p.push_back({(ll)202000000,(ll)10053041271});
p.push_back({(ll)202500000,(ll)10069836015});
p.push_back({(ll)203000000,(ll)10085283739});
p.push_back({(ll)203500000,(ll)10102816991});
p.push_back({(ll)204000000,(ll)10117752143});
p.push_back({(ll)204500000,(ll)10137675951});
p.push_back({(ll)205000000,(ll)10161543903});
p.push_back({(ll)205500000,(ll)10184453567});
p.push_back({(ll)206000000,(ll)10206271727});
p.push_back({(ll)206500000,(ll)10228092727});
p.push_back({(ll)207000000,(ll)10246819311});
p.push_back({(ll)207500000,(ll)10271912887});
p.push_back({(ll)208000000,(ll)10303646583});
p.push_back({(ll)208500000,(ll)10335467375});
p.push_back({(ll)209000000,(ll)10368805567});
p.push_back({(ll)209500000,(ll)10402726575});
p.push_back({(ll)210000000,(ll)10450380143});
p.push_back({(ll)210500000,(ll)10478637367});
p.push_back({(ll)211000000,(ll)10503563119});
p.push_back({(ll)211500000,(ll)10520692407});
p.push_back({(ll)212000000,(ll)10545595831});
p.push_back({(ll)212500000,(ll)10576990551});
p.push_back({(ll)213000000,(ll)10609496283});
p.push_back({(ll)213500000,(ll)10642450671});
p.push_back({(ll)214000000,(ll)10679454703});
p.push_back({(ll)214500000,(ll)10735163135});
p.push_back({(ll)215000000,(ll)10744643131});
p.push_back({(ll)215500000,(ll)10759189243});
p.push_back({(ll)216000000,(ll)10774052543});
p.push_back({(ll)216500000,(ll)10786187483});
p.push_back({(ll)217000000,(ll)10801398711});
p.push_back({(ll)217500000,(ll)10817425879});
p.push_back({(ll)218000000,(ll)10839528791});
p.push_back({(ll)218500000,(ll)10856708831});
p.push_back({(ll)219000000,(ll)10876116143});
p.push_back({(ll)219500000,(ll)10894874991});
p.push_back({(ll)220000000,(ll)10912932207});
p.push_back({(ll)220500000,(ll)10938242527});
p.push_back({(ll)221000000,(ll)10962735583});
p.push_back({(ll)221500000,(ll)10992292207});
p.push_back({(ll)222000000,(ll)11010688863});
p.push_back({(ll)222500000,(ll)11024325983});
p.push_back({(ll)223000000,(ll)11040105115});
p.push_back({(ll)223500000,(ll)11048489455});
p.push_back({(ll)224000000,(ll)11062939851});
p.push_back({(ll)224500000,(ll)11079561783});
p.push_back({(ll)225000000,(ll)11100281567});
p.push_back({(ll)225500000,(ll)11117863343});
p.push_back({(ll)226000000,(ll)11140829851});
p.push_back({(ll)226500000,(ll)11157822143});
p.push_back({(ll)227000000,(ll)11178062491});
p.push_back({(ll)227500000,(ll)11196804527});
p.push_back({(ll)228000000,(ll)11224007007});
p.push_back({(ll)228500000,(ll)11250739951});
p.push_back({(ll)229000000,(ll)11278892911});
p.push_back({(ll)229500000,(ll)11308155019});
p.push_back({(ll)230000000,(ll)11329204763});
p.push_back({(ll)230500000,(ll)11363727223});
p.push_back({(ll)231000000,(ll)11403609847});
p.push_back({(ll)231500000,(ll)11444435311});
p.push_back({(ll)232000000,(ll)11487524335});
p.push_back({(ll)232500000,(ll)11545166647});
p.push_back({(ll)233000000,(ll)11568597951});
p.push_back({(ll)233500000,(ll)11593868955});
p.push_back({(ll)234000000,(ll)11626710199});
p.push_back({(ll)234500000,(ll)11664210815});
p.push_back({(ll)235000000,(ll)11706434495});
p.push_back({(ll)235500000,(ll)11748308143});
p.push_back({(ll)236000000,(ll)11811366635});
p.push_back({(ll)236500000,(ll)11818982511});
p.push_back({(ll)237000000,(ll)11833844447});
p.push_back({(ll)237500000,(ll)11848403295});
p.push_back({(ll)238000000,(ll)11861541815});
p.push_back({(ll)238500000,(ll)11877224919});
p.push_back({(ll)239000000,(ll)11893232087});
p.push_back({(ll)239500000,(ll)11914194607});
p.push_back({(ll)240000000,(ll)11931408223});
p.push_back({(ll)240500000,(ll)11950428827});
p.push_back({(ll)241000000,(ll)11969517279});
p.push_back({(ll)241500000,(ll)11988200159});
p.push_back({(ll)242000000,(ll)12013288623});
p.push_back({(ll)242500000,(ll)12040114607});
p.push_back({(ll)243000000,(ll)12067877787});
p.push_back({(ll)243500000,(ll)12085069783});
p.push_back({(ll)244000000,(ll)12098830647});
p.push_back({(ll)244500000,(ll)12114478167});
p.push_back({(ll)245000000,(ll)12123894519});
p.push_back({(ll)245500000,(ll)12137569455});
p.push_back({(ll)246000000,(ll)12154097751});
p.push_back({(ll)246500000,(ll)12176894687});
p.push_back({(ll)247000000,(ll)12193700271});
p.push_back({(ll)247500000,(ll)12215694831});
p.push_back({(ll)248000000,(ll)12233040095});
p.push_back({(ll)248500000,(ll)12252387759});
p.push_back({(ll)249000000,(ll)12271432443});
p.push_back({(ll)249500000,(ll)12299553503});
p.push_back({(ll)250000000,(ll)12327536575});
p.push_back({(ll)250500000,(ll)12353777391});
p.push_back({(ll)251000000,(ll)12382933463});
p.push_back({(ll)251500000,(ll)12404920923});
p.push_back({(ll)252000000,(ll)12440366527});
p.push_back({(ll)252500000,(ll)12482549467});
p.push_back({(ll)253000000,(ll)12520071259});
p.push_back({(ll)253500000,(ll)12567306975});
p.push_back({(ll)254000000,(ll)12619992175});
p.push_back({(ll)254500000,(ll)12647337407});
p.push_back({(ll)255000000,(ll)12669348543});
p.push_back({(ll)255500000,(ll)12702857079});
p.push_back({(ll)256000000,(ll)12740481719});
p.push_back({(ll)256500000,(ll)12784611759});
p.push_back({(ll)257000000,(ll)12824422767});
p.push_back({(ll)257500000,(ll)12885761199});
p.push_back({(ll)258000000,(ll)12900706263});
p.push_back({(ll)258500000,(ll)12919772119});
p.push_back({(ll)259000000,(ll)12935431511});
p.push_back({(ll)259500000,(ll)12954906031});
p.push_back({(ll)260000000,(ll)12975152407});
p.push_back({(ll)260500000,(ll)12996853167});
p.push_back({(ll)261000000,(ll)13021337439});
p.push_back({(ll)261500000,(ll)13048756399});
p.push_back({(ll)262000000,(ll)13073922479});
p.push_back({(ll)262500000,(ll)13105604447});
p.push_back({(ll)263000000,(ll)13140309727});
p.push_back({(ll)263500000,(ll)13161563823});
p.push_back({(ll)264000000,(ll)13179646327});
p.push_back({(ll)264500000,(ll)13195686583});
p.push_back({(ll)265000000,(ll)13214637175});
p.push_back({(ll)265500000,(ll)13234423735});
p.push_back({(ll)266000000,(ll)13258270895});
p.push_back({(ll)266500000,(ll)13279216055});
p.push_back({(ll)267000000,(ll)13304598647});
p.push_back({(ll)267500000,(ll)13330298543});
p.push_back({(ll)268000000,(ll)13360211311});
p.push_back({(ll)268500000,(ll)13394327919});
p.push_back({(ll)269000000,(ll)13427303895});
p.push_back({(ll)269500000,(ll)13460338231});
p.push_back({(ll)270000000,(ll)13494250367});
p.push_back({(ll)270500000,(ll)13535146743});
p.push_back({(ll)271000000,(ll)13587762623});
p.push_back({(ll)271500000,(ll)13642930111});
p.push_back({(ll)272000000,(ll)13697161079});
p.push_back({(ll)272500000,(ll)13730033391});
p.push_back({(ll)273000000,(ll)13764662999});
p.push_back({(ll)273500000,(ll)13806405487});
p.push_back({(ll)274000000,(ll)13859001199});
p.push_back({(ll)274500000,(ll)13916149631});
p.push_back({(ll)275000000,(ll)13963310039});
p.push_back({(ll)275500000,(ll)13979947013});
p.push_back({(ll)276000000,(ll)13997338303});
p.push_back({(ll)276500000,(ll)14014158711});
p.push_back({(ll)277000000,(ll)14034019823});
p.push_back({(ll)277500000,(ll)14059375023});
p.push_back({(ll)278000000,(ll)14077726047});
p.push_back({(ll)278500000,(ll)14101522095});
p.push_back({(ll)279000000,(ll)14130652875});
p.push_back({(ll)279500000,(ll)14159412607});
p.push_back({(ll)280000000,(ll)14193654623});
p.push_back({(ll)280500000,(ll)14227285335});
p.push_back({(ll)281000000,(ll)14240941239});
p.push_back({(ll)281500000,(ll)14261137751});
p.push_back({(ll)282000000,(ll)14275454647});
p.push_back({(ll)282500000,(ll)14295568631});
p.push_back({(ll)283000000,(ll)14315643191});
p.push_back({(ll)283500000,(ll)14336982751});
p.push_back({(ll)284000000,(ll)14361994415});
p.push_back({(ll)284500000,(ll)14386857663});
p.push_back({(ll)285000000,(ll)14413354719});
p.push_back({(ll)285500000,(ll)14445299039});
p.push_back({(ll)286000000,(ll)14479238447});
p.push_back({(ll)286500000,(ll)14511036351});
p.push_back({(ll)287000000,(ll)14543101495});
p.push_back({(ll)287500000,(ll)14580782007});
p.push_back({(ll)288000000,(ll)14623901559});
p.push_back({(ll)288500000,(ll)14674185919});
p.push_back({(ll)289000000,(ll)14737323695});
p.push_back({(ll)289500000,(ll)14781785463});
p.push_back({(ll)290000000,(ll)14814472895});
p.push_back({(ll)290500000,(ll)14852363447});
p.push_back({(ll)291000000,(ll)14898196567});
p.push_back({(ll)291500000,(ll)14946671983});
p.push_back({(ll)292000000,(ll)15010985855});
p.push_back({(ll)292500000,(ll)15043372983});
p.push_back({(ll)293000000,(ll)15067613359});
p.push_back({(ll)293500000,(ll)15087254959});
p.push_back({(ll)294000000,(ll)15112391855});
p.push_back({(ll)294500000,(ll)15139129695});
p.push_back({(ll)295000000,(ll)15169564079});
p.push_back({(ll)295500000,(ll)15202387631});
p.push_back({(ll)296000000,(ll)15235983279});
p.push_back({(ll)296500000,(ll)15274429791});
p.push_back({(ll)297000000,(ll)15306397271});
p.push_back({(ll)297500000,(ll)15330612663});
p.push_back({(ll)298000000,(ll)15351175519});
p.push_back({(ll)298500000,(ll)15373301623});
p.push_back({(ll)299000000,(ll)15403027823});
p.push_back({(ll)299500000,(ll)15430280695});
p.push_back({(ll)300000000,(ll)15460508079});
p.push_back({(ll)300500000,(ll)15492413279});
p.push_back({(ll)301000000,(ll)15536232623});
p.push_back({(ll)301500000,(ll)15573782871});
p.push_back({(ll)302000000,(ll)15611412919});
p.push_back({(ll)302500000,(ll)15658517367});
p.push_back({(ll)303000000,(ll)15711020783});
p.push_back({(ll)303500000,(ll)15779192239});
p.push_back({(ll)304000000,(ll)15845736175});
p.push_back({(ll)304500000,(ll)15888205175});
p.push_back({(ll)305000000,(ll)15938704599});
p.push_back({(ll)305500000,(ll)15990853311});
p.push_back({(ll)306000000,(ll)16061328767});
p.push_back({(ll)306500000,(ll)16112053631});
p.push_back({(ll)307000000,(ll)16137007607});
p.push_back({(ll)307500000,(ll)16156757167});
p.push_back({(ll)308000000,(ll)16179019119});
p.push_back({(ll)308500000,(ll)16208940207});
p.push_back({(ll)309000000,(ll)16237027039});
p.push_back({(ll)309500000,(ll)16267487999});
p.push_back({(ll)310000000,(ll)16299279807});
p.push_back({(ll)310500000,(ll)16342001071});
p.push_back({(ll)311000000,(ll)16377175743});
p.push_back({(ll)311500000,(ll)16396795375});
p.push_back({(ll)312000000,(ll)16417065391});
p.push_back({(ll)312500000,(ll)16443030895});
p.push_back({(ll)313000000,(ll)16469255607});
p.push_back({(ll)313500000,(ll)16496291167});
p.push_back({(ll)314000000,(ll)16526725855});
p.push_back({(ll)314500000,(ll)16559646559});
p.push_back({(ll)315000000,(ll)16597228383});
p.push_back({(ll)315500000,(ll)16641816287});
p.push_back({(ll)316000000,(ll)16679151287});
p.push_back({(ll)316500000,(ll)16718717367});
p.push_back({(ll)317000000,(ll)16774465015});
p.push_back({(ll)317500000,(ll)16836553663});
p.push_back({(ll)318000000,(ll)16913806679});
p.push_back({(ll)318500000,(ll)16950709951});
p.push_back({(ll)319000000,(ll)16996670143});
p.push_back({(ll)319500000,(ll)17050125151});
p.push_back({(ll)320000000,(ll)17117079919});
p.push_back({(ll)320500000,(ll)17183384791});
p.push_back({(ll)321000000,(ll)17201135799});
p.push_back({(ll)321500000,(ll)17219881007});
p.push_back({(ll)322000000,(ll)17239426495});
p.push_back({(ll)322500000,(ll)17264801663});
p.push_back({(ll)323000000,(ll)17291231551});
p.push_back({(ll)323500000,(ll)17320580955});
p.push_back({(ll)324000000,(ll)17353729151});
p.push_back({(ll)324500000,(ll)17390043519});
p.push_back({(ll)325000000,(ll)17437326463});
p.push_back({(ll)325500000,(ll)17460899455});
p.push_back({(ll)326000000,(ll)17481255423});
p.push_back({(ll)326500000,(ll)17499412607});
p.push_back({(ll)327000000,(ll)17520334719});
p.push_back({(ll)327500000,(ll)17548723327});
p.push_back({(ll)328000000,(ll)17574418207});
p.push_back({(ll)328500000,(ll)17606033535});
p.push_back({(ll)329000000,(ll)17639687039});
p.push_back({(ll)329500000,(ll)17684552831});
p.push_back({(ll)330000000,(ll)17727659007});
p.push_back({(ll)330500000,(ll)17767534207});
p.push_back({(ll)331000000,(ll)17817694071});
p.push_back({(ll)331500000,(ll)17880362747});
p.push_back({(ll)332000000,(ll)17966786047});
p.push_back({(ll)332500000,(ll)18015592831});
p.push_back({(ll)333000000,(ll)18055828863});
p.push_back({(ll)333500000,(ll)18112875519});
p.push_back({(ll)334000000,(ll)18183321343});
p.push_back({(ll)334500000,(ll)18257728895});
p.push_back({(ll)335000000,(ll)18275091807});
p.push_back({(ll)335500000,(ll)18293806655});
p.push_back({(ll)336000000,(ll)18313970047});
p.push_back({(ll)336500000,(ll)18339115391});
p.push_back({(ll)337000000,(ll)18365674239});
p.push_back({(ll)337500000,(ll)18394780415});
p.push_back({(ll)338000000,(ll)18427977839});
p.push_back({(ll)338500000,(ll)18465022719});
p.push_back({(ll)339000000,(ll)18511959519});
p.push_back({(ll)339500000,(ll)18534909021});
p.push_back({(ll)340000000,(ll)18555679991});
p.push_back({(ll)340500000,(ll)18573531103});
p.push_back({(ll)341000000,(ll)18594512351});
p.push_back({(ll)341500000,(ll)18622935391});
p.push_back({(ll)342000000,(ll)18649014495});
p.push_back({(ll)342500000,(ll)18680398719});
p.push_back({(ll)343000000,(ll)18714050943});
p.push_back({(ll)343500000,(ll)18759143807});
p.push_back({(ll)344000000,(ll)18803081079});
p.push_back({(ll)344500000,(ll)18842124511});
p.push_back({(ll)345000000,(ll)18892461535});
p.push_back({(ll)345500000,(ll)18956362239});
p.push_back({(ll)346000000,(ll)19043190367});
p.push_back({(ll)346500000,(ll)19090627327});
p.push_back({(ll)347000000,(ll)19130564887});
p.push_back({(ll)347500000,(ll)19188361087});
p.push_back({(ll)348000000,(ll)19259368959});
p.push_back({(ll)348500000,(ll)19331921223});
p.push_back({(ll)349000000,(ll)19355342591});
p.push_back({(ll)349500000,(ll)19380056791});
p.push_back({(ll)350000000,(ll)19408459207});
p.push_back({(ll)350500000,(ll)19443013343});
p.push_back({(ll)351000000,(ll)19480343935});
p.push_back({(ll)351500000,(ll)19518882015});
p.push_back({(ll)352000000,(ll)19571790591});
p.push_back({(ll)352500000,(ll)19606742255});
p.push_back({(ll)353000000,(ll)19631948895});
p.push_back({(ll)353500000,(ll)19654202751});
p.push_back({(ll)354000000,(ll)19686110039});
p.push_back({(ll)354500000,(ll)19720429951});
p.push_back({(ll)355000000,(ll)19762034431});
p.push_back({(ll)355500000,(ll)19802651007});
p.push_back({(ll)356000000,(ll)19859804927});
p.push_back({(ll)356500000,(ll)19906333887});
p.push_back({(ll)357000000,(ll)19969118303});
p.push_back({(ll)357500000,(ll)20050232063});
p.push_back({(ll)358000000,(ll)20143816443});
p.push_back({(ll)358500000,(ll)20190642399});
p.push_back({(ll)359000000,(ll)20260051967});
p.push_back({(ll)359500000,(ll)20353209727});
p.push_back({(ll)360000000,(ll)20411450879});
p.push_back({(ll)360500000,(ll)20437062111});
p.push_back({(ll)361000000,(ll)20458927839});
p.push_back({(ll)361500000,(ll)20490791295});
p.push_back({(ll)362000000,(ll)20525201791});
p.push_back({(ll)362500000,(ll)20565706239});
p.push_back({(ll)363000000,(ll)20607169919});
p.push_back({(ll)363500000,(ll)20662813439});
p.push_back({(ll)364000000,(ll)20688650335});
p.push_back({(ll)364500000,(ll)20710200863});
p.push_back({(ll)365000000,(ll)20738599295});
p.push_back({(ll)365500000,(ll)20771909119});
p.push_back({(ll)366000000,(ll)20806829407});
p.push_back({(ll)366500000,(ll)20844331391});
p.push_back({(ll)367000000,(ll)20892406879});
p.push_back({(ll)367500000,(ll)20945646303});
p.push_back({(ll)368000000,(ll)20994659895});
p.push_back({(ll)368500000,(ll)21061973727});
p.push_back({(ll)369000000,(ll)21152320511});
p.push_back({(ll)369500000,(ll)21230302943});
p.push_back({(ll)370000000,(ll)21282666495});
p.push_back({(ll)370500000,(ll)21359798783});
p.push_back({(ll)371000000,(ll)21462074239});
p.push_back({(ll)371500000,(ll)21497975895});
p.push_back({(ll)372000000,(ll)21529663039});
p.push_back({(ll)372500000,(ll)21563991391});
p.push_back({(ll)373000000,(ll)21604177887});
p.push_back({(ll)373500000,(ll)21652578687});
p.push_back({(ll)374000000,(ll)21713000287});
p.push_back({(ll)374500000,(ll)21757071599});
p.push_back({(ll)375000000,(ll)21786331247});
p.push_back({(ll)375500000,(ll)21819577631});
p.push_back({(ll)376000000,(ll)21858110847});
p.push_back({(ll)376500000,(ll)21903514239});
p.push_back({(ll)377000000,(ll)21958867711});
p.push_back({(ll)377500000,(ll)22022655231});
p.push_back({(ll)378000000,(ll)22084147319});
p.push_back({(ll)378500000,(ll)22168126207});
p.push_back({(ll)379000000,(ll)22284697695});
p.push_back({(ll)379500000,(ll)22346409855});
p.push_back({(ll)380000000,(ll)22424463103});
p.push_back({(ll)380500000,(ll)22548273151});
p.push_back({(ll)381000000,(ll)22574601919});
p.push_back({(ll)381500000,(ll)22605321567});
p.push_back({(ll)382000000,(ll)22641135903});
p.push_back({(ll)382500000,(ll)22682874965});
p.push_back({(ll)383000000,(ll)22732484351});
p.push_back({(ll)383500000,(ll)22791273983});
p.push_back({(ll)384000000,(ll)22834112095});
p.push_back({(ll)384500000,(ll)22863583679});
p.push_back({(ll)385000000,(ll)22897066223});
p.push_back({(ll)385500000,(ll)22935545567});
p.push_back({(ll)386000000,(ll)22983247615});
p.push_back({(ll)386500000,(ll)23038125439});
p.push_back({(ll)387000000,(ll)23102687167});
p.push_back({(ll)387500000,(ll)23165477247});
p.push_back({(ll)388000000,(ll)23253288543});
p.push_back({(ll)388500000,(ll)23362852607});
p.push_back({(ll)389000000,(ll)23425337151});
p.push_back({(ll)389500000,(ll)23508461311});
p.push_back({(ll)390000000,(ll)23623542495});
p.push_back({(ll)390500000,(ll)23660123743});
p.push_back({(ll)391000000,(ll)23699969759});
p.push_back({(ll)391500000,(ll)23748940223});
p.push_back({(ll)392000000,(ll)23810585983});
p.push_back({(ll)392500000,(ll)23886436351});
p.push_back({(ll)393000000,(ll)23925016959});
p.push_back({(ll)393500000,(ll)23963162079});
p.push_back({(ll)394000000,(ll)24012477023});
p.push_back({(ll)394500000,(ll)24071471583});
p.push_back({(ll)395000000,(ll)24144835967});
p.push_back({(ll)395500000,(ll)24220272063});
p.push_back({(ll)396000000,(ll)24325822463});
p.push_back({(ll)396500000,(ll)24449464191});
p.push_back({(ll)397000000,(ll)24533309119});
p.push_back({(ll)397500000,(ll)24663840127});
p.push_back({(ll)398000000,(ll)24722030847});
p.push_back({(ll)398500000,(ll)24763727999});
p.push_back({(ll)399000000,(ll)24809800639});
p.push_back({(ll)399500000,(ll)24867380991});
p.push_back({(ll)400000000,(ll)24936686943});
p.push_back({(ll)400500000,(ll)24986306239});
p.push_back({(ll)401000000,(ll)25025193471});
p.push_back({(ll)401500000,(ll)25071136255});
p.push_back({(ll)402000000,(ll)25128967167});
p.push_back({(ll)402500000,(ll)25198970623});
p.push_back({(ll)403000000,(ll)25272800863});
p.push_back({(ll)403500000,(ll)25363391999});
p.push_back({(ll)404000000,(ll)25503781983});
p.push_back({(ll)404500000,(ll)25583406591});
p.push_back({(ll)405000000,(ll)25692226943});
p.push_back({(ll)405500000,(ll)25777154383});
p.push_back({(ll)406000000,(ll)25798117631});
p.push_back({(ll)406500000,(ll)25817826047});
p.push_back({(ll)407000000,(ll)25839332223});
p.push_back({(ll)407500000,(ll)25867690463});
p.push_back({(ll)408000000,(ll)25894291231});
p.push_back({(ll)408500000,(ll)25927131903});
p.push_back({(ll)409000000,(ll)25960935511});
p.push_back({(ll)409500000,(ll)26007068927});
p.push_back({(ll)410000000,(ll)26043036499});
p.push_back({(ll)410500000,(ll)26062094559});
p.push_back({(ll)411000000,(ll)26081608159});
p.push_back({(ll)411500000,(ll)26103644919});
p.push_back({(ll)412000000,(ll)26129453503});
p.push_back({(ll)412500000,(ll)26158416063});
p.push_back({(ll)413000000,(ll)26190442751});
p.push_back({(ll)413500000,(ll)26224334207});
p.push_back({(ll)414000000,(ll)26265852287});
p.push_back({(ll)414500000,(ll)26312123775});
p.push_back({(ll)415000000,(ll)26351210743});
p.push_back({(ll)415500000,(ll)26398757631});
p.push_back({(ll)416000000,(ll)26462064127});
p.push_back({(ll)416500000,(ll)26544701695});
p.push_back({(ll)417000000,(ll)26600483967});
p.push_back({(ll)417500000,(ll)26641684223});
p.push_back({(ll)418000000,(ll)26698138847});
p.push_back({(ll)418500000,(ll)26766337119});
p.push_back({(ll)419000000,(ll)26846499711});
p.push_back({(ll)419500000,(ll)26865186143});
p.push_back({(ll)420000000,(ll)26884229823});
p.push_back({(ll)420500000,(ll)26904988607});
p.push_back({(ll)421000000,(ll)26931728791});
p.push_back({(ll)421500000,(ll)26960542079});
p.push_back({(ll)422000000,(ll)26990681295});
p.push_back({(ll)422500000,(ll)27024694143});
p.push_back({(ll)423000000,(ll)27065309055});
p.push_back({(ll)423500000,(ll)27112444055});
p.push_back({(ll)424000000,(ll)27130951935});
p.push_back({(ll)424500000,(ll)27150176287});
p.push_back({(ll)425000000,(ll)27169183451});
p.push_back({(ll)425500000,(ll)27195938367});
p.push_back({(ll)426000000,(ll)27222868351});
p.push_back({(ll)426500000,(ll)27252734335});
p.push_back({(ll)427000000,(ll)27286470895});
p.push_back({(ll)427500000,(ll)27324918655});
p.push_back({(ll)428000000,(ll)27372393215});
p.push_back({(ll)428500000,(ll)27414332087});
p.push_back({(ll)429000000,(ll)27454675839});
p.push_back({(ll)429500000,(ll)27515159263});
p.push_back({(ll)430000000,(ll)27586270815});
p.push_back({(ll)430500000,(ll)27663930615});
p.push_back({(ll)431000000,(ll)27702420191});
p.push_back({(ll)431500000,(ll)27754137023});
p.push_back({(ll)432000000,(ll)27819697919});
p.push_back({(ll)432500000,(ll)27907381119});
p.push_back({(ll)433000000,(ll)27937039455});
p.push_back({(ll)433500000,(ll)27959394735});
p.push_back({(ll)434000000,(ll)27987906927});
p.push_back({(ll)434500000,(ll)28022474847});
p.push_back({(ll)435000000,(ll)28058170079});
p.push_back({(ll)435500000,(ll)28101075711});
p.push_back({(ll)436000000,(ll)28152818047});
p.push_back({(ll)436500000,(ll)28192281271});
p.push_back({(ll)437000000,(ll)28219745015});
p.push_back({(ll)437500000,(ll)28241402239});
p.push_back({(ll)438000000,(ll)28273854047});
p.push_back({(ll)438500000,(ll)28308297151});
p.push_back({(ll)439000000,(ll)28348737023});
p.push_back({(ll)439500000,(ll)28391349727});
p.push_back({(ll)440000000,(ll)28448445183});
p.push_back({(ll)440500000,(ll)28495429855});
p.push_back({(ll)441000000,(ll)28558240511});
p.push_back({(ll)441500000,(ll)28639414015});
p.push_back({(ll)442000000,(ll)28733081271});
p.push_back({(ll)442500000,(ll)28780109375});
p.push_back({(ll)443000000,(ll)28848491263});
p.push_back({(ll)443500000,(ll)28942084863});
p.push_back({(ll)444000000,(ll)29002012911});
p.push_back({(ll)444500000,(ll)29027841759});
p.push_back({(ll)445000000,(ll)29050811871});
p.push_back({(ll)445500000,(ll)29084647903});
p.push_back({(ll)446000000,(ll)29121139935});
p.push_back({(ll)446500000,(ll)29161717983});
p.push_back({(ll)447000000,(ll)29207301343});
p.push_back({(ll)447500000,(ll)29261072255});
p.push_back({(ll)448000000,(ll)29282878687});
p.push_back({(ll)448500000,(ll)29309362943});
p.push_back({(ll)449000000,(ll)29334651775});
p.push_back({(ll)449500000,(ll)29370618287});
p.push_back({(ll)450000000,(ll)29410670555});
p.push_back({(ll)450500000,(ll)29449530239});
p.push_back({(ll)451000000,(ll)29502527871});
p.push_back({(ll)451500000,(ll)29555241207});
p.push_back({(ll)452000000,(ll)29611093503});
p.push_back({(ll)452500000,(ll)29684294399});
p.push_back({(ll)453000000,(ll)29788005887});
p.push_back({(ll)453500000,(ll)29838742199});
p.push_back({(ll)454000000,(ll)29901385215});
p.push_back({(ll)454500000,(ll)29982934783});
p.push_back({(ll)455000000,(ll)30070975231});
p.push_back({(ll)455500000,(ll)30103079359});
p.push_back({(ll)456000000,(ll)30136417503});
p.push_back({(ll)456500000,(ll)30175307263});
p.push_back({(ll)457000000,(ll)30221640063});
p.push_back({(ll)457500000,(ll)30278014719});
p.push_back({(ll)458000000,(ll)30337652575});
p.push_back({(ll)458500000,(ll)30369179359});
p.push_back({(ll)459000000,(ll)30401645951});
p.push_back({(ll)459500000,(ll)30440187615});
p.push_back({(ll)460000000,(ll)30485868927});
p.push_back({(ll)460500000,(ll)30540014943});
p.push_back({(ll)461000000,(ll)30606244991});
p.push_back({(ll)461500000,(ll)30669016639});
p.push_back({(ll)462000000,(ll)30750435071});
p.push_back({(ll)462500000,(ll)30870723455});
p.push_back({(ll)463000000,(ll)30930380543});
p.push_back({(ll)463500000,(ll)31009396607});
p.push_back({(ll)464000000,(ll)31128356095});
p.push_back({(ll)464500000,(ll)31165847391});
p.push_back({(ll)465000000,(ll)31197040511});
p.push_back({(ll)465500000,(ll)31236889983});
p.push_back({(ll)466000000,(ll)31277636351});
p.push_back({(ll)466500000,(ll)31329556351});
p.push_back({(ll)467000000,(ll)31395141503});
p.push_back({(ll)467500000,(ll)31430624351});
p.push_back({(ll)468000000,(ll)31462399359});
p.push_back({(ll)468500000,(ll)31500288735});
p.push_back({(ll)469000000,(ll)31542285535});
p.push_back({(ll)469500000,(ll)31593768319});
p.push_back({(ll)470000000,(ll)31658087807});
p.push_back({(ll)470500000,(ll)31719586943});
p.push_back({(ll)471000000,(ll)31793130239});
p.push_back({(ll)471500000,(ll)31898030335});
p.push_back({(ll)472000000,(ll)31982841719});
p.push_back({(ll)472500000,(ll)32053202495});
p.push_back({(ll)473000000,(ll)32154789375});
p.push_back({(ll)473500000,(ll)32232981887});
p.push_back({(ll)474000000,(ll)32270675711});
p.push_back({(ll)474500000,(ll)32319325791});
p.push_back({(ll)475000000,(ll)32380384639});
p.push_back({(ll)475500000,(ll)32450483583});
p.push_back({(ll)476000000,(ll)32502449087});
p.push_back({(ll)476500000,(ll)32542074623});
p.push_back({(ll)477000000,(ll)32590210047});
p.push_back({(ll)477500000,(ll)32650450303});
p.push_back({(ll)478000000,(ll)32721365375});
p.push_back({(ll)478500000,(ll)32800351103});
p.push_back({(ll)479000000,(ll)32893134335});
p.push_back({(ll)479500000,(ll)33027501567});
p.push_back({(ll)480000000,(ll)33107842911});
p.push_back({(ll)480500000,(ll)33225770879});
p.push_back({(ll)481000000,(ll)33308031359});
p.push_back({(ll)481500000,(ll)33348911327});
p.push_back({(ll)482000000,(ll)33396214527});
p.push_back({(ll)482500000,(ll)33456379775});
p.push_back({(ll)483000000,(ll)33527238111});
p.push_back({(ll)483500000,(ll)33577889151});
p.push_back({(ll)484000000,(ll)33620481791});
p.push_back({(ll)484500000,(ll)33668550079});
p.push_back({(ll)485000000,(ll)33727186815});
p.push_back({(ll)485500000,(ll)33800185599});
p.push_back({(ll)486000000,(ll)33877627071});
p.push_back({(ll)486500000,(ll)33976255871});
p.push_back({(ll)487000000,(ll)34108444767});
p.push_back({(ll)487500000,(ll)34190919423});
p.push_back({(ll)488000000,(ll)34311654911});
p.push_back({(ll)488500000,(ll)34365855167});
p.push_back({(ll)489000000,(ll)34381899615});
p.push_back({(ll)489500000,(ll)34398348959});
p.push_back({(ll)490000000,(ll)34414927359});
p.push_back({(ll)490500000,(ll)34443627855});
p.push_back({(ll)491000000,(ll)34479441375});
p.push_back({(ll)491500000,(ll)34501795455});
p.push_back({(ll)492000000,(ll)34528270047});
p.push_back({(ll)492500000,(ll)34546951679});
p.push_back({(ll)493000000,(ll)34582375743});
p.push_back({(ll)493500000,(ll)34629201599});
p.push_back({(ll)494000000,(ll)34641678015});
p.push_back({(ll)494500000,(ll)34661836383});
p.push_back({(ll)495000000,(ll)34673126655});
p.push_back({(ll)495500000,(ll)34695333151});
p.push_back({(ll)496000000,(ll)34729663295});
p.push_back({(ll)496500000,(ll)34763708511});
p.push_back({(ll)497000000,(ll)34781979263});
p.push_back({(ll)497500000,(ll)34802306591});
p.push_back({(ll)498000000,(ll)34828515839});
p.push_back({(ll)498500000,(ll)34870259071});
p.push_back({(ll)499000000,(ll)34914552191});
p.push_back({(ll)499500000,(ll)34952657407});
p.push_back({(ll)500000000,(ll)35033100015});
p.push_back({(ll)500500000,(ll)35082679039});
}
void preprocess()
{
///freopen("text.txt", "w", stdout);
for (ll i = 1; i < maxnum; i ++)
for (ll j = 1; j < maxnum; j ++)
gcd[i][j] = __gcd(i, j);
ll mask = 0, x, idx = 0;
while(idx < maxn)
{
vector < ll > num;
for (ll bit = 0; ((ll)1 << bit) <= mask; bit ++)
if ((mask & ((ll)1 << bit)))
num.push_back(bit + 1);
bool tf = true;
ll atl = 0;
ll i = 0;
if (num[0] == 1)
i = 1;
ll sz = num.size();
for (i = 0; i < sz; i ++)
for (ll j = i + 1; j < sz; j ++)
{
x = gcd[num[i]][num[j]];
if ((mask & ((ll)1 << (x - 1))) == 0)
{
atl = x;
tf = false;
i = sz;
break;
}
}
if (tf)
{
if ((ll)idx % (ll)(1e5) == 0)
{
cout << idx << " " << mask << endl;
}
st.push_back(num);
mask ++;
idx ++;
}
else
mask = (mask | ((ll)1 << (atl - 1)));
}
cout << "Done " << mask << endl;
exit(0);
}
void solve()
{
ll n;
cin >> n;
/**cout << st[n].size();
for (ll v : st[n])
cout << " " << v;
cout << endl;*/
}
int main()
{
preprocess();
ll t;
cin >> t;
while(t --)
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
