Submission #642945

#TimeUsernameProblemLanguageResultExecution timeMemory
642945danikoynovPresent (RMI21_present)C++14
0 / 100
1 ms468 KiB
/** ____ ____ ____ ____ ____ ____ ||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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...