Submission #644943

#	Time	Username	Problem	Language	Result	Execution time	Memory
644943		danikoynov	Present (RMI21_present)	C++14	84 / 100	3981 ms	852 KiB

Main

/**
 ____ ____ ____ ____ ____ ____
||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 = 1e6 + 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)700000,(ll)9564415});
p.push_back({(ll)1400000,(ll)24351991});
p.push_back({(ll)2100000,(ll)39311191});
p.push_back({(ll)2800000,(ll)54219543});
p.push_back({(ll)3500000,(ll)71702511});
p.push_back({(ll)4200000,(ll)90883007});
p.push_back({(ll)4900000,(ll)111611247});
p.push_back({(ll)5600000,(ll)135872863});
p.push_back({(ll)6300000,(ll)155518319});
p.push_back({(ll)7000000,(ll)177042815});
p.push_back({(ll)7700000,(ll)204020671});
p.push_back({(ll)8400000,(ll)236979263});
p.push_back({(ll)9100000,(ll)268961851});
p.push_back({(ll)9800000,(ll)279613179});
p.push_back({(ll)10500000,(ll)294690527});
p.push_back({(ll)11200000,(ll)308706239});
p.push_back({(ll)11900000,(ll)323921531});
p.push_back({(ll)12600000,(ll)341606511});
p.push_back({(ll)13300000,(ll)362021431});
p.push_back({(ll)14000000,(ll)382573487});
p.push_back({(ll)14700000,(ll)405605979});
p.push_back({(ll)15400000,(ll)426053963});
p.push_back({(ll)16100000,(ll)448618207});
p.push_back({(ll)16800000,(ll)474584431});
p.push_back({(ll)17500000,(ll)507589687});
p.push_back({(ll)18200000,(ll)540019239});
p.push_back({(ll)18900000,(ll)570504811});
p.push_back({(ll)19600000,(ll)595688247});
p.push_back({(ll)20300000,(ll)638826359});
p.push_back({(ll)21000000,(ll)678626151});
p.push_back({(ll)21700000,(ll)726011963});
p.push_back({(ll)22400000,(ll)793610079});
p.push_back({(ll)23100000,(ll)826389943});
p.push_back({(ll)23800000,(ll)854721463});
p.push_back({(ll)24500000,(ll)891401143});
p.push_back({(ll)25200000,(ll)938045119});
p.push_back({(ll)25900000,(ll)979963451});
p.push_back({(ll)26600000,(ll)1042874047});
p.push_back({(ll)27300000,(ll)1078990197});
p.push_back({(ll)28000000,(ll)1092852607});
p.push_back({(ll)28700000,(ll)1109409423});
p.push_back({(ll)29400000,(ll)1122047951});
p.push_back({(ll)30100000,(ll)1139893599});
p.push_back({(ll)30800000,(ll)1157126975});
p.push_back({(ll)31500000,(ll)1178677551});
p.push_back({(ll)32200000,(ll)1198958559});
p.push_back({(ll)32900000,(ll)1220551247});
p.push_back({(ll)33600000,(ll)1244387135});
p.push_back({(ll)34300000,(ll)1265520255});
p.push_back({(ll)35000000,(ll)1295885951});
p.push_back({(ll)35700000,(ll)1328708095});
p.push_back({(ll)36400000,(ll)1348560047});
p.push_back({(ll)37100000,(ll)1362695899});
p.push_back({(ll)37800000,(ll)1378557103});
p.push_back({(ll)38500000,(ll)1392250783});
p.push_back({(ll)39200000,(ll)1409940287});
p.push_back({(ll)39900000,(ll)1427444831});
p.push_back({(ll)40600000,(ll)1448428447});
p.push_back({(ll)41300000,(ll)1470770559});
p.push_back({(ll)42000000,(ll)1491402959});
p.push_back({(ll)42700000,(ll)1514509391});
p.push_back({(ll)43400000,(ll)1537643519});
p.push_back({(ll)44100000,(ll)1567125311});
p.push_back({(ll)44800000,(ll)1600515903});
p.push_back({(ll)45500000,(ll)1628776287});
p.push_back({(ll)46200000,(ll)1657087207});
p.push_back({(ll)46900000,(ll)1692561279});
p.push_back({(ll)47600000,(ll)1735988767});
p.push_back({(ll)48300000,(ll)1782900799});
p.push_back({(ll)49000000,(ll)1842813439});
p.push_back({(ll)49700000,(ll)1887919423});
p.push_back({(ll)50400000,(ll)1918114351});
p.push_back({(ll)51100000,(ll)1950397775});
p.push_back({(ll)51800000,(ll)1990559663});
p.push_back({(ll)52500000,(ll)2036655551});
p.push_back({(ll)53200000,(ll)2086866751});
p.push_back({(ll)53900000,(ll)2149615658});
p.push_back({(ll)54600000,(ll)2165312383});
p.push_back({(ll)55300000,(ll)2184136063});
p.push_back({(ll)56000000,(ll)2201334879});
p.push_back({(ll)56700000,(ll)2221846399});
p.push_back({(ll)57400000,(ll)2250662847});
p.push_back({(ll)58100000,(ll)2277536703});
p.push_back({(ll)58800000,(ll)2302090239});
p.push_back({(ll)59500000,(ll)2328804095});
p.push_back({(ll)60200000,(ll)2361168127});
p.push_back({(ll)60900000,(ll)2401546447});
p.push_back({(ll)61600000,(ll)2423174879});
p.push_back({(ll)62300000,(ll)2442814463});
p.push_back({(ll)63000000,(ll)2459301631});
p.push_back({(ll)63700000,(ll)2483205983});
p.push_back({(ll)64400000,(ll)2504636543});
p.push_back({(ll)65100000,(ll)2531592383});
p.push_back({(ll)65800000,(ll)2556805567});
p.push_back({(ll)66500000,(ll)2586302079});
p.push_back({(ll)67200000,(ll)2614886911});
p.push_back({(ll)67900000,(ll)2652909951});
p.push_back({(ll)68600000,(ll)2688911263});
p.push_back({(ll)69300000,(ll)2723589375});
p.push_back({(ll)70000000,(ll)2765834239});
p.push_back({(ll)70700000,(ll)2821243483});
p.push_back({(ll)71400000,(ll)2875599615});
p.push_back({(ll)72100000,(ll)2955191823});
p.push_back({(ll)72800000,(ll)2989818143});
p.push_back({(ll)73500000,(ll)3026760255});
p.push_back({(ll)74200000,(ll)3085183487});
p.push_back({(ll)74900000,(ll)3137894047});
p.push_back({(ll)75600000,(ll)3221366479});
p.push_back({(ll)76300000,(ll)3235107583});
p.push_back({(ll)77000000,(ll)3255846975});
p.push_back({(ll)77700000,(ll)3272050559});
p.push_back({(ll)78400000,(ll)3292835855});
p.push_back({(ll)79100000,(ll)3321103519});
p.push_back({(ll)79800000,(ll)3344193663});
p.push_back({(ll)80500000,(ll)3371116031});
p.push_back({(ll)81200000,(ll)3396170239});
p.push_back({(ll)81900000,(ll)3427851359});
p.push_back({(ll)82600000,(ll)3466109183});
p.push_back({(ll)83300000,(ll)3494979711});
p.push_back({(ll)84000000,(ll)3512710399});
p.push_back({(ll)84700000,(ll)3529941711});
p.push_back({(ll)85400000,(ll)3549854719});
p.push_back({(ll)86100000,(ll)3574404351});
p.push_back({(ll)86800000,(ll)3598259263});
p.push_back({(ll)87500000,(ll)3627815423});
p.push_back({(ll)88200000,(ll)3656620031});
p.push_back({(ll)88900000,(ll)3680557183});
p.push_back({(ll)89600000,(ll)3716455583});
p.push_back({(ll)90300000,(ll)3759182495});
p.push_back({(ll)91000000,(ll)3793916223});
p.push_back({(ll)91700000,(ll)3830220351});
p.push_back({(ll)92400000,(ll)3882707711});
p.push_back({(ll)93100000,(ll)3938559487});
p.push_back({(ll)93800000,(ll)4017706751});
p.push_back({(ll)94500000,(ll)4060193567});
p.push_back({(ll)95200000,(ll)4095518335});
p.push_back({(ll)95900000,(ll)4145578623});
p.push_back({(ll)96600000,(ll)4200697887});
p.push_back({(ll)97300000,(ll)4276418047});
p.push_back({(ll)98000000,(ll)4309730503});
p.push_back({(ll)98700000,(ll)4333352623});
p.push_back({(ll)99400000,(ll)4358999183});
p.push_back({(ll)100100000,(ll)4384441877});
p.push_back({(ll)100800000,(ll)4414457623});
p.push_back({(ll)101500000,(ll)4448075679});
p.push_back({(ll)102200000,(ll)4484999535});
p.push_back({(ll)102900000,(ll)4531004623});
p.push_back({(ll)103600000,(ll)4568235343});
p.push_back({(ll)104300000,(ll)4590691927});
p.push_back({(ll)105000000,(ll)4614042983});
p.push_back({(ll)105700000,(ll)4639241895});
p.push_back({(ll)106400000,(ll)4668951471});
p.push_back({(ll)107100000,(ll)4700785743});
p.push_back({(ll)107800000,(ll)4735999055});
p.push_back({(ll)108500000,(ll)4775073023});
p.push_back({(ll)109200000,(ll)4822429535});
p.push_back({(ll)109900000,(ll)4867949799});
p.push_back({(ll)110600000,(ll)4915759423});
p.push_back({(ll)111300000,(ll)4975106735});
p.push_back({(ll)112000000,(ll)5057146687});
p.push_back({(ll)112700000,(ll)5121976183});
p.push_back({(ll)113400000,(ll)5169866327});
p.push_back({(ll)114100000,(ll)5225202999});
p.push_back({(ll)114800000,(ll)5302005167});
p.push_back({(ll)115500000,(ll)5373179191});
p.push_back({(ll)116200000,(ll)5394645695});
p.push_back({(ll)116900000,(ll)5418169575});
p.push_back({(ll)117600000,(ll)5443491463});
p.push_back({(ll)118300000,(ll)5473673575});
p.push_back({(ll)119000000,(ll)5504816221});
p.push_back({(ll)119700000,(ll)5540744015});
p.push_back({(ll)120400000,(ll)5578731727});
p.push_back({(ll)121100000,(ll)5625426079});
p.push_back({(ll)121800000,(ll)5651659103});
p.push_back({(ll)122500000,(ll)5675431507});
p.push_back({(ll)123200000,(ll)5700916383});
p.push_back({(ll)123900000,(ll)5726524247});
p.push_back({(ll)124600000,(ll)5756305751});
p.push_back({(ll)125300000,(ll)5789878911});
p.push_back({(ll)126000000,(ll)5826908319});
p.push_back({(ll)126700000,(ll)5872952655});
p.push_back({(ll)127400000,(ll)5915414583});
p.push_back({(ll)128100000,(ll)5961356983});
p.push_back({(ll)128800000,(ll)6015023031});
p.push_back({(ll)129500000,(ll)6084724655});
p.push_back({(ll)130200000,(ll)6175262695});
p.push_back({(ll)130900000,(ll)6216291431});
p.push_back({(ll)131600000,(ll)6271017791});
p.push_back({(ll)132300000,(ll)6333575871});
p.push_back({(ll)133000000,(ll)6416709103});
p.push_back({(ll)133700000,(ll)6460585687});
p.push_back({(ll)134400000,(ll)6489526975});
p.push_back({(ll)135100000,(ll)6522422999});
p.push_back({(ll)135800000,(ll)6560278103});
p.push_back({(ll)136500000,(ll)6600451231});
p.push_back({(ll)137200000,(ll)6648325455});
p.push_back({(ll)137900000,(ll)6704631247});
p.push_back({(ll)138600000,(ll)6732977511});
p.push_back({(ll)139300000,(ll)6762940735});
p.push_back({(ll)140000000,(ll)6796613279});
p.push_back({(ll)140700000,(ll)6833870927});
p.push_back({(ll)141400000,(ll)6879315023});
p.push_back({(ll)142100000,(ll)6924805327});
p.push_back({(ll)142800000,(ll)6981912167});
p.push_back({(ll)143500000,(ll)7035970647});
p.push_back({(ll)144200000,(ll)7106004671});
p.push_back({(ll)144900000,(ll)7201744031});
p.push_back({(ll)145600000,(ll)7282090815});
p.push_back({(ll)146300000,(ll)7342546367});
p.push_back({(ll)147000000,(ll)7421137103});
p.push_back({(ll)147700000,(ll)7518438695});
p.push_back({(ll)148400000,(ll)7548397247});
p.push_back({(ll)149100000,(ll)7574921383});
p.push_back({(ll)149800000,(ll)7611035583});
p.push_back({(ll)150500000,(ll)7651167407});
p.push_back({(ll)151200000,(ll)7690792271});
p.push_back({(ll)151900000,(ll)7742469471});
p.push_back({(ll)152600000,(ll)7789711183});
p.push_back({(ll)153300000,(ll)7820057167});
p.push_back({(ll)154000000,(ll)7852021095});
p.push_back({(ll)154700000,(ll)7886639911});
p.push_back({(ll)155400000,(ll)7923732559});
p.push_back({(ll)156100000,(ll)7968961999});
p.push_back({(ll)156800000,(ll)8021587407});
p.push_back({(ll)157500000,(ll)8075403479});
p.push_back({(ll)158200000,(ll)8136991319});
p.push_back({(ll)158900000,(ll)8216785599});
p.push_back({(ll)159600000,(ll)8321901671});
p.push_back({(ll)160300000,(ll)8374127935});
p.push_back({(ll)161000000,(ll)8442467927});
p.push_back({(ll)161700000,(ll)8533317039});
p.push_back({(ll)162400000,(ll)8595227991});
p.push_back({(ll)163100000,(ll)8609859863});
p.push_back({(ll)163800000,(ll)8626381643});
p.push_back({(ll)164500000,(ll)8640234735});
p.push_back({(ll)165200000,(ll)8658003823});
p.push_back({(ll)165900000,(ll)8677070391});
p.push_back({(ll)166600000,(ll)8698052887});
p.push_back({(ll)167300000,(ll)8723207863});
p.push_back({(ll)168000000,(ll)8743205051});
p.push_back({(ll)168700000,(ll)8764991343});
p.push_back({(ll)169400000,(ll)8792113355});
p.push_back({(ll)170100000,(ll)8825701579});
p.push_back({(ll)170800000,(ll)8858732299});
p.push_back({(ll)171500000,(ll)8870200983});
p.push_back({(ll)172200000,(ll)8887037407});
p.push_back({(ll)172900000,(ll)8899795247});
p.push_back({(ll)173600000,(ll)8915484095});
p.push_back({(ll)174300000,(ll)8933899999});
p.push_back({(ll)175000000,(ll)8959296779});
p.push_back({(ll)175700000,(ll)8978023479});
p.push_back({(ll)176400000,(ll)8999403675});
p.push_back({(ll)177100000,(ll)9026270875});
p.push_back({(ll)177800000,(ll)9045725791});
p.push_back({(ll)178500000,(ll)9074853359});
p.push_back({(ll)179200000,(ll)9108486751});
p.push_back({(ll)179900000,(ll)9137663983});
p.push_back({(ll)180600000,(ll)9167042487});
p.push_back({(ll)181300000,(ll)9200222679});
p.push_back({(ll)182000000,(ll)9242917871});
p.push_back({(ll)182700000,(ll)9291280059});
p.push_back({(ll)183400000,(ll)9340788079});
p.push_back({(ll)184100000,(ll)9400391535});
p.push_back({(ll)184800000,(ll)9431166447});
p.push_back({(ll)185500000,(ll)9461458679});
p.push_back({(ll)186200000,(ll)9501306223});
p.push_back({(ll)186900000,(ll)9544931183});
p.push_back({(ll)187600000,(ll)9595906815});
p.push_back({(ll)188300000,(ll)9664017067});
p.push_back({(ll)189000000,(ll)9675461815});
p.push_back({(ll)189700000,(ll)9692273207});
p.push_back({(ll)190400000,(ll)9705054295});
p.push_back({(ll)191100000,(ll)9720755127});
p.push_back({(ll)191800000,(ll)9739178839});
p.push_back({(ll)192500000,(ll)9764545335});
p.push_back({(ll)193200000,(ll)9783294999});
p.push_back({(ll)193900000,(ll)9804661783});
p.push_back({(ll)194600000,(ll)9831544071});
p.push_back({(ll)195300000,(ll)9850957663});
p.push_back({(ll)196000000,(ll)9880027999});
p.push_back({(ll)196700000,(ll)9913648063});
p.push_back({(ll)197400000,(ll)9937293167});
p.push_back({(ll)198100000,(ll)9951854711});
p.push_back({(ll)198800000,(ll)9968453403});
p.push_back({(ll)199500000,(ll)9982071487});
p.push_back({(ll)200200000,(ll)10000052683});
p.push_back({(ll)200900000,(ll)10019083231});
p.push_back({(ll)201600000,(ll)10040136023});
p.push_back({(ll)202300000,(ll)10065098079});
p.push_back({(ll)203000000,(ll)10085283739});
p.push_back({(ll)203700000,(ll)10107074651});
p.push_back({(ll)204400000,(ll)10134170479});
p.push_back({(ll)205100000,(ll)10167789743});
p.push_back({(ll)205800000,(ll)10201038135});
p.push_back({(ll)206500000,(ll)10228092727});
p.push_back({(ll)207200000,(ll)10255452863});
p.push_back({(ll)207900000,(ll)10297691071});
p.push_back({(ll)208600000,(ll)10339477183});
p.push_back({(ll)209300000,(ll)10385331963});
p.push_back({(ll)210000000,(ll)10450380143});
p.push_back({(ll)210700000,(ll)10487905403});
p.push_back({(ll)211400000,(ll)10516241647});
p.push_back({(ll)212100000,(ll)10552877751});
p.push_back({(ll)212800000,(ll)10597739455});
p.push_back({(ll)213500000,(ll)10642450671});
p.push_back({(ll)214200000,(ll)10704451423});
p.push_back({(ll)214900000,(ll)10743162327});
p.push_back({(ll)215600000,(ll)10761447871});
p.push_back({(ll)216300000,(ll)10778725487});
p.push_back({(ll)217000000,(ll)10801398711});
p.push_back({(ll)217700000,(ll)10825599151});
p.push_back({(ll)218400000,(ll)10852474351});
p.push_back({(ll)219100000,(ll)10878337887});
p.push_back({(ll)219800000,(ll)10908179163});
p.push_back({(ll)220500000,(ll)10938242527});
p.push_back({(ll)221200000,(ll)10976084703});
p.push_back({(ll)221900000,(ll)11009202543});
p.push_back({(ll)222600000,(ll)11026732383});
p.push_back({(ll)223300000,(ll)11044783447});
p.push_back({(ll)224000000,(ll)11062939851});
p.push_back({(ll)224700000,(ll)11088548575});
p.push_back({(ll)225400000,(ll)11113619807});
p.push_back({(ll)226100000,(ll)11143066843});
p.push_back({(ll)226800000,(ll)11173235455});
p.push_back({(ll)227500000,(ll)11196804527});
p.push_back({(ll)228200000,(ll)11236561631});
p.push_back({(ll)228900000,(ll)11276478575});
p.push_back({(ll)229600000,(ll)11310921407});
p.push_back({(ll)230300000,(ll)11347817687});
p.push_back({(ll)231000000,(ll)11403609847});
p.push_back({(ll)231700000,(ll)11458217455});
p.push_back({(ll)232400000,(ll)11542761019});
p.push_back({(ll)233100000,(ll)11577022143});
p.push_back({(ll)233800000,(ll)11613008983});
p.push_back({(ll)234500000,(ll)11664210815});
p.push_back({(ll)235200000,(ll)11718075119});
p.push_back({(ll)235900000,(ll)11796836703});
p.push_back({(ll)236600000,(ll)11822502107});
p.push_back({(ll)237300000,(ll)11845219803});
p.push_back({(ll)238000000,(ll)11861541815});
p.push_back({(ll)238700000,(ll)11882488919});
p.push_back({(ll)239400000,(ll)11911941551});
p.push_back({(ll)240100000,(ll)11934941879});
p.push_back({(ll)240800000,(ll)11962786555});
p.push_back({(ll)241500000,(ll)11988200159});
p.push_back({(ll)242200000,(ll)12020201839});
p.push_back({(ll)242900000,(ll)12063102303});
p.push_back({(ll)243600000,(ll)12086552347});
p.push_back({(ll)244300000,(ll)12107242207});
p.push_back({(ll)245000000,(ll)12123894519});
p.push_back({(ll)245700000,(ll)12147218231});
p.push_back({(ll)246400000,(ll)12170350943});
p.push_back({(ll)247100000,(ll)12198221079});
p.push_back({(ll)247800000,(ll)12223103711});
p.push_back({(ll)248500000,(ll)12252387759});
p.push_back({(ll)249200000,(ll)12283521903});
p.push_back({(ll)249900000,(ll)12321162187});
p.push_back({(ll)250600000,(ll)12357414651});
p.push_back({(ll)251300000,(ll)12394181867});
p.push_back({(ll)252000000,(ll)12440366527});
p.push_back({(ll)252700000,(ll)12493147631});
p.push_back({(ll)253400000,(ll)12554637679});
p.push_back({(ll)254100000,(ll)12622907759});
p.push_back({(ll)254800000,(ll)12657438935});
p.push_back({(ll)255500000,(ll)12702857079});
p.push_back({(ll)256200000,(ll)12756237039});
p.push_back({(ll)256900000,(ll)12817854143});
p.push_back({(ll)257600000,(ll)12888246199});
p.push_back({(ll)258300000,(ll)12911369663});
p.push_back({(ll)259000000,(ll)12935431511});
p.push_back({(ll)259700000,(ll)12961540727});
p.push_back({(ll)260400000,(ll)12992489007});
p.push_back({(ll)261100000,(ll)13024822871});
p.push_back({(ll)261800000,(ll)13061953967});
p.push_back({(ll)262500000,(ll)13105604447});
p.push_back({(ll)263200000,(ll)13154137627});
p.push_back({(ll)263900000,(ll)13175558615});
p.push_back({(ll)264600000,(ll)13199765719});
p.push_back({(ll)265300000,(ll)13226071735});
p.push_back({(ll)266000000,(ll)13258270895});
p.push_back({(ll)266700000,(ll)13289675951});
p.push_back({(ll)267400000,(ll)13326061743});
p.push_back({(ll)268100000,(ll)13367278431});
p.push_back({(ll)268800000,(ll)13416318687});
p.push_back({(ll)269500000,(ll)13460338231});
p.push_back({(ll)270200000,(ll)13510696639});
p.push_back({(ll)270900000,(ll)13573350239});
p.push_back({(ll)271600000,(ll)13658776663});
p.push_back({(ll)272300000,(ll)13719908151});
p.push_back({(ll)273000000,(ll)13764662999});
p.push_back({(ll)273700000,(ll)13826430703});
p.push_back({(ll)274400000,(ll)13900991983});
p.push_back({(ll)275100000,(ll)13965407959});
p.push_back({(ll)275800000,(ll)13992750431});
p.push_back({(ll)276500000,(ll)14014158711});
p.push_back({(ll)277200000,(ll)14042954103});
p.push_back({(ll)277900000,(ll)14073230967});
p.push_back({(ll)278600000,(ll)14107248111});
p.push_back({(ll)279300000,(ll)14145149663});
p.push_back({(ll)280000000,(ll)14193654623});
p.push_back({(ll)280700000,(ll)14231701463});
p.push_back({(ll)281400000,(ll)14256890615});
p.push_back({(ll)282100000,(ll)14278924215});
p.push_back({(ll)282800000,(ll)14306860599});
p.push_back({(ll)283500000,(ll)14336982751});
p.push_back({(ll)284200000,(ll)14369821039});
p.push_back({(ll)284900000,(ll)14407960239});
p.push_back({(ll)285600000,(ll)14451619639});
p.push_back({(ll)286300000,(ll)14499898551});
p.push_back({(ll)287000000,(ll)14543101495});
p.push_back({(ll)287700000,(ll)14599474487});
p.push_back({(ll)288400000,(ll)14666172079});
p.push_back({(ll)289100000,(ll)14751927999});
p.push_back({(ll)289800000,(ll)14802171831});
p.push_back({(ll)290500000,(ll)14852363447});
p.push_back({(ll)291200000,(ll)14915164863});
p.push_back({(ll)291900000,(ll)15000163823});
p.push_back({(ll)292600000,(ll)15049490903});
p.push_back({(ll)293300000,(ll)15078559959});
p.push_back({(ll)294000000,(ll)15112391855});
p.push_back({(ll)294700000,(ll)15151181535});
p.push_back({(ll)295400000,(ll)15196407231});
p.push_back({(ll)296100000,(ll)15241381231});
p.push_back({(ll)296800000,(ll)15301470559});
p.push_back({(ll)297500000,(ll)15330612663});
p.push_back({(ll)298200000,(ll)15357805787});
p.push_back({(ll)298900000,(ll)15397663671});
p.push_back({(ll)299600000,(ll)15436520175});
p.push_back({(ll)300300000,(ll)15478663919});
p.push_back({(ll)301000000,(ll)15536232623});
p.push_back({(ll)301700000,(ll)15589410167});
p.push_back({(ll)302400000,(ll)15647231215});
p.push_back({(ll)303100000,(ll)15725426367});
p.push_back({(ll)303800000,(ll)15832815359});
p.push_back({(ll)304500000,(ll)15888205175});
p.push_back({(ll)305200000,(ll)15955448503});
p.push_back({(ll)305900000,(ll)16044380271});
p.push_back({(ll)306600000,(ll)16115925463});
p.push_back({(ll)307300000,(ll)16146085335});
p.push_back({(ll)308000000,(ll)16179019119});
p.push_back({(ll)308700000,(ll)16217156591});
p.push_back({(ll)309400000,(ll)16260589279});
p.push_back({(ll)310100000,(ll)16308731247});
p.push_back({(ll)310800000,(ll)16364127583});
p.push_back({(ll)311500000,(ll)16396795375});
p.push_back({(ll)312200000,(ll)16427255255});
p.push_back({(ll)312900000,(ll)16462984535});
p.push_back({(ll)313600000,(ll)16501723575});
p.push_back({(ll)314300000,(ll)16546855087});
p.push_back({(ll)315000000,(ll)16597228383});
p.push_back({(ll)315700000,(ll)16651678455});
p.push_back({(ll)316400000,(ll)16712488759});
p.push_back({(ll)317100000,(ll)16783062895});
p.push_back({(ll)317800000,(ll)16883683055});
p.push_back({(ll)318500000,(ll)16950709951});
p.push_back({(ll)319200000,(ll)17016787383});
p.push_back({(ll)319900000,(ll)17101022047});
p.push_back({(ll)320600000,(ll)17186198743});
p.push_back({(ll)321300000,(ll)17213948319});
p.push_back({(ll)322000000,(ll)17239426495});
p.push_back({(ll)322700000,(ll)17275365087});
p.push_back({(ll)323400000,(ll)17315836031});
p.push_back({(ll)324100000,(ll)17360751999});
p.push_back({(ll)324800000,(ll)17418952319});
p.push_back({(ll)325500000,(ll)17460899455});
p.push_back({(ll)326200000,(ll)17487007903});
p.push_back({(ll)326900000,(ll)17516518655});
p.push_back({(ll)327600000,(ll)17552952447});
p.push_back({(ll)328300000,(ll)17592939007});
p.push_back({(ll)329000000,(ll)17639687039});
p.push_back({(ll)329700000,(ll)17702638719});
p.push_back({(ll)330400000,(ll)17757857151});
p.push_back({(ll)331100000,(ll)17827710719});
p.push_back({(ll)331800000,(ll)17924380255});
p.push_back({(ll)332500000,(ll)18015592831});
p.push_back({(ll)333200000,(ll)18077520951});
p.push_back({(ll)333900000,(ll)18170003583});
p.push_back({(ll)334600000,(ll)18260131991});
p.push_back({(ll)335300000,(ll)18288031707});
p.push_back({(ll)336000000,(ll)18313970047});
p.push_back({(ll)336700000,(ll)18350152479});
p.push_back({(ll)337400000,(ll)18390147327});
p.push_back({(ll)338100000,(ll)18435543423});
p.push_back({(ll)338800000,(ll)18493350399});
p.push_back({(ll)339500000,(ll)18534909021});
p.push_back({(ll)340200000,(ll)18561134815});
p.push_back({(ll)340900000,(ll)18590743935});
p.push_back({(ll)341600000,(ll)18627103167});
p.push_back({(ll)342300000,(ll)18667577855});
p.push_back({(ll)343000000,(ll)18714050943});
p.push_back({(ll)343700000,(ll)18777326079});
p.push_back({(ll)344400000,(ll)18832625151});
p.push_back({(ll)345100000,(ll)18903167359});
p.push_back({(ll)345800000,(ll)18999734015});
p.push_back({(ll)346500000,(ll)19090627327});
p.push_back({(ll)347200000,(ll)19153102591});
p.push_back({(ll)347900000,(ll)19244909055});
p.push_back({(ll)348600000,(ll)19334926575});
p.push_back({(ll)349300000,(ll)19368062847});
p.push_back({(ll)350000000,(ll)19408459207});
p.push_back({(ll)350700000,(ll)19456809983});
p.push_back({(ll)351400000,(ll)19512752511});
p.push_back({(ll)352100000,(ll)19584243583});
p.push_back({(ll)352800000,(ll)19620312799});
p.push_back({(ll)353500000,(ll)19654202751});
p.push_back({(ll)354200000,(ll)19700770015});
p.push_back({(ll)354900000,(ll)19751922431});
p.push_back({(ll)355600000,(ll)19814978655});
p.push_back({(ll)356300000,(ll)19887558839});
p.push_back({(ll)357000000,(ll)19969118303});
p.push_back({(ll)357700000,(ll)20090487679});
p.push_back({(ll)358400000,(ll)20184073439});
p.push_back({(ll)359100000,(ll)20276741631});
p.push_back({(ll)359800000,(ll)20403978911});
p.push_back({(ll)360500000,(ll)20437062111});
p.push_back({(ll)361200000,(ll)20472211839});
p.push_back({(ll)361900000,(ll)20519889279});
p.push_back({(ll)362600000,(ll)20573099263});
p.push_back({(ll)363300000,(ll)20640481663});
p.push_back({(ll)364000000,(ll)20688650335});
p.push_back({(ll)364700000,(ll)20722205279});
p.push_back({(ll)365400000,(ll)20762698495});
p.push_back({(ll)366100000,(ll)20812165887});
p.push_back({(ll)366800000,(ll)20872254559});
p.push_back({(ll)367500000,(ll)20945646303});
p.push_back({(ll)368200000,(ll)21022153087});
p.push_back({(ll)368900000,(ll)21129177599});
p.push_back({(ll)369600000,(ll)21242319415});
p.push_back({(ll)370300000,(ll)21327184767});
p.push_back({(ll)371000000,(ll)21462074239});
p.push_back({(ll)371700000,(ll)21511308927});
p.push_back({(ll)372400000,(ll)21557403135});
p.push_back({(ll)373100000,(ll)21613336159});
p.push_back({(ll)373800000,(ll)21686391903});
p.push_back({(ll)374500000,(ll)21757071599});
p.push_back({(ll)375200000,(ll)21799134431});
p.push_back({(ll)375900000,(ll)21849657695});
p.push_back({(ll)376600000,(ll)21914762623});
p.push_back({(ll)377300000,(ll)21997872511});
p.push_back({(ll)378000000,(ll)22084147319});
p.push_back({(ll)378700000,(ll)22213107967});
p.push_back({(ll)379400000,(ll)22333023615});
p.push_back({(ll)380100000,(ll)22448079615});
p.push_back({(ll)380800000,(ll)22563558575});
p.push_back({(ll)381500000,(ll)22605321567});
p.push_back({(ll)382200000,(ll)22656079295});
p.push_back({(ll)382900000,(ll)22721195391});
p.push_back({(ll)383600000,(ll)22805190527});
p.push_back({(ll)384300000,(ll)22851930079});
p.push_back({(ll)385000000,(ll)22897066223});
p.push_back({(ll)385700000,(ll)22952715135});
p.push_back({(ll)386400000,(ll)23024741855});
p.push_back({(ll)387100000,(ll)23113780735});
p.push_back({(ll)387800000,(ll)23210088383});
p.push_back({(ll)388500000,(ll)23362852607});
p.push_back({(ll)389200000,(ll)23455876319});
p.push_back({(ll)389900000,(ll)23605978623});
p.push_back({(ll)390600000,(ll)23666143999});
p.push_back({(ll)391300000,(ll)23728561023});
p.push_back({(ll)392000000,(ll)23810585983});
p.push_back({(ll)392700000,(ll)23899618815});
p.push_back({(ll)393400000,(ll)23956960511});
p.push_back({(ll)394100000,(ll)24025024383});
p.push_back({(ll)394800000,(ll)24113346943});
p.push_back({(ll)395500000,(ll)24220272063});
p.push_back({(ll)396200000,(ll)24381508351});
p.push_back({(ll)396900000,(ll)24515711583});
p.push_back({(ll)397600000,(ll)24696176703});
p.push_back({(ll)398300000,(ll)24746961791});
p.push_back({(ll)399000000,(ll)24809800639});
p.push_back({(ll)399700000,(ll)24892737279});
p.push_back({(ll)400400000,(ll)24981321055});
p.push_back({(ll)401100000,(ll)25034970975});
p.push_back({(ll)401800000,(ll)25103624959});
p.push_back({(ll)402500000,(ll)25198970623});
p.push_back({(ll)403200000,(ll)25305097087});
p.push_back({(ll)403900000,(ll)25474434431});
p.push_back({(ll)404600000,(ll)25602416863});
p.push_back({(ll)405300000,(ll)25771715711});
p.push_back({(ll)406000000,(ll)25798117631});
p.push_back({(ll)406700000,(ll)25825040319});
p.push_back({(ll)407400000,(ll)25860440543});
p.push_back({(ll)408100000,(ll)25901973727});
p.push_back({(ll)408800000,(ll)25946822239});
p.push_back({(ll)409500000,(ll)26007068927});
p.push_back({(ll)410200000,(ll)26050916223});
p.push_back({(ll)410900000,(ll)26078204767});
p.push_back({(ll)411600000,(ll)26108200735});
p.push_back({(ll)412300000,(ll)26146191323});
p.push_back({(ll)413000000,(ll)26190442751});
p.push_back({(ll)413700000,(ll)26239385983});
p.push_back({(ll)414400000,(ll)26305984895});
p.push_back({(ll)415100000,(ll)26359645783});
p.push_back({(ll)415800000,(ll)26434067455});
p.push_back({(ll)416500000,(ll)26544701695});
p.push_back({(ll)417200000,(ll)26616058591});
p.push_back({(ll)417900000,(ll)26686587071});
p.push_back({(ll)418600000,(ll)26783201143});
p.push_back({(ll)419300000,(ll)26857970047});
p.push_back({(ll)420000000,(ll)26884229823});
p.push_back({(ll)420700000,(ll)26915087687});
p.push_back({(ll)421400000,(ll)26953410943});
p.push_back({(ll)422100000,(ll)26997696083});
p.push_back({(ll)422800000,(ll)27047104847});
p.push_back({(ll)423500000,(ll)27112444055});
p.push_back({(ll)424200000,(ll)27137772479});
p.push_back({(ll)424900000,(ll)27165897439});
p.push_back({(ll)425600000,(ll)27200594047});
p.push_back({(ll)426300000,(ll)27240517823});
p.push_back({(ll)427000000,(ll)27286470895});
p.push_back({(ll)427700000,(ll)27345899903});
p.push_back({(ll)428400000,(ll)27404577535});
p.push_back({(ll)429100000,(ll)27467546847});
p.push_back({(ll)429800000,(ll)27555469951});
p.push_back({(ll)430500000,(ll)27663930615});
p.push_back({(ll)431200000,(ll)27719635711});
p.push_back({(ll)431900000,(ll)27804985087});
p.push_back({(ll)432600000,(ll)27919131743});
p.push_back({(ll)433300000,(ll)27953037591});
p.push_back({(ll)434000000,(ll)27987906927});
p.push_back({(ll)434700000,(ll)28037117151});
p.push_back({(ll)435400000,(ll)28091156351});
p.push_back({(ll)436100000,(ll)28160715775});
p.push_back({(ll)436800000,(ll)28207481503});
p.push_back({(ll)437500000,(ll)28241402239});
p.push_back({(ll)438200000,(ll)28288815127});
p.push_back({(ll)438900000,(ll)28340414847});
p.push_back({(ll)439600000,(ll)28403930075});
p.push_back({(ll)440300000,(ll)28477276639});
p.push_back({(ll)441000000,(ll)28558240511});
p.push_back({(ll)441700000,(ll)28679352063});
p.push_back({(ll)442400000,(ll)28773419903});
p.push_back({(ll)443100000,(ll)28865025919});
p.push_back({(ll)443800000,(ll)28993946847});
p.push_back({(ll)444500000,(ll)29027841759});
p.push_back({(ll)445200000,(ll)29063613439});
p.push_back({(ll)445900000,(ll)29113030847});
p.push_back({(ll)446600000,(ll)29167244031});
p.push_back({(ll)447300000,(ll)29242204927});
p.push_back({(ll)448000000,(ll)29282878687});
p.push_back({(ll)448700000,(ll)29316687199});
p.push_back({(ll)449400000,(ll)29364588911});
p.push_back({(ll)450100000,(ll)29416805887});
p.push_back({(ll)450800000,(ll)29481355647});
p.push_back({(ll)451500000,(ll)29555241207});
p.push_back({(ll)452200000,(ll)29636032223});
p.push_back({(ll)452900000,(ll)29765501823});
p.push_back({(ll)453600000,(ll)29850121951});
p.push_back({(ll)454300000,(ll)29948773119});
p.push_back({(ll)455000000,(ll)30070975231});
p.push_back({(ll)455700000,(ll)30116010175});
p.push_back({(ll)456400000,(ll)30168716775});
p.push_back({(ll)457100000,(ll)30233863535});
p.push_back({(ll)457800000,(ll)30318100863});
p.push_back({(ll)458500000,(ll)30369179359});
p.push_back({(ll)459200000,(ll)30417403263});
p.push_back({(ll)459900000,(ll)30474268031});
p.push_back({(ll)460600000,(ll)30553483135});
p.push_back({(ll)461300000,(ll)30642145023});
p.push_back({(ll)462000000,(ll)30750435071});
p.push_back({(ll)462700000,(ll)30893471711});
p.push_back({(ll)463400000,(ll)30991993087});
p.push_back({(ll)464100000,(ll)31141293823});
p.push_back({(ll)464800000,(ll)31184912991});
p.push_back({(ll)465500000,(ll)31236889983});
p.push_back({(ll)466200000,(ll)31298332159});
p.push_back({(ll)466900000,(ll)31381231615});
p.push_back({(ll)467600000,(ll)31439230399});
p.push_back({(ll)468300000,(ll)31483801343});
p.push_back({(ll)469000000,(ll)31542285535});
p.push_back({(ll)469700000,(ll)31616787199});
p.push_back({(ll)470400000,(ll)31709135039});
p.push_back({(ll)471100000,(ll)31808861439});
p.push_back({(ll)471800000,(ll)31960669055});
p.push_back({(ll)472500000,(ll)32053202495});
p.push_back({(ll)473200000,(ll)32211703807});
p.push_back({(ll)473900000,(ll)32264139487});
p.push_back({(ll)474600000,(ll)32331045247});
p.push_back({(ll)475300000,(ll)32418066815});
p.push_back({(ll)476000000,(ll)32502449087});
p.push_back({(ll)476700000,(ll)32561721823});
p.push_back({(ll)477400000,(ll)32636733311});
p.push_back({(ll)478100000,(ll)32737799679});
p.push_back({(ll)478800000,(ll)32852506239});
p.push_back({(ll)479500000,(ll)33027501567});
p.push_back({(ll)480200000,(ll)33147935487});
p.push_back({(ll)480900000,(ll)33302773823});
p.push_back({(ll)481600000,(ll)33357583455});
p.push_back({(ll)482300000,(ll)33429035263});
p.push_back({(ll)483000000,(ll)33527238111});
p.push_back({(ll)483700000,(ll)33593598687});
p.push_back({(ll)484400000,(ll)33659172223});
p.push_back({(ll)485100000,(ll)33740571007});
p.push_back({(ll)485800000,(ll)33846037887});
p.push_back({(ll)486500000,(ll)33976255871});
p.push_back({(ll)487200000,(ll)34137645823});
p.push_back({(ll)487900000,(ll)34280593279});
p.push_back({(ll)488600000,(ll)34367542119});
p.push_back({(ll)489300000,(ll)34394692223});
p.push_back({(ll)490000000,(ll)34414927359});
p.push_back({(ll)490700000,(ll)34460526399});
p.push_back({(ll)491400000,(ll)34499267663});
p.push_back({(ll)492100000,(ll)34530555007});
p.push_back({(ll)492800000,(ll)34564507007});
p.push_back({(ll)493500000,(ll)34629201599});
p.push_back({(ll)494200000,(ll)34648391743});
p.push_back({(ll)494900000,(ll)34669011679});
p.push_back({(ll)495600000,(ll)34699125119});
p.push_back({(ll)496300000,(ll)34749011839});
p.push_back({(ll)497000000,(ll)34781979263});
p.push_back({(ll)497700000,(ll)34812891167});
p.push_back({(ll)498400000,(ll)34865231135});
p.push_back({(ll)499100000,(ll)34922106229});
p.push_back({(ll)499800000,(ll)34999995327});
p.push_back({(ll)500500000,(ll)35082679039});
p.push_back({(ll)501200000,(ll)35185038911});
p.push_back({(ll)501900000,(ll)35253621631});
p.push_back({(ll)502600000,(ll)35341474543});
p.push_back({(ll)503300000,(ll)35437879663});
p.push_back({(ll)504000000,(ll)35458484415});
p.push_back({(ll)504700000,(ll)35483066079});
p.push_back({(ll)505400000,(ll)35517371751});
p.push_back({(ll)506100000,(ll)35568519919});
p.push_back({(ll)506800000,(ll)35595372927});
p.push_back({(ll)507500000,(ll)35624477887});
p.push_back({(ll)508200000,(ll)35686302591});
p.push_back({(ll)508900000,(ll)35715529663});
p.push_back({(ll)509600000,(ll)35739183327});
p.push_back({(ll)510300000,(ll)35760789759});
p.push_back({(ll)511000000,(ll)35807586751});
p.push_back({(ll)511700000,(ll)35845049071});
p.push_back({(ll)512400000,(ll)35876062559});
p.push_back({(ll)513100000,(ll)35917437951});
p.push_back({(ll)513800000,(ll)35978832319});
p.push_back({(ll)514500000,(ll)36039698223});
p.push_back({(ll)515200000,(ll)36139022063});
p.push_back({(ll)515900000,(ll)36244003775});
p.push_back({(ll)516600000,(ll)36297311103});
p.push_back({(ll)517300000,(ll)36396448639});
p.push_back({(ll)518000000,(ll)36508114479});
p.push_back({(ll)518700000,(ll)36531272831});
p.push_back({(ll)519400000,(ll)36561552959});
p.push_back({(ll)520100000,(ll)36613571871});
p.push_back({(ll)520800000,(ll)36658585183});
p.push_back({(ll)521500000,(ll)36690558911});
p.push_back({(ll)522200000,(ll)36746233823});
p.push_back({(ll)522900000,(ll)36788443823});
p.push_back({(ll)523600000,(ll)36815754719});
p.push_back({(ll)524300000,(ll)36855438271});
p.push_back({(ll)525000000,(ll)36913260511});
p.push_back({(ll)525700000,(ll)36946048479});
p.push_back({(ll)526400000,(ll)36982100799});
p.push_back({(ll)527100000,(ll)37052385215});
p.push_back({(ll)527800000,(ll)37151346623});
p.push_back({(ll)528500000,(ll)37249481727});
p.push_back({(ll)529200000,(ll)37353367151});
p.push_back({(ll)529900000,(ll)37467967359});
p.push_back({(ll)530600000,(ll)37582867935});
p.push_back({(ll)531300000,(ll)37608054719});
p.push_back({(ll)532000000,(ll)37636359103});
p.push_back({(ll)532700000,(ll)37689239519});
p.push_back({(ll)533400000,(ll)37733889919});
p.push_back({(ll)534100000,(ll)37766343615});
p.push_back({(ll)534800000,(ll)37822236639});
p.push_back({(ll)535500000,(ll)37866217055});
p.push_back({(ll)536200000,(ll)37890176991});
p.push_back({(ll)536900000,(ll)37934648607});
p.push_back({(ll)537600000,(ll)37988148335});
p.push_back({(ll)538300000,(ll)38020812671});
p.push_back({(ll)539000000,(ll)38058076127});
p.push_back({(ll)539700000,(ll)38134617279});
p.push_back({(ll)540400000,(ll)38237466495});
p.push_back({(ll)541100000,(ll)38334159295});
p.push_back({(ll)541800000,(ll)38433430255});
p.push_back({(ll)542500000,(ll)38547799807});
p.push_back({(ll)543200000,(ll)38658688703});
p.push_back({(ll)543900000,(ll)38692917551});
p.push_back({(ll)544600000,(ll)38740981087});
p.push_back({(ll)545300000,(ll)38804274367});
p.push_back({(ll)546000000,(ll)38856951135});
p.push_back({(ll)546700000,(ll)38929065343});
p.push_back({(ll)547400000,(ll)38964204575});
p.push_back({(ll)548100000,(ll)39021689855});
p.push_back({(ll)548800000,(ll)39078653119});
p.push_back({(ll)549500000,(ll)39133756383});
p.push_back({(ll)550200000,(ll)39227450479});
p.push_back({(ll)550900000,(ll)39350075135});
p.push_back({(ll)551600000,(ll)39487630911});
p.push_back({(ll)552300000,(ll)39607336703});
p.push_back({(ll)553000000,(ll)39733654975});
p.push_back({(ll)553700000,(ll)39768138207});
p.push_back({(ll)554400000,(ll)39819931135});
p.push_back({(ll)555100000,(ll)39881641183});
p.push_back({(ll)555800000,(ll)39935218655});
p.push_back({(ll)556500000,(ll)40005343375});
p.push_back({(ll)557200000,(ll)40042601951});
p.push_back({(ll)557900000,(ll)40100218815});
p.push_back({(ll)558600000,(ll)40155718879});
p.push_back({(ll)559300000,(ll)40217793983});
p.push_back({(ll)560000000,(ll)40305213375});
p.push_back({(ll)560700000,(ll)40435650495});
p.push_back({(ll)561400000,(ll)40569323391});
p.push_back({(ll)562100000,(ll)40691326847});
p.push_back({(ll)562800000,(ll)40811270079});
p.push_back({(ll)563500000,(ll)40858574783});
p.push_back({(ll)564200000,(ll)40940640223});
p.push_back({(ll)564900000,(ll)40991956863});
p.push_back({(ll)565600000,(ll)41075986751});
p.push_back({(ll)566300000,(ll)41122981759});
p.push_back({(ll)567000000,(ll)41205446111});
p.push_back({(ll)567700000,(ll)41255875519});
p.push_back({(ll)568400000,(ll)41346849983});
p.push_back({(ll)569100000,(ll)41495854847});
p.push_back({(ll)569800000,(ll)41647470015});
p.push_back({(ll)570500000,(ll)41803906559});
p.push_back({(ll)571200000,(ll)41903275967});
p.push_back({(ll)571900000,(ll)41960674111});
p.push_back({(ll)572600000,(ll)42031383871});
p.push_back({(ll)573300000,(ll)42097487199});
p.push_back({(ll)574000000,(ll)42165946655});
p.push_back({(ll)574700000,(ll)42216769471});
p.push_back({(ll)575400000,(ll)42295471327});
p.push_back({(ll)576100000,(ll)42351564255});
p.push_back({(ll)576800000,(ll)42461343679});
p.push_back({(ll)577500000,(ll)42619191231});
p.push_back({(ll)578200000,(ll)42782955455});
p.push_back({(ll)578900000,(ll)42950297743});
p.push_back({(ll)579600000,(ll)42970437567});
p.push_back({(ll)580300000,(ll)42991193695});
p.push_back({(ll)581000000,(ll)43021997455});
p.push_back({(ll)581700000,(ll)43073924991});
p.push_back({(ll)582400000,(ll)43106452351});
p.push_back({(ll)583100000,(ll)43137179583});
p.push_back({(ll)583800000,(ll)43191910367});
p.push_back({(ll)584500000,(ll)43229211583});
p.push_back({(ll)585200000,(ll)43255031151});
p.push_back({(ll)585900000,(ll)43276296063});
p.push_back({(ll)586600000,(ll)43324349743});
p.push_back({(ll)587300000,(ll)43363381215});
p.push_back({(ll)588000000,(ll)43392994271});
p.push_back({(ll)588700000,(ll)43439076735});
p.push_back({(ll)589400000,(ll)43501686575});
p.push_back({(ll)590100000,(ll)43564403503});
p.push_back({(ll)590800000,(ll)43659428463});
p.push_back({(ll)591500000,(ll)43763972847});
p.push_back({(ll)592200000,(ll)43825613247});
p.push_back({(ll)592900000,(ll)43925005503});
p.push_back({(ll)593600000,(ll)44025959359});
p.push_back({(ll)594300000,(ll)44046814687});
p.push_back({(ll)595000000,(ll)44070240127});
p.push_back({(ll)595700000,(ll)44103129567});
p.push_back({(ll)596400000,(ll)44158200047});
p.push_back({(ll)597100000,(ll)44186836735});
p.push_back({(ll)597800000,(ll)44214690895});
p.push_back({(ll)598500000,(ll)44278449503});
p.push_back({(ll)599200000,(ll)44308796959});
p.push_back({(ll)599900000,(ll)44330663247});
p.push_back({(ll)600600000,(ll)44358078207});
p.push_back({(ll)601300000,(ll)44406254559});
p.push_back({(ll)602000000,(ll)44443628479});
p.push_back({(ll)602700000,(ll)44472863343});
p.push_back({(ll)603400000,(ll)44526969663});
p.push_back({(ll)604100000,(ll)44583630015});
p.push_back({(ll)604800000,(ll)44661899135});
p.push_back({(ll)605500000,(ll)44744853375});
p.push_back({(ll)606200000,(ll)44847935807});
p.push_back({(ll)606900000,(ll)44916846463});
p.push_back({(ll)607600000,(ll)45004865407});
p.push_back({(ll)608300000,(ll)45102218863});
p.push_back({(ll)609000000,(ll)45133501375});
p.push_back({(ll)609700000,(ll)45165715391});
p.push_back({(ll)610400000,(ll)45231533503});
p.push_back({(ll)611100000,(ll)45263919583});
p.push_back({(ll)611800000,(ll)45294993151});
p.push_back({(ll)612500000,(ll)45366446047});
p.push_back({(ll)613200000,(ll)45390778303});
p.push_back({(ll)613900000,(ll)45420676767});
p.push_back({(ll)614600000,(ll)45474185087});
p.push_back({(ll)615300000,(ll)45519220319});
p.push_back({(ll)616000000,(ll)45552469343});
p.push_back({(ll)616700000,(ll)45611950015});
p.push_back({(ll)617400000,(ll)45685002111});
p.push_back({(ll)618100000,(ll)45802071663});
p.push_back({(ll)618800000,(ll)45911300543});
p.push_back({(ll)619500000,(ll)46010281919});
p.push_back({(ll)620200000,(ll)46108360639});
p.push_back({(ll)620900000,(ll)46187827071});
p.push_back({(ll)621600000,(ll)46212196319});
p.push_back({(ll)622300000,(ll)46258412415});
p.push_back({(ll)623000000,(ll)46310560735});
p.push_back({(ll)623700000,(ll)46343738303});
p.push_back({(ll)624400000,(ll)46391365951});
p.push_back({(ll)625100000,(ll)46445306847});
p.push_back({(ll)625800000,(ll)46476448703});
p.push_back({(ll)626500000,(ll)46509503295});
p.push_back({(ll)627200000,(ll)46574281839});
p.push_back({(ll)627900000,(ll)46607602495});
p.push_back({(ll)628600000,(ll)46641329551});
p.push_back({(ll)629300000,(ll)46712160879});
p.push_back({(ll)630000000,(ll)46798389119});
p.push_back({(ll)630700000,(ll)46898081535});
p.push_back({(ll)631400000,(ll)47013279615});
p.push_back({(ll)632100000,(ll)47120923311});
p.push_back({(ll)632800000,(ll)47245081535});
p.push_back({(ll)633500000,(ll)47280523231});
p.push_back({(ll)634200000,(ll)47325502879});
p.push_back({(ll)634900000,(ll)47391485919});
p.push_back({(ll)635600000,(ll)47446243295});
p.push_back({(ll)636300000,(ll)47519575663});
p.push_back({(ll)637000000,(ll)47557242335});
p.push_back({(ll)637700000,(ll)47617834495});
p.push_back({(ll)638400000,(ll)47677542335});
p.push_back({(ll)639100000,(ll)47740918239});
p.push_back({(ll)639800000,(ll)47829626751});
p.push_back({(ll)640500000,(ll)47959392127});
p.push_back({(ll)641200000,(ll)48090693567});
p.push_back({(ll)641900000,(ll)48222124991});
p.push_back({(ll)642600000,(ll)48332299631});
p.push_back({(ll)643300000,(ll)48370108703});
p.push_back({(ll)644000000,(ll)48433683327});
p.push_back({(ll)644700000,(ll)48489404383});
p.push_back({(ll)645400000,(ll)48559877471});
p.push_back({(ll)646100000,(ll)48611394895});
p.push_back({(ll)646800000,(ll)48653967327});
p.push_back({(ll)647500000,(ll)48723285343});
p.push_back({(ll)648200000,(ll)48772247487});
p.push_back({(ll)648900000,(ll)48859565951});
p.push_back({(ll)649600000,(ll)48964582191});
p.push_back({(ll)650300000,(ll)49124162863});
p.push_back({(ll)651000000,(ll)49225559415});
p.push_back({(ll)651700000,(ll)49375793023});
p.push_back({(ll)652400000,(ll)49430758367});
p.push_back({(ll)653100000,(ll)49499652063});
p.push_back({(ll)653800000,(ll)49564532671});
p.push_back({(ll)654500000,(ll)49649093087});
p.push_back({(ll)655200000,(ll)49699178431});
p.push_back({(ll)655900000,(ll)49768046559});
p.push_back({(ll)656600000,(ll)49832956895});
p.push_back({(ll)657300000,(ll)49917474143});
p.push_back({(ll)658000000,(ll)50064162687});
p.push_back({(ll)658700000,(ll)50218303231});
p.push_back({(ll)659400000,(ll)50367753407});
p.push_back({(ll)660100000,(ll)50485675967});
p.push_back({(ll)660800000,(ll)50537235423});
p.push_back({(ll)661500000,(ll)50617009087});
p.push_back({(ll)662200000,(ll)50674483135});
p.push_back({(ll)662900000,(ll)50754074559});
p.push_back({(ll)663600000,(ll)50805650399});
p.push_back({(ll)664300000,(ll)50885429183});
p.push_back({(ll)665000000,(ll)50942863295});
p.push_back({(ll)665700000,(ll)51054587647});
p.push_back({(ll)666400000,(ll)51217132543});
p.push_back({(ll)667100000,(ll)51376371647});
p.push_back({(ll)667800000,(ll)51541851371});
p.push_back({(ll)668500000,(ll)51579847743});
p.push_back({(ll)669200000,(ll)51646429055});
p.push_back({(ll)669900000,(ll)51714948863});
p.push_back({(ll)670600000,(ll)51812176767});
p.push_back({(ll)671300000,(ll)51850795455});
p.push_back({(ll)672000000,(ll)51922714111});
p.push_back({(ll)672700000,(ll)51990462207});
p.push_back({(ll)673400000,(ll)52097779061});
p.push_back({(ll)674100000,(ll)52251229951});
p.push_back({(ll)674800000,(ll)52410404415});
p.push_back({(ll)675500000,(ll)52614836703});
p.push_back({(ll)676200000,(ll)52653214047});
p.push_back({(ll)676900000,(ll)52718585791});
p.push_back({(ll)677600000,(ll)52787777871});
p.push_back({(ll)678300000,(ll)52884956415});
p.push_back({(ll)679000000,(ll)52923223935});
p.push_back({(ll)679700000,(ll)52991892863});
p.push_back({(ll)680400000,(ll)53061097951});
p.push_back({(ll)681100000,(ll)53169697791});
p.push_back({(ll)681800000,(ll)53322481407});
p.push_back({(ll)682500000,(ll)53479870079});
p.push_back({(ll)683200000,(ll)53688175487});
p.push_back({(ll)683900000,(ll)53739083647});
p.push_back({(ll)684600000,(ll)53827703119});
p.push_back({(ll)685300000,(ll)53909593599});
p.push_back({(ll)686000000,(ll)53990279039});
p.push_back({(ll)686700000,(ll)54064022879});
p.push_back({(ll)687400000,(ll)54142762879});
p.push_back({(ll)688100000,(ll)54272769787});
p.push_back({(ll)688800000,(ll)54498914047});
p.push_back({(ll)689500000,(ll)54683299583});
p.push_back({(ll)690200000,(ll)54797763807});
p.push_back({(ll)690900000,(ll)54881180607});
p.push_back({(ll)691600000,(ll)54951247743});
p.push_back({(ll)692300000,(ll)55048773215});
p.push_back({(ll)693000000,(ll)55110450671});
p.push_back({(ll)693700000,(ll)55199218143});
p.push_back({(ll)694400000,(ll)55308238587});
p.push_back({(ll)695100000,(ll)55493967359});
p.push_back({(ll)695800000,(ll)55712873471});
p.push_back({(ll)696500000,(ll)55865245183});
p.push_back({(ll)697200000,(ll)55961648127});
p.push_back({(ll)697900000,(ll)56084344831});
p.push_back({(ll)698600000,(ll)56158506879});
p.push_back({(ll)699300000,(ll)56271267711});
p.push_back({(ll)700000000,(ll)56417623807});
p.push_back({(ll)700700000,(ll)56673722239});
p.push_back({(ll)701400000,(ll)56913185663});
p.push_back({(ll)702100000,(ll)56984669661});
p.push_back({(ll)702800000,(ll)57096322943});
p.push_back({(ll)703500000,(ll)57210376991});
p.push_back({(ll)704200000,(ll)57309634047});
p.push_back({(ll)704900000,(ll)57430069119});
p.push_back({(ll)705600000,(ll)57643450111});
p.push_back({(ll)706300000,(ll)57889701631});
p.push_back({(ll)707000000,(ll)58038947775});
p.push_back({(ll)707700000,(ll)58168412031});
p.push_back({(ll)708400000,(ll)58290118527});
p.push_back({(ll)709100000,(ll)58418308319});
p.push_back({(ll)709800000,(ll)58592894847});
p.push_back({(ll)710500000,(ll)58909134719});
p.push_back({(ll)711200000,(ll)59096628991});
p.push_back({(ll)711900000,(ll)59224552319});
p.push_back({(ll)712600000,(ll)59348729727});
p.push_back({(ll)713300000,(ll)59468275455});
p.push_back({(ll)714000000,(ll)59627249535});
p.push_back({(ll)714700000,(ll)59916193663});
p.push_back({(ll)715400000,(ll)60144372799});
p.push_back({(ll)716100000,(ll)60185523807});
p.push_back({(ll)716800000,(ll)60268531583});
p.push_back({(ll)717500000,(ll)60335805311});
p.push_back({(ll)718200000,(ll)60419229791});
p.push_back({(ll)718900000,(ll)60465193823});
p.push_back({(ll)719600000,(ll)60549596255});
p.push_back({(ll)720300000,(ll)60629540735});
p.push_back({(ll)721000000,(ll)60753116159});
p.push_back({(ll)721700000,(ll)60952139647});
p.push_back({(ll)722400000,(ll)61104586495});
p.push_back({(ll)723100000,(ll)61225441791});
p.push_back({(ll)723800000,(ll)61272576799});
p.push_back({(ll)724500000,(ll)61356521087});
p.push_back({(ll)725200000,(ll)61440270719});
p.push_back({(ll)725900000,(ll)61504769919});
p.push_back({(ll)726600000,(ll)61557008895});
p.push_back({(ll)727300000,(ll)61635911551});
p.push_back({(ll)728000000,(ll)61729959807});
p.push_back({(ll)728700000,(ll)61875662591});
p.push_back({(ll)729400000,(ll)62046191359});
p.push_back({(ll)730100000,(ll)62212283903});
p.push_back({(ll)730800000,(ll)62315765631});
p.push_back({(ll)731500000,(ll)62405365247});
p.push_back({(ll)732200000,(ll)62478424027});
p.push_back({(ll)732900000,(ll)62569336255});
p.push_back({(ll)733600000,(ll)62646289759});
p.push_back({(ll)734300000,(ll)62723563263});
p.push_back({(ll)735000000,(ll)62849994623});
p.push_back({(ll)735700000,(ll)63075023871});
p.push_back({(ll)736400000,(ll)63257493247});
p.push_back({(ll)737100000,(ll)63386191743});
p.push_back({(ll)737800000,(ll)63467535871});
p.push_back({(ll)738500000,(ll)63540129663});
p.push_back({(ll)739200000,(ll)63638944991});
p.push_back({(ll)739900000,(ll)63704131455});
p.push_back({(ll)740600000,(ll)63791163263});
p.push_back({(ll)741300000,(ll)63907530303});
p.push_back({(ll)742000000,(ll)64106823167});
p.push_back({(ll)742700000,(ll)64312251391});
p.push_back({(ll)743400000,(ll)64461206911});
p.push_back({(ll)744100000,(ll)64564252543});
p.push_back({(ll)744800000,(ll)64694948735});
p.push_back({(ll)745500000,(ll)64765920127});
p.push_back({(ll)746200000,(ll)64881246079});
p.push_back({(ll)746900000,(ll)65064547711});
p.push_back({(ll)747600000,(ll)65308938239});
p.push_back({(ll)748300000,(ll)65520832383});
p.push_back({(ll)749000000,(ll)65618270143});
p.push_back({(ll)749700000,(ll)65739202431});
p.push_back({(ll)750400000,(ll)65822520191});
p.push_back({(ll)751100000,(ll)65937690495});
p.push_back({(ll)751800000,(ll)66090094463});
p.push_back({(ll)752500000,(ll)66345700607});
p.push_back({(ll)753200000,(ll)66588974975});
p.push_back({(ll)753900000,(ll)66707406591});
p.push_back({(ll)754600000,(ll)66843645407});
p.push_back({(ll)755300000,(ll)66949195647});
p.push_back({(ll)756000000,(ll)67093134847});
p.push_back({(ll)756700000,(ll)67382619903});
p.push_back({(ll)757400000,(ll)67652861823});
p.push_back({(ll)758100000,(ll)67769298815});
p.push_back({(ll)758800000,(ll)67914652543});
p.push_back({(ll)759500000,(ll)68016750463});
p.push_back({(ll)760200000,(ll)68153368447});
p.push_back({(ll)760900000,(ll)68440571391});
p.push_back({(ll)761600000,(ll)68720023057});
p.push_back({(ll)762300000,(ll)68730753259});
p.push_back({(ll)763000000,(ll)68745781151});
p.push_back({(ll)763700000,(ll)68759766503});
p.push_back({(ll)764400000,(ll)68775027803});
p.push_back({(ll)765100000,(ll)68792693711});
p.push_back({(ll)765800000,(ll)68813102477});
p.push_back({(ll)766500000,(ll)68833777383});
p.push_back({(ll)767200000,(ll)68856681263});
p.push_back({(ll)767900000,(ll)68877129963});
p.push_back({(ll)768600000,(ll)68899839211});
p.push_back({(ll)769300000,(ll)68925691867});
p.push_back({(ll)770000000,(ll)68958664667});
p.push_back({(ll)770700000,(ll)68989424871});
p.push_back({(ll)771400000,(ll)69000874911});
p.push_back({(ll)772100000,(ll)69016799135});
p.push_back({(ll)772800000,(ll)69029238439});
p.push_back({(ll)773500000,(ll)69044934019});
p.push_back({(ll)774200000,(ll)69062436327});
p.push_back({(ll)774900000,(ll)69084920735});
p.push_back({(ll)775600000,(ll)69104647783});
p.push_back({(ll)776300000,(ll)69126730923});
p.push_back({(ll)777000000,(ll)69148187387});
p.push_back({(ll)777700000,(ll)69170786111});
p.push_back({(ll)778400000,(ll)69196328911});
p.push_back({(ll)779100000,(ll)69229359055});
p.push_back({(ll)779800000,(ll)69261146731});
p.push_back({(ll)780500000,(ll)69292005987});
p.push_back({(ll)781200000,(ll)69320941247});
p.push_back({(ll)781900000,(ll)69361275111});
p.push_back({(ll)782600000,(ll)69403542763});
p.push_back({(ll)783300000,(ll)69452471551});
p.push_back({(ll)784000000,(ll)69524848693});
p.push_back({(ll)784700000,(ll)69548978391});
p.push_back({(ll)785400000,(ll)69577535831});
p.push_back({(ll)786100000,(ll)69615437751});
p.push_back({(ll)786800000,(ll)69661373011});
p.push_back({(ll)787500000,(ll)69704687471});
p.push_back({(ll)788200000,(ll)69767132623});
p.push_back({(ll)788900000,(ll)69799640271});
p.push_back({(ll)789600000,(ll)69813932887});
p.push_back({(ll)790300000,(ll)69829666923});
p.push_back({(ll)791000000,(ll)69843502911});
p.push_back({(ll)791700000,(ll)69861121501});
p.push_back({(ll)792400000,(ll)69878602047});
p.push_back({(ll)793100000,(ll)69899571463});
p.push_back({(ll)793800000,(ll)69922184639});
p.push_back({(ll)794500000,(ll)69942538047});
p.push_back({(ll)795200000,(ll)69965610815});
p.push_back({(ll)795900000,(ll)69988866975});
p.push_back({(ll)796600000,(ll)70018334527});
p.push_back({(ll)797300000,(ll)70051737503});
p.push_back({(ll)798000000,(ll)70068865259});
p.push_back({(ll)798700000,(ll)70083483033});
p.push_back({(ll)799400000,(ll)70099416899});
p.push_back({(ll)800100000,(ll)70113132611});
p.push_back({(ll)800800000,(ll)70131003795});
p.push_back({(ll)801500000,(ll)70149144903});
p.push_back({(ll)802200000,(ll)70169469459});
p.push_back({(ll)802900000,(ll)70194118559});
p.push_back({(ll)803600000,(ll)70213245467});
p.push_back({(ll)804300000,(ll)70235802767});
p.push_back({(ll)805000000,(ll)70261430175});
p.push_back({(ll)805700000,(ll)70291799039});
p.push_back({(ll)806400000,(ll)70325192543});
p.push_back({(ll)807100000,(ll)70351454015});
p.push_back({(ll)807800000,(ll)70380302191});
p.push_back({(ll)808500000,(ll)70416928575});
p.push_back({(ll)809200000,(ll)70464355947});
p.push_back({(ll)809900000,(ll)70505385599});
p.push_back({(ll)810600000,(ll)70568573295});
p.push_back({(ll)811300000,(ll)70611198183});
p.push_back({(ll)812000000,(ll)70639526375});
p.push_back({(ll)812700000,(ll)70672318271});
p.push_back({(ll)813400000,(ll)70715541423});
p.push_back({(ll)814100000,(ll)70764689215});
p.push_back({(ll)814800000,(ll)70813888367});
p.push_back({(ll)815500000,(ll)70869975855});
p.push_back({(ll)816200000,(ll)70886343639});
p.push_back({(ll)816900000,(ll)70904962879});
p.push_back({(ll)817600000,(ll)70922553759});
p.push_back({(ll)818300000,(ll)70944401359});
p.push_back({(ll)819000000,(ll)70972072919});
p.push_back({(ll)819700000,(ll)71001528797});
p.push_back({(ll)820400000,(ll)71024303007});
p.push_back({(ll)821100000,(ll)71052195743});
p.push_back({(ll)821800000,(ll)71085825855});
p.push_back({(ll)822500000,(ll)71125042015});
p.push_back({(ll)823200000,(ll)71144445163});
p.push_back({(ll)823900000,(ll)71166860687});
p.push_back({(ll)824600000,(ll)71181961191});
p.push_back({(ll)825300000,(ll)71204346575});
p.push_back({(ll)826000000,(ll)71226675103});
p.push_back({(ll)826700000,(ll)71254246887});
p.push_back({(ll)827400000,(ll)71278531801});
p.push_back({(ll)828100000,(ll)71307697103});
p.push_back({(ll)828800000,(ll)71338041295});
p.push_back({(ll)829500000,(ll)71374855375});
p.push_back({(ll)830200000,(ll)71410525427});
p.push_back({(ll)830900000,(ll)71445349071});
p.push_back({(ll)831600000,(ll)71491913687});
p.push_back({(ll)832300000,(ll)71544582763});
p.push_back({(ll)833000000,(ll)71606240207});
p.push_back({(ll)833700000,(ll)71676817767});
p.push_back({(ll)834400000,(ll)71711496623});
p.push_back({(ll)835100000,(ll)71753743343});
p.push_back({(ll)835800000,(ll)71809171263});
p.push_back({(ll)836500000,(ll)71863545663});
p.push_back({(ll)837200000,(ll)71941817191});
p.push_back({(ll)837900000,(ll)71957619731});
p.push_back({(ll)838600000,(ll)71976662707});
p.push_back({(ll)839300000,(ll)71993458803});
p.push_back({(ll)840000000,(ll)72014140391});
p.push_back({(ll)840700000,(ll)72042761423});
p.push_back({(ll)841400000,(ll)72066577895});
p.push_back({(ll)842100000,(ll)72093842767});
p.push_back({(ll)842800000,(ll)72119347663});
p.push_back({(ll)843500000,(ll)72150463439});
p.push_back({(ll)844200000,(ll)72192415647});
p.push_back({(ll)844900000,(ll)72215736723});
p.push_back({(ll)845600000,(ll)72233721663});
p.push_back({(ll)846300000,(ll)72250861131});
p.push_back({(ll)847000000,(ll)72274230411});
p.push_back({(ll)847700000,(ll)72296457175});
p.push_back({(ll)848400000,(ll)72322060207});
p.push_back({(ll)849100000,(ll)72348701769});
p.push_back({(ll)849800000,(ll)72378318687});
p.push_back({(ll)850500000,(ll)72403787007});
p.push_back({(ll)851200000,(ll)72444293771});
p.push_back({(ll)851900000,(ll)72480850407});
p.push_back({(ll)852600000,(ll)72515577783});
p.push_back({(ll)853300000,(ll)72553367527});
p.push_back({(ll)854000000,(ll)72612314943});
p.push_back({(ll)854700000,(ll)72665109407});
p.push_back({(ll)855400000,(ll)72747107431});
p.push_back({(ll)856100000,(ll)72781837555});
p.push_back({(ll)856800000,(ll)72818168783});
p.push_back({(ll)857500000,(ll)72870715199});
p.push_back({(ll)858200000,(ll)72926508267});
p.push_back({(ll)858900000,(ll)73005819743});
p.push_back({(ll)859600000,(ll)73032079003});
p.push_back({(ll)860300000,(ll)73054562151});
p.push_back({(ll)861000000,(ll)73082077581});
p.push_back({(ll)861700000,(ll)73107916727});
p.push_back({(ll)862400000,(ll)73137461207});
p.push_back({(ll)863100000,(ll)73171461983});
p.push_back({(ll)863800000,(ll)73210539215});
p.push_back({(ll)864500000,(ll)73254399903});
p.push_back({(ll)865200000,(ll)73289250279});
p.push_back({(ll)865900000,(ll)73314348135});
p.push_back({(ll)866600000,(ll)73335877279});
p.push_back({(ll)867300000,(ll)73362595037});
p.push_back({(ll)868000000,(ll)73391017319});
p.push_back({(ll)868700000,(ll)73422704591});
p.push_back({(ll)869400000,(ll)73459042255});
p.push_back({(ll)870100000,(ll)73501005141});
p.push_back({(ll)870800000,(ll)73550476655});
p.push_back({(ll)871500000,(ll)73590582135});
p.push_back({(ll)872200000,(ll)73641064023});
p.push_back({(ll)872900000,(ll)73704136319});
p.push_back({(ll)873600000,(ll)73789416775});
p.push_back({(ll)874300000,(ll)73849249655});
p.push_back({(ll)875000000,(ll)73893367607});
p.push_back({(ll)875700000,(ll)73954695087});
p.push_back({(ll)876400000,(ll)74028257199});
p.push_back({(ll)877100000,(ll)74093838503});
p.push_back({(ll)877800000,(ll)74118285119});
p.push_back({(ll)878500000,(ll)74140041687});
p.push_back({(ll)879200000,(ll)74165830887});
p.push_back({(ll)879900000,(ll)74195113295});
p.push_back({(ll)880600000,(ll)74227208095});
p.push_back({(ll)881300000,(ll)74262527951});
p.push_back({(ll)882000000,(ll)74303307247});
p.push_back({(ll)882700000,(ll)74352693151});
p.push_back({(ll)883400000,(ll)74374103967});
p.push_back({(ll)884100000,(ll)74396597711});
p.push_back({(ll)884800000,(ll)74424116711});
p.push_back({(ll)885500000,(ll)74449951965});
p.push_back({(ll)886200000,(ll)74479474583});
p.push_back({(ll)886900000,(ll)74513284735});
p.push_back({(ll)887600000,(ll)74552082239});
p.push_back({(ll)888300000,(ll)74596427727});
p.push_back({(ll)889000000,(ll)74640924263});
p.push_back({(ll)889700000,(ll)74689041335});
p.push_back({(ll)890400000,(ll)74742584023});
p.push_back({(ll)891100000,(ll)74813955903});
p.push_back({(ll)891800000,(ll)74898075455});
p.push_back({(ll)892500000,(ll)74941092967});
p.push_back({(ll)893200000,(ll)74996528615});
p.push_back({(ll)893900000,(ll)75063254655});
p.push_back({(ll)894600000,(ll)75148361343});
p.push_back({(ll)895300000,(ll)75183235431});
p.push_back({(ll)896000000,(ll)75213092767});
p.push_back({(ll)896700000,(ll)75246544799});
p.push_back({(ll)897400000,(ll)75283855319});
p.push_back({(ll)898100000,(ll)75329740239});
p.push_back({(ll)898800000,(ll)75372170415});
p.push_back({(ll)899500000,(ll)75430920095});
p.push_back({(ll)900200000,(ll)75455990959});
p.push_back({(ll)900900000,(ll)75485610911});
p.push_back({(ll)901600000,(ll)75519790383});
p.push_back({(ll)902300000,(ll)75560046015});
p.push_back({(ll)903000000,(ll)75602432335});
p.push_back({(ll)903700000,(ll)75650481535});
p.push_back({(ll)904400000,(ll)75705024127});
p.push_back({(ll)905100000,(ll)75766285799});
p.push_back({(ll)905800000,(ll)75836528591});
p.push_back({(ll)906500000,(ll)75936105935});
p.push_back({(ll)907200000,(ll)76005298903});
p.push_back({(ll)907900000,(ll)76070380903});
p.push_back({(ll)908600000,(ll)76152270655});
p.push_back({(ll)909300000,(ll)76240224915});
p.push_back({(ll)910000000,(ll)76270413799});
p.push_back({(ll)910700000,(ll)76301027287});
p.push_back({(ll)911400000,(ll)76336864207});
p.push_back({(ll)912100000,(ll)76374183215});
p.push_back({(ll)912800000,(ll)76416671647});
p.push_back({(ll)913500000,(ll)76471174607});
p.push_back({(ll)914200000,(ll)76511086543});
p.push_back({(ll)914900000,(ll)76542099687});
p.push_back({(ll)915600000,(ll)76573583335});
p.push_back({(ll)916300000,(ll)76609258983});
p.push_back({(ll)917000000,(ll)76646883247});
p.push_back({(ll)917700000,(ll)76692987711});
p.push_back({(ll)918400000,(ll)76745133919});
p.push_back({(ll)919100000,(ll)76806275559});
p.push_back({(ll)919800000,(ll)76863236023});
p.push_back({(ll)920500000,(ll)76944812975});
p.push_back({(ll)921200000,(ll)77045311463});
p.push_back({(ll)921900000,(ll)77100863167});
p.push_back({(ll)922600000,(ll)77175215007});
p.push_back({(ll)923300000,(ll)77267934655});
p.push_back({(ll)924000000,(ll)77315983067});
p.push_back({(ll)924700000,(ll)77330951771});
p.push_back({(ll)925400000,(ll)77347262415});
p.push_back({(ll)926100000,(ll)77361153755});
p.push_back({(ll)926800000,(ll)77379184431});
p.push_back({(ll)927500000,(ll)77399083423});
p.push_back({(ll)928200000,(ll)77420079055});
p.push_back({(ll)928900000,(ll)77444634527});
p.push_back({(ll)929600000,(ll)77465097055});
p.push_back({(ll)930300000,(ll)77487686095});
p.push_back({(ll)931000000,(ll)77514457039});
p.push_back({(ll)931700000,(ll)77548101487});
p.push_back({(ll)932400000,(ll)77579391335});
p.push_back({(ll)933100000,(ll)77591808295});
p.push_back({(ll)933800000,(ll)77609632499});
p.push_back({(ll)934500000,(ll)77621147111});
p.push_back({(ll)935200000,(ll)77637036267});
p.push_back({(ll)935900000,(ll)77656232911});
p.push_back({(ll)936600000,(ll)77680638743});
p.push_back({(ll)937300000,(ll)77699879379});
p.push_back({(ll)938000000,(ll)77721116591});
p.push_back({(ll)938700000,(ll)77747614559});
p.push_back({(ll)939400000,(ll)77767916383});
p.push_back({(ll)940100000,(ll)77798413359});
p.push_back({(ll)940800000,(ll)77832024855});
p.push_back({(ll)941500000,(ll)77861174819});
p.push_back({(ll)942200000,(ll)77889550951});
p.push_back({(ll)942900000,(ll)77923939815});
p.push_back({(ll)943600000,(ll)77968061879});
p.push_back({(ll)944300000,(ll)78016373935});
p.push_back({(ll)945000000,(ll)78069491615});
p.push_back({(ll)945700000,(ll)78122107479});
p.push_back({(ll)946400000,(ll)78152786579});
p.push_back({(ll)947100000,(ll)78184399335});
p.push_back({(ll)947800000,(ll)78224494511});
p.push_back({(ll)948500000,(ll)78270416703});
p.push_back({(ll)949200000,(ll)78320734127});
p.push_back({(ll)949900000,(ll)78384685415});
p.push_back({(ll)950600000,(ll)78397098447});
p.push_back({(ll)951300000,(ll)78414919143});
p.push_back({(ll)952000000,(ll)78426437335});
p.push_back({(ll)952700000,(ll)78442332915});
p.push_back({(ll)953400000,(ll)78461488959});
p.push_back({(ll)954100000,(ll)78485937751});
p.push_back({(ll)954800000,(ll)78505172895});
p.push_back({(ll)955500000,(ll)78526400415});
p.push_back({(ll)956200000,(ll)78552887135});
p.push_back({(ll)956900000,(ll)78573200223});
p.push_back({(ll)957600000,(ll)78603706967});
p.push_back({(ll)958300000,(ll)78637305263});
p.push_back({(ll)959000000,(ll)78658144371});
p.push_back({(ll)959700000,(ll)78673076695});
p.push_back({(ll)960400000,(ll)78689416167});
p.push_back({(ll)961100000,(ll)78703277651});
p.push_back({(ll)961800000,(ll)78721323075});
p.push_back({(ll)962500000,(ll)78741128087});
p.push_back({(ll)963200000,(ll)78762103207});
p.push_back({(ll)963900000,(ll)78786761519});
p.push_back({(ll)964600000,(ll)78807216731});
p.push_back({(ll)965300000,(ll)78829717359});
p.push_back({(ll)966000000,(ll)78856463719});
p.push_back({(ll)966700000,(ll)78890154959});
p.push_back({(ll)967400000,(ll)78922728091});
p.push_back({(ll)968100000,(ll)78953722995});
p.push_back({(ll)968800000,(ll)78979093943});
p.push_back({(ll)969500000,(ll)79022849855});
p.push_back({(ll)970200000,(ll)79062990655});
p.push_back({(ll)970900000,(ll)79110931223});
p.push_back({(ll)971600000,(ll)79178858303});
p.push_back({(ll)972300000,(ll)79210896575});
p.push_back({(ll)973000000,(ll)79239497535});
p.push_back({(ll)973700000,(ll)79277663191});
p.push_back({(ll)974400000,(ll)79323996775});
p.push_back({(ll)975100000,(ll)79366789039});
p.push_back({(ll)975800000,(ll)79429671855});
p.push_back({(ll)976500000,(ll)79463916939});
p.push_back({(ll)977200000,(ll)79484710815});
p.push_back({(ll)977900000,(ll)79501255911});
p.push_back({(ll)978600000,(ll)79524576207});
p.push_back({(ll)979300000,(ll)79547770207});
p.push_back({(ll)980000000,(ll)79575666591});
p.push_back({(ll)980700000,(ll)79600621519});
p.push_back({(ll)981400000,(ll)79629731355});
p.push_back({(ll)982100000,(ll)79660889051});
p.push_back({(ll)982800000,(ll)79698593071});
p.push_back({(ll)983500000,(ll)79730024851});
p.push_back({(ll)984200000,(ll)79748136575});
p.push_back({(ll)984900000,(ll)79765639087});
p.push_back({(ll)985600000,(ll)79785737951});
p.push_back({(ll)986300000,(ll)79811437015});
p.push_back({(ll)987000000,(ll)79836787175});
p.push_back({(ll)987700000,(ll)79864630507});
p.push_back({(ll)988400000,(ll)79895037515});
p.push_back({(ll)989100000,(ll)79920871595});
p.push_back({(ll)989800000,(ll)79961902943});
p.push_back({(ll)990500000,(ll)79998256615});
p.push_back({(ll)991200000,(ll)80032868071});
p.push_back({(ll)991900000,(ll)80074578863});
p.push_back({(ll)992600000,(ll)80130486191});
p.push_back({(ll)993300000,(ll)80184837307});
p.push_back({(ll)994000000,(ll)80264542827});
p.push_back({(ll)994700000,(ll)80299108327});
p.push_back({(ll)995400000,(ll)80335971815});
p.push_back({(ll)996100000,(ll)80393573303});
p.push_back({(ll)996800000,(ll)80447081659});
p.push_back({(ll)997500000,(ll)80530754463});
p.push_back({(ll)998200000,(ll)80545686771});
p.push_back({(ll)998900000,(ll)80566374887});
p.push_back({(ll)999600000,(ll)80583090907});
p.push_back({(ll)1000300000,(ll)80604050919});
p.push_back({(ll)1001000000,(ll)80633505767});
p.push_back({(ll)1001700000,(ll)80658841503});
p.push_back({(ll)1002400000,(ll)80685671039});
p.push_back({(ll)1003100000,(ll)80713289647});
p.push_back({(ll)1003800000,(ll)80746962847});
p.push_back({(ll)1004500000,(ll)80787023807});
p.push_back({(ll)1005200000,(ll)80808017823});
p.push_back({(ll)1005900000,(ll)80832130783});
p.push_back({(ll)1006600000,(ll)80847089615});
p.push_back({(ll)1007300000,(ll)80868771815});
p.push_back({(ll)1008000000,(ll)80895696319});
p.push_back({(ll)1008700000,(ll)80920820943});
p.push_back({(ll)1009400000,(ll)80948215727});
p.push_back({(ll)1010100000,(ll)80973967311});
p.push_back({(ll)1010800000,(ll)81006150991});
p.push_back({(ll)1011500000,(ll)81046478319});
p.push_back({(ll)1012200000,(ll)81083619255});
p.push_back({(ll)1012900000,(ll)81119174463});
p.push_back({(ll)1013600000,(ll)81169927999});
p.push_back({(ll)1014300000,(ll)81221275455});
p.push_back({(ll)1015000000,(ll)81285908383});
p.push_back({(ll)1015700000,(ll)81346437039});
p.push_back({(ll)1016400000,(ll)81382514607});
p.push_back({(ll)1017100000,(ll)81430398903});
p.push_back({(ll)1017800000,(ll)81482718959});
p.push_back({(ll)1018500000,(ll)81543598543});
p.push_back({(ll)1019200000,(ll)81609646311});
p.push_back({(ll)1019900000,(ll)81635923671});
p.push_back({(ll)1020600000,(ll)81657603667});
p.push_back({(ll)1021300000,(ll)81685318575});
p.push_back({(ll)1022000000,(ll)81715792999});
p.push_back({(ll)1022700000,(ll)81748670415});
p.push_back({(ll)1023400000,(ll)81787178191});
p.push_back({(ll)1024100000,(ll)81831910847});
p.push_back({(ll)1024800000,(ll)81875713999});
p.push_back({(ll)1025500000,(ll)81898737343});
p.push_back({(ll)1026200000,(ll)81923151579});
p.push_back({(ll)1026900000,(ll)81949005743});
p.push_back({(ll)1027600000,(ll)81979981743});
p.push_back({(ll)1028300000,(ll)82012298447});
p.push_back({(ll)1029000000,(ll)82049443759});
p.push_back({(ll)1029700000,(ll)82092586847});
p.push_back({(ll)1030400000,(ll)82142435623});
p.push_back({(ll)1031100000,(ll)82184270951});
p.push_back({(ll)1031800000,(ll)82242002279});
p.push_back({(ll)1032500000,(ll)82305474239});
p.push_back({(ll)1033200000,(ll)82387804015});
p.push_back({(ll)1033900000,(ll)82444858319});
p.push_back({(ll)1034600000,(ll)82491869159});
p.push_back({(ll)1035300000,(ll)82552566703});
p.push_back({(ll)1036000000,(ll)82634098263});
p.push_back({(ll)1036700000,(ll)82687826215});
p.push_back({(ll)1037400000,(ll)82714162279});
p.push_back({(ll)1038100000,(ll)82737170727});
p.push_back({(ll)1038800000,(ll)82766539351});
p.push_back({(ll)1039500000,(ll)82796905767});
p.push_back({(ll)1040200000,(ll)82831777183});
p.push_back({(ll)1040900000,(ll)82869376599});
p.push_back({(ll)1041600000,(ll)82917435343});
p.push_back({(ll)1042300000,(ll)82953032999});
p.push_back({(ll)1043000000,(ll)82980493775});
p.push_back({(ll)1043700000,(ll)83001694623});
p.push_back({(ll)1044400000,(ll)83030594903});
p.push_back({(ll)1045100000,(ll)83060709279});
p.push_back({(ll)1045800000,(ll)83094355887});
p.push_back({(ll)1046500000,(ll)83132330191});
p.push_back({(ll)1047200000,(ll)83180426703});
p.push_back({(ll)1047900000,(ll)83223381991});
p.push_back({(ll)1048600000,(ll)83269611735});
p.push_back({(ll)1049300000,(ll)83323914023});
p.push_back({(ll)1050000000,(ll)83392503535});
p.push_back({(ll)1050700000,(ll)83484476647});
p.push_back({(ll)1051400000,(ll)83525841383});
p.push_back({(ll)1052100000,(ll)83583655743});
p.push_back({(ll)1052800000,(ll)83646740223});
p.push_back({(ll)1053500000,(ll)83728539503});
p.push_back({(ll)1054200000,(ll)83772399519});
p.push_back({(ll)1054900000,(ll)83802644951});
p.push_back({(ll)1055600000,(ll)83837134055});
p.push_back({(ll)1056300000,(ll)83874982783});
p.push_back({(ll)1057000000,(ll)83921483727});
p.push_back({(ll)1057700000,(ll)83970315167});
p.push_back({(ll)1058400000,(ll)84023295951});
p.push_back({(ll)1059100000,(ll)84054679887});
p.push_back({(ll)1059800000,(ll)84084207295});
p.push_back({(ll)1060500000,(ll)84122301399});
p.push_back({(ll)1061200000,(ll)84159598031});
p.push_back({(ll)1061900000,(ll)84205689759});
p.push_back({(ll)1062600000,(ll)84260171727});
p.push_back({(ll)1063300000,(ll)84319084223});
p.push_back({(ll)1064000000,(ll)84377263935});
p.push_back({(ll)1064700000,(ll)84458907599});
p.push_back({(ll)1065400000,(ll)84560093103});
p.push_back({(ll)1066100000,(ll)84613996351});
p.push_back({(ll)1066800000,(ll)84684387063});
p.push_back({(ll)1067500000,(ll)84779803551});
p.push_back({(ll)1068200000,(ll)84841469415});
p.push_back({(ll)1068900000,(ll)84869415887});
p.push_back({(ll)1069600000,(ll)84903239631});
p.push_back({(ll)1070300000,(ll)84943406311});
p.push_back({(ll)1071000000,(ll)84985819039});
p.push_back({(ll)1071700000,(ll)85032877935});
p.push_back({(ll)1072400000,(ll)85094306963});
p.push_back({(ll)1073100000,(ll)85121157023});
p.push_back({(ll)1073800000,(ll)85149994911});
p.push_back({(ll)1074500000,(ll)85187707863});

    for (ll i = 1; i < maxnum; i ++)
        for (ll j = 1; j < maxnum; j ++)
            gcd[i][j] = __gcd(i, j);
}
void preprocess(ll n)
{
    ///freopen("text.txt", "w", stdout);



    ll i = 0;
    while(p[i].first <= n)
        i ++;
    i --;

    ll mask = p[i].second, x, idx = p[i].first;
    if (idx == n)
    {
        vector < ll > num;
        for (ll bit = 0; ((ll)1 << bit) <= mask; bit ++)
            if ((mask & ((ll)1 << bit)))
                num.push_back(bit + 1);

        cout << num.size() << " ";
        for (int v : num)
            cout << v << " ";
        cout << endl;
        return;

    }
    mask ++;
    while(true)
    {

        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;
            }*/idx ++;
            if (idx == n)
            {
                cout << num.size() << " ";
                for (int v : num)
                    cout << v << " ";
                cout << endl;
                return;
            }
            mask ++;

        }
        else
            mask = (mask | ((ll)1 << (atl - 1)));

    }
    ///cout << "Done " << mask << endl;
    ///exit(0);
}

void solve()
{
    ll n;
    cin >> n;
    preprocess(n);


}

int main()
{
    precompute();
    ll t;
    cin >> t;
    while(t --)
        solve();
    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 21 / 21
• Subtask 3: 41 / 41
• Subtask 4: 14 / 14
• Subtask 5: 0 / 16