/**
____ ____ ____ ____ ____ ____
||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, cst = 6e5;
vector < vector < ll > > st;
ll gcd[maxnum][maxnum];
vector < ll > p;
void precompute()
{
p.push_back(0);
p.push_back(7643727);
p.push_back(20668351);
p.push_back(35071943);
p.push_back(44906027);
p.push_back(58218911);
p.push_back(73695511);
p.push_back(90883007);
p.push_back(108370527);
p.push_back(128785343);
p.push_back(145427647);
p.push_back(168107103);
p.push_back(184863615);
p.push_back(207106943);
p.push_back(236979263);
p.push_back(265554303);
p.push_back(275592539);
p.push_back(288318007);
p.push_back(303039351);
p.push_back(312743531);
p.push_back(325960347);
p.push_back(341606511);
p.push_back(358670175);
p.push_back(376189899);
p.push_back(395659831);
p.push_back(413083375);
p.push_back(435967711);
p.push_back(452237039);
p.push_back(474584431);
p.push_back(504128351);
p.push_back(531634543);
p.push_back(553927967);
p.push_back(577933495);
p.push_back(607232599);
p.push_back(642583407);
p.push_back(678626151);
p.push_back(719357115);
p.push_back(774977399);
p.push_back(813178735);
p.push_back(841167287);
p.push_back(863457079);
p.push_back(897852279);
p.push_back(938045119);
p.push_back(975984479);
p.push_back(1019875183);
p.push_back(1075004959);
p.push_back(1084053725);
p.push_back(1096823047);
p.push_back(1110536799);
p.push_back(1122047951);
p.push_back(1136479039);
p.push_back(1150489071);
p.push_back(1170214751);
p.push_back(1186284879);
p.push_back(1208226819);
p.push_back(1223833215);
p.push_back(1244387135);
p.push_back(1262689391);
p.push_back(1285917599);
p.push_back(1314653023);
p.push_back(1343045023);
p.push_back(1351681871);
p.push_back(1364478815);
p.push_back(1378557103);
p.push_back(1389577023);
p.push_back(1403603775);
p.push_back(1418012111);
p.push_back(1436916127);
p.push_back(1453688783);
p.push_back(1475894079);
p.push_back(1491402959);
p.push_back(1512386663);
p.push_back(1529950287);
p.push_back(1552752543);
p.push_back(1581908751);
p.push_back(1611914303);
p.push_back(1633040511);
p.push_back(1657087207);
p.push_back(1685763967);
p.push_back(1722827951);
p.push_back(1761883295);
p.push_back(1801818271);
p.push_back(1860178751);
p.push_back(1892511359);
p.push_back(1918114351);
p.push_back(1946481871);
p.push_back(1981900447);
p.push_back(2017752447);
p.push_back(2055447727);
p.push_back(2109943167);
p.push_back(2150901447);
p.push_back(2165312383);
p.push_back(2182679743);
p.push_back(2196293375);
p.push_back(2215388111);
p.push_back(2234282879);
p.push_back(2255248255);
p.push_back(2282366719);
p.push_back(2302090239);
p.push_back(2323493375);
p.push_back(2351859151);
p.push_back(2385289935);
p.push_back(2417267983);
p.push_back(2429624543);
p.push_back(2448281855);
p.push_back(2459301631);
p.push_back(2477879551);
p.push_back(2497977535);
p.push_back(2520819775);
p.push_back(2542891263);
p.push_back(2565647071);
p.push_back(2588541535);
p.push_back(2614886911);
p.push_back(2646247423);
p.push_back(2681995775);
p.push_back(2708542783);
p.push_back(2739196351);
p.push_back(2785342879);
p.push_back(2825724575);
p.push_back(2875599615);
p.push_back(2952562687);
p.push_back(2978277887);
p.push_back(3008541951);
p.push_back(3054609759);
p.push_back(3095576831);
p.push_back(3146055935);
p.push_back(3221366479);
p.push_back(3231295743);
p.push_back(3248500479);
p.push_back(3262015743);
p.push_back(3278828671);
p.push_back(3298076927);
p.push_back(3323990031);
p.push_back(3344193663);
p.push_back(3365944031);
p.push_back(3391663775);
p.push_back(3412909183);
p.push_back(3444349343);
p.push_back(3478769919);
p.push_back(3496444175);
p.push_back(3512710399);
p.push_back(3528373983);
p.push_back(3544397599);
p.push_back(3562606623);
p.push_back(3586819071);
p.push_back(3608216127);
p.push_back(3629986687);
p.push_back(3656620031);
p.push_back(3676855423);
p.push_back(3705989887);
p.push_back(3739951615);
p.push_back(3769636031);
p.push_back(3799294815);
p.push_back(3836036543);
p.push_back(3882707711);
p.push_back(3931024255);
p.push_back(3995414591);
p.push_back(4039477439);
p.push_back(4068685551);
p.push_back(4106691007);
p.push_back(4153263103);
p.push_back(4200697887);
p.push_back(4265465599);
p.push_back(4303357221);
p.push_back(4324619927);
p.push_back(4342780815);
p.push_back(4366336021);
p.push_back(4389606887);
p.push_back(4414457623);
p.push_back(4442693807);
p.push_back(4474012751);
p.push_back(4509471567);
p.push_back(4549629087);
p.push_back(4573177959);
p.push_back(4596249671);
p.push_back(4614042983);
p.push_back(4635889943);
p.push_back(4661775263);
p.push_back(4685839775);
p.push_back(4714862359);
p.push_back(4746253487);
p.push_back(4782101407);
p.push_back(4822429535);
p.push_back(4862532917);
p.push_back(4901338999);
p.push_back(4947543783);
p.push_back(5007476431);
p.push_back(5084186431);
p.push_back(5131179447);
p.push_back(5169866327);
p.push_back(5216671591);
p.push_back(5276502191);
p.push_back(5353046239);
p.push_back(5381556535);
p.push_back(5403154511);
p.push_back(5421278695);
p.push_back(5443491463);
p.push_back(5470232615);
p.push_back(5494618711);
p.push_back(5523990103);
p.push_back(5555339615);
p.push_back(5591774623);
p.push_back(5634729343);
p.push_back(5651659103);
p.push_back(5672912167);
p.push_back(5692072999);
p.push_back(5713991855);
p.push_back(5740488351);
p.push_back(5767257175);
p.push_back(5794887327);
p.push_back(5826908319);
p.push_back(5864766927);
p.push_back(5906739303);
p.push_back(5943499439);
p.push_back(5982462183);
p.push_back(6034755007);
p.push_back(6095918943);
p.push_back(6175262695);
p.push_back(6212009647);
p.push_back(6251107135);
p.push_back(6304068279);
p.push_back(6364922967);
p.push_back(6443149487);
p.push_back(6464221279);
p.push_back(6489526975);
p.push_back(6516168535);
p.push_back(6548455975);
p.push_back(6581946063);
p.push_back(6618878159);
p.push_back(6663149343);
p.push_back(6711830847);
p.push_back(6732977511);
p.push_back(6758474215);
p.push_back(6785154639);
p.push_back(6817154343);
p.push_back(6850822351);
p.push_back(6887903439);
p.push_back(6933022047);
p.push_back(6981912167);
p.push_back(7028516783);
p.push_back(7085106095);
p.push_back(7155491247);
p.push_back(7249155239);
p.push_back(7294153191);
p.push_back(7352660007);
p.push_back(7421137103);
p.push_back(7516489157);
p.push_back(7537358423);
p.push_back(7561742311);
p.push_back(7588926661);
p.push_back(7621435687);
p.push_back(7655064655);
p.push_back(7690792271);
p.push_back(7734990239);
p.push_back(7785043367);
p.push_back(7805967407);
p.push_back(7831003367);
p.push_back(7857773391);
p.push_back(7890155951);
p.push_back(7923732559);
p.push_back(7959786703);
p.push_back(8004056527);
p.push_back(8054412711);
p.push_back(8099337447);
p.push_back(8157930023);
p.push_back(8226312559);
p.push_back(8321901671);
p.push_back(8364443327);
p.push_back(8424285607);
p.push_back(8493566127);
p.push_back(8588431039);
p.push_back(8598342743);
p.push_back(8611893435);
p.push_back(8626381643);
p.push_back(8637451095);
p.push_back(8651627103);
p.push_back(8667279983);
p.push_back(8688867503);
p.push_back(8704706423);
p.push_back(8725708911);
p.push_back(8743205051);
p.push_back(8762855883);
p.push_back(8782087519);
p.push_back(8808862783);
p.push_back(8837475631);
p.push_back(8861488731);
p.push_back(8872925807);
p.push_back(8887037407);
p.push_back(8898470711);
p.push_back(8911357407);
p.push_back(8927631967);
p.push_back(8944095287);
p.push_back(8963456359);
p.push_back(8980887263);
p.push_back(8999403675);
p.push_back(9020668511);
p.push_back(9039001115);
p.push_back(9062197019);
p.push_back(9092082111);
p.push_back(9118012639);
p.push_back(9142144763);
p.push_back(9167042487);
p.push_back(9196275671);
p.push_back(9231959255);
p.push_back(9267837039);
p.push_back(9307697851);
p.push_back(9364077679);
p.push_back(9402927159);
p.push_back(9431166447);
p.push_back(9453815647);
p.push_back(9489765751);
p.push_back(9529585007);
p.push_back(9567025007);
p.push_back(9611970415);
p.push_back(9665545755);
p.push_back(9675461815);
p.push_back(9688873847);
p.push_back(9702158443);
p.push_back(9714555743);
p.push_back(9730827995);
p.push_back(9745990831);
p.push_back(9766623031);
p.push_back(9783294999);
p.push_back(9802536799);
p.push_back(9821357291);
p.push_back(9840232635);
p.push_back(9863766879);
p.push_back(9889446623);
p.push_back(9918340447);
p.push_back(9937293167);
p.push_back(9949810111);
p.push_back(9965832379);
p.push_back(9974423195);
p.push_back(9988211903);
p.push_back(10004211063);
p.push_back(10022304175);
p.push_back(10040136023);
p.push_back(10060122335);
p.push_back(10077691231);
p.push_back(10100689759);
p.push_back(10117752143);
p.push_back(10140536159);
p.push_back(10171258699);
p.push_back(10201038135);
p.push_back(10222493375);
p.push_back(10246819311);
p.push_back(10275443191);
p.push_back(10312986607);
p.push_back(10351936635);
p.push_back(10391938715);
p.push_back(10450380143);
p.push_back(10483173103);
p.push_back(10508883035);
p.push_back(10537391543);
p.push_back(10573091543);
p.push_back(10609496283);
p.push_back(10647890879);
p.push_back(10704451423);
p.push_back(10741758139);
p.push_back(10756907675);
p.push_back(10774052543);
p.push_back(10788999639);
p.push_back(10807711575);
p.push_back(10828733791);
p.push_back(10852474351);
p.push_back(10876116143);
p.push_back(10900703999);
p.push_back(10922915167);
p.push_back(10951434671);
p.push_back(10986558191);
p.push_back(11010688863);
p.push_back(11026732383);
p.push_back(11043471535);
p.push_back(11058581979);
p.push_back(11077342487);
p.push_back(11100281567);
p.push_back(11123405779);
p.push_back(11145377503);
p.push_back(11173235455);
p.push_back(11193121119);
p.push_back(11224007007);
p.push_back(11258228159);
p.push_back(11288286903);
p.push_back(11317367543);
p.push_back(11356226551);
p.push_back(11403609847);
p.push_back(11448734127);
p.push_back(11513754031);
p.push_back(11557948351);
p.push_back(11587143415);
p.push_back(11626710199);
p.push_back(11675908863);
p.push_back(11718075119);
p.push_back(11783934127);
p.push_back(11817590827);
p.push_back(11833844447);
p.push_back(11849883999);
p.push_back(11865904311);
p.push_back(11884666935);
p.push_back(11911941551);
p.push_back(11931408223);
p.push_back(11952689819);
p.push_back(11980780235);
p.push_back(12001553631);
p.push_back(12033602891);
p.push_back(12067877787);
p.push_back(12086552347);
p.push_back(12103210463);
p.push_back(12119355759);
p.push_back(12135312255);
p.push_back(12154097751);
p.push_back(12181380271);
p.push_back(12201545911);
p.push_back(12223103711);
p.push_back(12250122011);
p.push_back(12271432443);
p.push_back(12304374111);
p.push_back(12338877151);
p.push_back(12369359799);
p.push_back(12400395967);
p.push_back(12440366527);
p.push_back(12486852975);
p.push_back(12535002591);
p.push_back(12604249439);
p.push_back(12638793087);
p.push_back(12669348543);
p.push_back(12712479679);
p.push_back(12756237039);
p.push_back(12805235775);
p.push_back(12874909119);
p.push_back(12900706263);
p.push_back(12922715999);
p.push_back(12941632731);
p.push_back(12966125367);
p.push_back(12992489007);
p.push_back(13021337439);
p.push_back(13053988207);
p.push_back(13087192495);
p.push_back(13126100703);
p.push_back(13158688727);
p.push_back(13179646327);
p.push_back(13199765719);
p.push_back(13223142679);
p.push_back(13249903839);
p.push_back(13274717791);
p.push_back(13304598647);
p.push_back(13336579247);
p.push_back(13373826935);
p.push_back(13416318687);
p.push_back(13456327615);
p.push_back(13494250367);
p.push_back(13543756983);
p.push_back(13605736175);
p.push_back(13686442943);
p.push_back(13725940975);
p.push_back(13764662999);
p.push_back(13815076023);
p.push_back(13877436095);
p.push_back(13958894039);
p.push_back(13976383839);
p.push_back(13997338303);
p.push_back(14017991391);
p.push_back(14042954103);
p.push_back(14068698559);
p.push_back(14097471351);
p.push_back(14130652875);
p.push_back(14164338095);
p.push_back(14203379055);
p.push_back(14233757623);
p.push_back(14256890615);
p.push_back(14275454647);
p.push_back(14298898711);
p.push_back(14327772631);
p.push_back(14350442871);
p.push_back(14381125311);
p.push_back(14413354719);
p.push_back(14451619639);
p.push_back(14495776855);
p.push_back(14532652527);
p.push_back(14571760575);
p.push_back(14623901559);
p.push_back(14685594079);
p.push_back(14765183287);
p.push_back(14802171831);
p.push_back(14843737719);
p.push_back(14898196567);
p.push_back(14959218111);
p.push_back(15033733975);
p.push_back(15056786871);
p.push_back(15083413855);
p.push_back(15112391855);
p.push_back(15145389791);
p.push_back(15181444335);
p.push_back(15220500191);
p.push_back(15269214575);
p.push_back(15306397271);
p.push_back(15335416159);
p.push_back(15357805787);
p.push_back(15389955767);
p.push_back(15423029599);
p.push_back(15460508079);
p.push_back(15502795103);
p.push_back(15549427183);
p.push_back(15601130943);
p.push_back(15647231215);
p.push_back(15711020783);
p.push_back(15800288703);
p.push_back(15864421823);
p.push_back(15912502295);
p.push_back(15977245567);
p.push_back(16061328767);
p.push_back(16115925463);
p.push_back(16144049751);
p.push_back(16172398327);
p.push_back(16204396031);
p.push_back(16237027039);
p.push_back(16275323247);
p.push_back(16313908719);
p.push_back(16364127583);
p.push_back(16393013599);
p.push_back(16417065391);
p.push_back(16446574015);
p.push_back(16479854935);
p.push_back(16513652063);
p.push_back(16551114463);
p.push_back(16597228383);
p.push_back(16647210327);
p.push_back(16693756279);
p.push_back(16749529007);
p.push_back(16822021871);
p.push_back(16913806679);
p.push_back(16959731191);
p.push_back(17016787383);
p.push_back(17086594799);
p.push_back(17180583423);
p.push_back(17201135799);
p.push_back(17223452031);
p.push_back(17249537919);
p.push_back(17281708767);
p.push_back(17315836031);
p.push_back(17353729151);
p.push_back(17400334975);
p.push_back(17450757215);
p.push_back(17471518687);
p.push_back(17494856639);
p.push_back(17520334719);
p.push_back(17552952447);
p.push_back(17587160703);
p.push_back(17625803903);
p.push_back(17673534591);
p.push_back(17727659007);
p.push_back(17773709151);
p.push_back(17839475455);
p.push_back(17924380255);
p.push_back(18007070591);
p.push_back(18055828863);
p.push_back(18125935359);
p.push_back(18223254271);
p.push_back(18268358959);
p.push_back(18291150207);
p.push_back(18313970047);
p.push_back(18343806943);
p.push_back(18377175935);
p.push_back(18415096031);
p.push_back(18457464319);
p.push_back(18511959519);
p.push_back(18539229527);
p.push_back(18561134815);
p.push_back(18585967999);
p.push_back(18615443327);
p.push_back(18649014495);
p.push_back(18689579391);
p.push_back(18730052991);
p.push_back(18787875199);
p.push_back(18832625151);
p.push_back(18892461535);
p.push_back(18969141759);
p.push_back(19065803287);
p.push_back(19113489887);
p.push_back(19177668831);
p.push_back(19259368959);
p.push_back(19334926575);
p.push_back(19365217119);
p.push_back(19396563143);
p.push_back(19434414535);
p.push_back(19480343935);
p.push_back(19530167167);
p.push_back(19596123615);
p.push_back(19620312799);
p.push_back(19650533215);
p.push_back(19686110039);
p.push_back(19730833279);
p.push_back(19776378879);
p.push_back(19836000639);
p.push_back(19899357055);
p.push_back(19969118303);
p.push_back(20068050431);
p.push_back(20165247743);
p.push_back(20234127039);
p.push_back(20328679423);
p.push_back(20411450879);
p.push_back(20440117983);
p.push_back(20472211839);
p.push_back(20510419423);
p.push_back(20556671871);
p.push_back(20607169919);
p.push_back(20671141085);
p.push_back(20697394399);
p.push_back(20725924095);
p.push_back(20762698495);
p.push_back(20806829407);
p.push_back(20854869887);
p.push_back(20913802239);
p.push_back(20976010079);
p.push_back(21047215039);
p.push_back(21152320511);
p.push_back(21242319415);
p.push_back(21312099007);
p.push_back(21412197759);
p.push_back(21492954847);
p.push_back(21529663039);
p.push_back(21572618327);
p.push_back(21622781311);
p.push_back(21686391903);
p.push_back(21750544255);
p.push_back(21786331247);
p.push_back(21827788479);
p.push_back(21875218815);
p.push_back(21934466303);
p.push_back(22012086655);
p.push_back(22084147319);
p.push_back(22189323007);
p.push_back(22308722303);
p.push_back(22389540543);
p.push_back(22519441919);
p.push_back(22574601919);
p.push_back(22613549823);
p.push_back(22656079295);
p.push_back(22711078399);
p.push_back(22779614303);
p.push_back(22834112095);
p.push_back(22869852023);
p.push_back(22911876983);
p.push_back(22961047775);
p.push_back(23024741855);
p.push_back(23102687167);
p.push_back(23179388671);
p.push_back(23296226047);
p.push_back(23400231807);
p.push_back(23488256767);
p.push_back(23623542495);
p.push_back(23666143999);
p.push_back(23721247967);
p.push_back(23785916639);
p.push_back(23869792735);
p.push_back(23925016959);
p.push_back(23974711519);
p.push_back(24032933247);
p.push_back(24113346943);
p.push_back(24206590719);
p.push_back(24325822463);
p.push_back(24465494623);
p.push_back(24578951935);
p.push_back(24707682047);
p.push_back(24752723007);
p.push_back(24809800639);
p.push_back(24880933247);
p.push_back(24965914079);
p.push_back(25009104639);
p.push_back(25065161311);
p.push_back(25128967167);
p.push_back(25213018591);
p.push_back(25305097087);
p.push_back(25441416831);
p.push_back(25564357375);
p.push_back(25692226943);
p.push_back(25781689215);
p.push_back(25806313087);
p.push_back(25828707071);
p.push_back(25860440543);
p.push_back(25894291231);
p.push_back(25935621247);
p.push_back(25977223551);
p.push_back(26035929855);
p.push_back(26058974815);
p.push_back(26081608159);
p.push_back(26108200735);
p.push_back(26142013311);
p.push_back(26176749679);
p.push_back(26216490495);
p.push_back(26265852287);
p.push_back(26321356919);
p.push_back(26366586743);
p.push_back(26434067455);
p.push_back(26525017599);
p.push_back(26600483967);
p.push_back(26650956991);
p.push_back(26726300415);
p.push_back(26826516223);
p.push_back(26861983327);
p.push_back(26884229823);
p.push_back(26910917967);
p.push_back(26944561631);
p.push_back(26978684031);
p.push_back(27017613663);
p.push_back(27065309055);
p.push_back(27115330559);
p.push_back(27137772479);
p.push_back(27162621783);
p.push_back(27188789983);
p.push_back(27222868351);
p.push_back(27260170463);
p.push_back(27300793055);
p.push_back(27353422303);
p.push_back(27404577535);
p.push_back(27454675839);
p.push_back(27528881919);
p.push_back(27627251199);
p.push_back(27686712287);
p.push_back(27741913983);
p.push_back(27819697919);
p.push_back(27919131743);
p.push_back(27948065247);
p.push_back(27974633247);
p.push_back(28018050503);
p.push_back(28058170079);
p.push_back(28107584895);
p.push_back(28173705471);
p.push_back(28207481503);
p.push_back(28237988095);
p.push_back(28273854047);
p.push_back(28317266431);
p.push_back(28363408895);
p.push_back(28425429247);
p.push_back(28488860895);
p.push_back(28558240511);
p.push_back(28656918911);
p.push_back(28754219967);
p.push_back(28823532255);
p.push_back(28916704767);
p.push_back(29002012911);
p.push_back(29031109439);
p.push_back(29063613439);
p.push_back(29107161535);
p.push_back(29152301823);
p.push_back(29207301343);
p.push_back(29264087279);
p.push_back(29295157591);
p.push_back(29324587735);
p.push_back(29364588911);
p.push_back(29410670555);
p.push_back(29460656895);
p.push_back(29528360383);
p.push_back(29583839967);
p.push_back(29667363583);
p.push_back(29788005887);
p.push_back(29850121951);
p.push_back(29931844351);
p.push_back(30050621311);
p.push_back(30098629471);
p.push_back(30136417503);
p.push_back(30184063231);
p.push_back(30242570623);
p.push_back(30318100863);
p.push_back(30363183487);
p.push_back(30401645951);
p.push_back(30448869311);
p.push_back(30506468735);
p.push_back(30580254463);
p.push_back(30655803391);
p.push_back(30750435071);
p.push_back(30882795071);
p.push_back(30959843199);
p.push_back(31075350143);
p.push_back(31159750879);
p.push_back(31197040511);
p.push_back(31243921279);
p.push_back(31298332159);
p.push_back(31369462143);
p.push_back(31425143007);
p.push_back(31462399359);
p.push_back(31509196159);
p.push_back(31562372479);
p.push_back(31630399871);
p.push_back(31709135039);
p.push_back(31793130239);
p.push_back(31927117407);
p.push_back(32008424447);
p.push_back(32111726335);
p.push_back(32224940207);
p.push_back(32270675711);
p.push_back(32331045247);
p.push_back(32402618751);
p.push_back(32486259071);
p.push_back(32534443743);
p.push_back(32590210047);
p.push_back(32662857215);
p.push_back(32753675007);
p.push_back(32852506239);
p.push_back(33010607615);
p.push_back(33107842911);
p.push_back(33258917375);
p.push_back(33324171695);
p.push_back(33376339807);
p.push_back(33442472319);
p.push_back(33527238111);
p.push_back(33588646079);
p.push_back(33639080831);
p.push_back(33702350047);
p.push_back(33785967359);
p.push_back(33877627071);
p.push_back(34001178111);
p.push_back(34137645823);
p.push_back(34255398399);
p.push_back(34364143731);
p.push_back(34381899615);
p.push_back(34400216159);
p.push_back(34425080863);
p.push_back(34464673103);
p.push_back(34499267663);
p.push_back(34528270047);
p.push_back(34550704767);
p.push_back(34600986495);
p.push_back(34634627711);
p.push_back(34654370815);
p.push_back(34673126655);
p.push_back(34699125119);
p.push_back(34740055423);
p.push_back(34771197311);
p.push_back(34799815935);
p.push_back(34828515839);
p.push_back(34882655135);
p.push_back(34932431087);
p.push_back(34999995327);
p.push_back(35070990207);
p.push_back(35170096879);
p.push_back(35215819135);
p.push_back(35303170943);
p.push_back(35370322943);
p.push_back(35439579535);
p.push_back(35458484415);
p.push_back(35477531951);
p.push_back(35503482767);
p.push_back(35542645215);
p.push_back(35575566559);
p.push_back(35604313839);
p.push_back(35631471327);
p.push_back(35686302591);
p.push_back(35710373343);
p.push_back(35735599807);
p.push_back(35752469951);
p.push_back(35776713567);
p.push_back(35822832095);
p.push_back(35852654815);
p.push_back(35876062559);
p.push_back(35907937167);
p.push_back(35970425791);
p.push_back(36010442943);
p.push_back(36090167807);
p.push_back(36157003327);
p.push_back(36250061423);
p.push_back(36297311103);
p.push_back(36385381375);
p.push_back(36471868927);
p.push_back(36519869855);
p.push_back(36545178671);
p.push_back(36574443359);
p.push_back(36625210687);
p.push_back(36658585183);
p.push_back(36682138159);
p.push_back(36725809023);
p.push_back(36778616207);
p.push_back(36799770495);
p.push_back(36826782303);
p.push_back(36864617407);
p.push_back(36913260511);
p.push_back(36943762543);
p.push_back(36966848447);
p.push_back(37025693631);
p.push_back(37084169151);
p.push_back(37184705775);
p.push_back(37279543231);
p.push_back(37353367151);
p.push_back(37453765359);
p.push_back(37550567295);
p.push_back(37597585375);
p.push_back(37619588031);
p.push_back(37649969023);
p.push_back(37701784927);
p.push_back(37733889919);
p.push_back(37757743039);
p.push_back(37802927999);
p.push_back(37853503423);
p.push_back(37876960927);
p.push_back(37902012287);
p.push_back(37941270463);
p.push_back(37988148335);
p.push_back(38018229215);
p.push_back(38042351791);
p.push_back(38103709631);
p.push_back(38161341631);
p.push_back(38262652863);
p.push_back(38359377855);
p.push_back(38433430255);
p.push_back(38535266047);
p.push_back(38633815999);
p.push_back(38676745565);
p.push_back(38709236959);
p.push_back(38760763663);
p.push_back(38810355903);
p.push_back(38856951135);
p.push_back(38926796735);
p.push_back(38957930943);
p.push_back(38991469887);
p.push_back(39051710399);
p.push_back(39093724351);
p.push_back(39148482431);
p.push_back(39227450479);
p.push_back(39332288447);
p.push_back(39464367295);
p.push_back(39545166655);
p.push_back(39662227391);
p.push_back(39745327039);
p.push_back(39774694367);
p.push_back(39819931135);
p.push_back(39873253343);
p.push_back(39917245375);
p.push_back(39996895535);
p.push_back(40021384383);
p.push_back(40053058431);
p.push_back(40108105519);
p.push_back(40155718879);
p.push_back(40203319231);
p.push_back(40283049855);
p.push_back(40379563967);
p.push_back(40505380799);
p.push_back(40590647167);
p.push_back(40707186431);
p.push_back(40811270079);
p.push_back(40853708671);
p.push_back(40920629119);
p.push_back(40971517823);
p.push_back(41037108191);
p.push_back(41090033599);
p.push_back(41128134591);
p.push_back(41205446111);
p.push_back(41244796383);
p.push_back(41318874623);
p.push_back(41424174591);
p.push_back(41571286015);
p.push_back(41692937727);
p.push_back(41842411455);
p.push_back(41903275967);
p.push_back(41947518911);
p.push_back(42015230687);
p.push_back(42062378879);
p.push_back(42144891199);
p.push_back(42180526015);
p.push_back(42230677439);
p.push_back(42295471327);
p.push_back(42342035391);
p.push_back(42430541695);
p.push_back(42557812671);
p.push_back(42699167615);
p.push_back(42827230975);
p.push_back(42952192479);
p.push_back(42970437567);
p.push_back(42989524023);
p.push_back(43010828527);
p.push_back(43053548335);
p.push_back(43088987071);
p.push_back(43118373103);
p.push_back(43140871103);
p.push_back(43191910367);
p.push_back(43225294815);
p.push_back(43251228607);
p.push_back(43268321151);
p.push_back(43292803551);
p.push_back(43339941663);
p.push_back(43369764511);
p.push_back(43392994271);
p.push_back(43426660287);
p.push_back(43488965823);
p.push_back(43531614959);
p.push_back(43621362415);
p.push_back(43681767167);
p.push_back(43773993727);
p.push_back(43825613247);
p.push_back(43911519999);
p.push_back(44006866815);
p.push_back(44037155807);
p.push_back(44059408351);
p.push_back(44077436863);
p.push_back(44111423359);
p.push_back(44158200047);
p.push_back(44180427647);
p.push_back(44207978143);
p.push_back(44248118719);
p.push_back(44295486463);
p.push_back(44314041215);
p.push_back(44332525535);
p.push_back(44358078207);
p.push_back(44398271807);
p.push_back(44432820847);
p.push_back(44462212207);
p.push_back(44486953199);
p.push_back(44543785439);
p.push_back(44594959295);
p.push_back(44661899135);
p.push_back(44733505407);
p.push_back(44833210239);
p.push_back(44879156415);
p.push_back(44966444799);
p.push_back(45033303935);
p.push_back(45104316383);
p.push_back(45133501375);
p.push_back(45155426239);
p.push_back(45205786591);
p.push_back(45246320607);
p.push_back(45271687999);
p.push_back(45313794015);
p.push_back(45368543471);
p.push_back(45390778303);
p.push_back(45417734015);
p.push_back(45457538559);
p.push_back(45504524511);
p.push_back(45535569007);
p.push_back(45563510527);
p.push_back(45623633855);
p.push_back(45685002111);
p.push_back(45786314495);
p.push_back(45889649663);
p.push_back(45955126463);
p.push_back(46056439679);
p.push_back(46162181119);
p.push_back(46190701119);
p.push_back(46212196319);
p.push_back(46245790047);
p.push_back(46305841711);
p.push_back(46329159551);
p.push_back(46358773503);
p.push_back(46410966415);
p.push_back(46447405023);
p.push_back(46476448703);
p.push_back(46501895935);
p.push_back(46555279327);
p.push_back(46590768335);
p.push_back(46614550495);
p.push_back(46659815359);
p.push_back(46720576703);
p.push_back(46798389119);
p.push_back(46883807103);
p.push_back(46992628671);
p.push_back(47076880319);
p.push_back(47155997695);
p.push_back(47250782687);
p.push_back(47283596415);
p.push_back(47325502879);
p.push_back(47383915487);
p.push_back(47428714463);
p.push_back(47499783519);
p.push_back(47536452831);
p.push_back(47568849343);
p.push_back(47627026367);
p.push_back(47677542335);
p.push_back(47725166047);
p.push_back(47805947775);
p.push_back(47915933631);
p.push_back(48046964223);
p.push_back(48121477423);
p.push_back(48237805311);
p.push_back(48332299631);
p.push_back(48363621679);
p.push_back(48412348351);
p.push_back(48466878207);
p.push_back(48508972927);
p.push_back(48587938783);
p.push_back(48620848351);
p.push_back(48653967327);
p.push_back(48713699103);
p.push_back(48758788063);
p.push_back(48821764031);
p.push_back(48893984639);
p.push_back(49005137855);
p.push_back(49130872767);
p.push_back(49225559415);
p.push_back(49342513023);
p.push_back(49417185151);
p.push_back(49463275487);
p.push_back(49531835263);
p.push_back(49580779391);
p.push_back(49662114687);
p.push_back(49699178431);
p.push_back(49761558495);
p.push_back(49816692671);
p.push_back(49868842975);
p.push_back(49966017663);
p.push_back(50099175359);
p.push_back(50234639807);
p.push_back(50367753407);
p.push_back(50477702367);
p.push_back(50519048063);
p.push_back(50588897215);
p.push_back(50638343359);
p.push_back(50706616287);
p.push_back(50759622399);
p.push_back(50805650399);
p.push_back(50874099679);
p.push_back(50923088351);
p.push_back(51007424447);
p.push_back(51138122879);
p.push_back(51275980671);
p.push_back(51406700287);
p.push_back(51541851371);
p.push_back(51576028927);
p.push_back(51622121343);
p.push_back(51691693951);
p.push_back(51748439391);
p.push_back(51824870079);
p.push_back(51859771263);
p.push_back(51922714111);
p.push_back(51980478207);
p.push_back(52065970047);
p.push_back(52176443775);
p.push_back(52350541567);
p.push_back(52475132927);
p.push_back(52618309375);
p.push_back(52653214047);
p.push_back(52704100223);
p.push_back(52770596735);
p.push_back(52838573407);
p.push_back(52901717247);
p.push_back(52937102719);
p.push_back(53006083423);
p.push_back(53061097951);
p.push_back(53154766719);
p.push_back(53275049471);
p.push_back(53437756543);
p.push_back(53569715967);
p.push_back(53701426687);
p.push_back(53744024159);
p.push_back(53827703119);
p.push_back(53890686463);
p.push_back(53974567487);
p.push_back(54020880895);
p.push_back(54104886767);
p.push_back(54171343839);
p.push_back(54293438335);
p.push_back(54498914047);
p.push_back(54661668607);
p.push_back(54782186175);
p.push_back(54831669119);
p.push_back(54914405247);
p.push_back(54984954751);
p.push_back(55053375423);
p.push_back(55110450671);
p.push_back(55186669439);
p.push_back(55267982847);
p.push_back(55416781823);
p.push_back(55595830463);
p.push_back(55758946047);
p.push_back(55872995775);
p.push_back(55961648127);
p.push_back(56056501631);
p.push_back(56140507007);
p.push_back(56225783679);
p.push_back(56320585727);
p.push_back(56488913279);
p.push_back(56694574975);
p.push_back(56913185663);
p.push_back(56971050879);
p.push_back(57066971007);
p.push_back(57180975711);
p.push_back(57235166591);
p.push_back(57333169919);
p.push_back(57453215487);
p.push_back(57643450111);
p.push_back(57856638719);
p.push_back(58017616767);
p.push_back(58121888991);
p.push_back(58243284479);
p.push_back(58319466367);
p.push_back(58427834111);
p.push_back(58592894847);
p.push_back(58852810495);
p.push_back(59075837823);
p.push_back(59174769535);
p.push_back(59279288191);
p.push_back(59375789951);
p.push_back(59482644351);
p.push_back(59627249535);
p.push_back(59885633279);
p.push_back(60132195199);
p.push_back(60167692407);
p.push_back(60218018303);
p.push_back(60286119807);
p.push_back(60354608639);
p.push_back(60419229791);
p.push_back(60454945727);
p.push_back(60532634847);
p.push_back(60584859263);
p.push_back(60683604543);
p.push_back(60812246783);
p.push_back(60966670079);
p.push_back(61104586495);
p.push_back(61221057023);
p.push_back(61256829535);
p.push_back(61325321079);
p.push_back(61381029759);
p.push_back(61473210111);
p.push_back(61508620367);
p.push_back(61557008895);
p.push_back(61626228607);
p.push_back(61692321279);
p.push_back(61792766847);
p.push_back(61943217151);
p.push_back(62078071807);
p.push_back(62262180863);
p.push_back(62315765631);
p.push_back(62386066303);
p.push_back(62452678527);
p.push_back(62548877183);
p.push_back(62596073919);
p.push_back(62679822719);
p.push_back(62734728959);
p.push_back(62849994623);
p.push_back(63021054975);
p.push_back(63206608767);
p.push_back(63358611679);
p.push_back(63406173055);
p.push_back(63490680703);
p.push_back(63554158079);
p.push_back(63638944991);
p.push_back(63687795167);
p.push_back(63772471807);
p.push_back(63843866587);
p.push_back(63978250111);
p.push_back(64175289471);
p.push_back(64338630911);
p.push_back(64461206911);
p.push_back(64548185983);
p.push_back(64646926207);
p.push_back(64731875583);
p.push_back(64827719551);
p.push_back(64928502655);
p.push_back(65103396607);
p.push_back(65308938239);
p.push_back(65513246655);
p.push_back(65579872127);
p.push_back(65675255551);
p.push_back(65785106303);
p.push_back(65855189343);
p.push_back(65952196479);
p.push_back(66090094463);
p.push_back(66324728383);
p.push_back(66538946047);
p.push_back(66637090751);
p.push_back(66748202751);
p.push_back(66865397631);
p.push_back(66975965055);
p.push_back(67093134847);
p.push_back(67327475199);
p.push_back(67579608063);
p.push_back(67702124415);
p.push_back(67818166655);
p.push_back(67935717311);
p.push_back(68038033279);
p.push_back(68153368447);
p.push_back(68373413631);
p.push_back(68636942079);
p.push_back(68725445583);
p.push_back(68737441655);
p.push_back(68752887711);
p.push_back(68761453811);
p.push_back(68775027803);
p.push_back(68790868445);
p.push_back(68806902183);
p.push_back(68825192911);
p.push_back(68843278659);
p.push_back(68860810031);
p.push_back(68881442623);
p.push_back(68899839211);
p.push_back(68922963151);
p.push_back(68949449167);
p.push_back(68976665823);
p.push_back(68993418393);
p.push_back(69005303963);
p.push_back(69019997403);
p.push_back(69029238439);
p.push_back(69042869047);
p.push_back(69058616751);
p.push_back(69074458207);
p.push_back(69093102483);
p.push_back(69110682645);
p.push_back(69128795243);
p.push_back(69148187387);
p.push_back(69166809039);
p.push_back(69190193071);
p.push_back(69215579871);
p.push_back(69243962203);
p.push_back(69267822187);
p.push_back(69294326387);
p.push_back(69320941247);
p.push_back(69357323495);
p.push_back(69393048751);
p.push_back(69430636975);
p.push_back(69480050303);
p.push_back(69529424103);
p.push_back(69556343735);
p.push_back(69577535831);
p.push_back(69609234239);
p.push_back(69646485463);
p.push_back(69687118523);
p.push_back(69729181503);
p.push_back(69793054335);
p.push_back(69800870615);
p.push_back(69813932887);
p.push_back(69828314983);
p.push_back(69838180271);
p.push_back(69851507551);
p.push_back(69866930279);
p.push_back(69884198303);
p.push_back(69901636871);
p.push_back(69922184639);
p.push_back(69938724075);
p.push_back(69961358287);
p.push_back(69978138959);
p.push_back(70000513999);
p.push_back(70030243803);
p.push_back(70059130719);
p.push_back(70068865259);
p.push_back(70081614951);
p.push_back(70096302439);
p.push_back(70105997263);
p.push_back(70119272667);
p.push_back(70134897615);
p.push_back(70151934939);
p.push_back(70169469459);
p.push_back(70189122463);
p.push_back(70206411983);
p.push_back(70229438895);
p.push_back(70245699423);
p.push_back(70267929995);
p.push_back(70297413535);
p.push_back(70325192543);
p.push_back(70347220535);
p.push_back(70371272167);
p.push_back(70400633975);
p.push_back(70436044839);
p.push_back(70472107895);
p.push_back(70512803519);
p.push_back(70568573295);
p.push_back(70606848615);
p.push_back(70634466871);
p.push_back(70657257587);
p.push_back(70691733311);
p.push_back(70732028471);
p.push_back(70769485775);
p.push_back(70813888367);
p.push_back(70868522471);
p.push_back(70881251247);
p.push_back(70900342687);
p.push_back(70911081131);
p.push_back(70929934295);
p.push_back(70949703599);
p.push_back(70972072919);
p.push_back(70995117479);
p.push_back(71017795535);
p.push_back(71039813291);
p.push_back(71066815131);
p.push_back(71098549695);
p.push_back(71134418127);
p.push_back(71144445163);
p.push_back(71161045943);
p.push_back(71175780971);
p.push_back(71192433623);
p.push_back(71211047343);
p.push_back(71237370087);
p.push_back(71257469379);
p.push_back(71278531801);
p.push_back(71305462891);
p.push_back(71326502955);
p.push_back(71357737167);
p.push_back(71391623631);
p.push_back(71422498719);
p.push_back(71452467891);
p.push_back(71491913687);
p.push_back(71540245455);
p.push_back(71585016555);
p.push_back(71651753455);
p.push_back(71691558719);
p.push_back(71722639603);
p.push_back(71761481535);
p.push_back(71809171263);
p.push_back(71855734463);
p.push_back(71923998527);
p.push_back(71947703199);
p.push_back(71963947091);
p.push_back(71979673319);
p.push_back(71995629619);
p.push_back(72014140391);
p.push_back(72039105983);
p.push_back(72059787167);
p.push_back(72081360079);
p.push_back(72108602639);
p.push_back(72128290623);
p.push_back(72158289871);
p.push_back(72192415647);
p.push_back(72214165967);
p.push_back(72229434963);
p.push_back(72246038759);
p.push_back(72261156703);
p.push_back(72279520743);
p.push_back(72299558291);
p.push_back(72322060207);
p.push_back(72346486687);
p.push_back(72367326747);
p.push_back(72391734507);
p.push_back(72417379631);
p.push_back(72450946351);
p.push_back(72483898611);
p.push_back(72515577783);
p.push_back(72548987879);
p.push_back(72593317807);
p.push_back(72645492655);
p.push_back(72698070943);
p.push_back(72752601707);
p.push_back(72784294507);
p.push_back(72818168783);
p.push_back(72863757783);
p.push_back(72914485167);
p.push_back(72968663967);
p.push_back(73019636143);
p.push_back(73038138527);
p.push_back(73057705935);
p.push_back(73082077581);
p.push_back(73103403167);
p.push_back(73128656815);
p.push_back(73155783887);
p.push_back(73187498959);
p.push_back(73221386191);
p.push_back(73260556095);
p.push_back(73289250279);
p.push_back(73309247415);
p.push_back(73329113191);
p.push_back(73351907613);
p.push_back(73374678879);
p.push_back(73400423527);
p.push_back(73427334095);
p.push_back(73459042255);
p.push_back(73493387567);
p.push_back(73534021583);
p.push_back(73571911223);
p.push_back(73611305847);
p.push_back(73657529063);
p.push_back(73719224239);
p.push_back(73789416775);
p.push_back(73840762687);
p.push_back(73879979959);
p.push_back(73926025319);
p.push_back(73987766191);
p.push_back(74058323551);
p.push_back(74096774455);
p.push_back(74118285119);
p.push_back(74136614055);
p.push_back(74159758733);
p.push_back(74183995103);
p.push_back(74208294815);
p.push_back(74236654431);
p.push_back(74268581839);
p.push_back(74303307247);
p.push_back(74344152271);
p.push_back(74366858191);
p.push_back(74390249831);
p.push_back(74407493535);
p.push_back(74429343207);
p.push_back(74456071583);
p.push_back(74479474583);
p.push_back(74508482975);
p.push_back(74540724175);
p.push_back(74575894751);
p.push_back(74616983455);
p.push_back(74657638263);
p.push_back(74695570807);
p.push_back(74742584023);
p.push_back(74801782703);
p.push_back(74879182751);
p.push_back(74926554751);
p.push_back(74964128967);
p.push_back(75011186495);
p.push_back(75070594879);
p.push_back(75148361343);
p.push_back(75179585951);
p.push_back(75202567631);
p.push_back(75232212327);
p.push_back(75263902951);
p.push_back(75297076175);
p.push_back(75333362895);
p.push_back(75372170415);
p.push_back(75421736799);
p.push_back(75448322007);
p.push_back(75471468007);
p.push_back(75501197215);
p.push_back(75532603343);
p.push_back(75565913951);
p.push_back(75602432335);
p.push_back(75641432015);
p.push_back(75691282335);
p.push_back(75737744615);
p.push_back(75795613623);
p.push_back(75864751807);
p.push_back(75951046463);
p.push_back(76005298903);
p.push_back(76058486231);
p.push_back(76126060159);
p.push_back(76214747055);
p.push_back(76252702679);
p.push_back(76275455951);
p.push_back(76304698463);
p.push_back(76336864207);
p.push_back(76370245535);
p.push_back(76405620687);
p.push_back(76443780559);
p.push_back(76492693343);
p.push_back(76521304535);
p.push_back(76544203951);
p.push_back(76573583335);
p.push_back(76605627343);
p.push_back(76638912989);
p.push_back(76674535119);
p.push_back(76713053391);
p.push_back(76762120095);
p.push_back(76810568167);
p.push_back(76863236023);
p.push_back(76930858815);
p.push_back(77018992367);
p.push_back(77077830831);
p.push_back(77129442775);
p.push_back(77196427071);
p.push_back(77282492335);
p.push_back(77315983067);
p.push_back(77328904503);
p.push_back(77344229207);
p.push_back(77353937191);
p.push_back(77367318231);
p.push_back(77383344195);
p.push_back(77402525599);
p.push_back(77420079055);
p.push_back(77441857495);
p.push_back(77458663887);
p.push_back(77479933855);
p.push_back(77498234619);
p.push_back(77522132895);
p.push_back(77551151067);
p.push_back(77579391335);
p.push_back(77589256811);
p.push_back(77602587327);
p.push_back(77616148791);
p.push_back(77628547187);
p.push_back(77644381543);
p.push_back(77659800551);
p.push_back(77680638743);
p.push_back(77696992023);
p.push_back(77716546715);
p.push_back(77735300927);
p.push_back(77754085995);
p.push_back(77777409195);
p.push_back(77802962751);
p.push_back(77832024855);
p.push_back(77856802791);
p.push_back(77884039283);
p.push_back(77909480887);
p.push_back(77947185127);
p.push_back(77982917643);
p.push_back(78020467887);
p.push_back(78069491615);
p.push_back(78119382699);
p.push_back(78147273655);
p.push_back(78168103611);
p.push_back(78200862135);
p.push_back(78238073655);
p.push_back(78280788539);
p.push_back(78320734127);
p.push_back(78383387459);
p.push_back(78392019647);
p.push_back(78405855095);
p.push_back(78420070503);
p.push_back(78431588839);
p.push_back(78446171095);
p.push_back(78461488959);
p.push_back(78483849875);
p.push_back(78499021263);
p.push_back(78519730291);
p.push_back(78537132959);
p.push_back(78557231067);
p.push_back(78576840511);
p.push_back(78603706967);
p.push_back(78632550239);
p.push_back(78655231079);
p.push_back(78666719719);
p.push_back(78681407731);
p.push_back(78691989407);
p.push_back(78705335063);
p.push_back(78721323075);
p.push_back(78738104923);
p.push_back(78757239247);
p.push_back(78775352919);
p.push_back(78793198031);
p.push_back(78815788959);
p.push_back(78833326031);
p.push_back(78856463719);
p.push_back(78886901131);
p.push_back(78913839007);
p.push_back(78937076055);
p.push_back(78961231143);
p.push_back(78990644007);
p.push_back(79026389799);
p.push_back(79062990655);
p.push_back(79103668079);
p.push_back(79159414991);
p.push_back(79197329079);
p.push_back(79225231271);
p.push_back(79249568183);
p.push_back(79287184695);
p.push_back(79323996775);
p.push_back(79361255019);
p.push_back(79409000255);
p.push_back(79459356623);
p.push_back(79473994655);
p.push_back(79491827687);
p.push_back(79505359539);
p.push_back(79524576207);
p.push_back(79544682399);
p.push_back(79565754319);
p.push_back(79593149391);
p.push_back(79614022747);
p.push_back(79637348255);
p.push_back(79664566175);
p.push_back(79698593071);
p.push_back(79728509927);
p.push_back(79743491999);
p.push_back(79761174887);
p.push_back(79775737655);
p.push_back(79794362271);
p.push_back(79814590303);
p.push_back(79836787175);
p.push_back(79862379051);
p.push_back(79883788127);
p.push_back(79908396959);
p.push_back(79934531535);
p.push_back(79969222559);
p.push_back(80000951915);
p.push_back(80032868071);
p.push_back(80067024799);
p.push_back(80113336127);
p.push_back(80163705807);
p.push_back(80219023263);
p.push_back(80269929583);
p.push_back(80302106023);
p.push_back(80335971815);
p.push_back(80382911447);
p.push_back(80432596587);
p.push_back(80492166399);
p.push_back(80535220291);
p.push_back(80550798823);
p.push_back(80567707623);
p.push_back(80583090907);
p.push_back(80601681871);
p.push_back(80623216599);
p.push_back(80647113935);
p.push_back(80669750955);
p.push_back(80696355279);
p.push_back(80717428843);
p.push_back(80746962847);
p.push_back(80782303535);
p.push_back(80804388815);
p.push_back(80820375667);
p.push_back(80837043159);
p.push_back(80852320159);
p.push_back(80871016351);
p.push_back(80895696319);
p.push_back(80917398811);
p.push_back(80939652491);
p.push_back(80967213871);
p.push_back(80987531103);
p.push_back(81018292687);
p.push_back(81053078431);
p.push_back(81083619255);
p.push_back(81112728551);
p.push_back(81151955871);
p.push_back(81201820763);
p.push_back(81243736747);
p.push_back(81309044655);
p.push_back(81353069275);
p.push_back(81382514607);
p.push_back(81422005719);
p.push_back(81470736063);
p.push_back(81514345707);
p.push_back(81579249583);
p.push_back(81615917007);
p.push_back(81639089127);
p.push_back(81657603667);
p.push_back(81680730319);
p.push_back(81709248551);
p.push_back(81735894967);
p.push_back(81767404783);
p.push_back(81798468815);
p.push_back(81840312935);
p.push_back(81875713999);
p.push_back(81894838351);
p.push_back(81915027047);
p.push_back(81939931367);
p.push_back(81962465239);
p.push_back(81988816815);
p.push_back(82016883823);
p.push_back(82049443759);
p.push_back(82085519311);
p.push_back(82126931407);
p.push_back(82166363903);
p.push_back(82208629991);
p.push_back(82253606383);
p.push_back(82313844687);
p.push_back(82387804015);
p.push_back(82438391735);
p.push_back(82478197367);
p.push_back(82524810991);
p.push_back(82584633151);
p.push_back(82661610775);
p.push_back(82691822823);
p.push_back(82714162279);
p.push_back(82733363615);
p.push_back(82757823783);
p.push_back(82784168431);
p.push_back(82812908683);
p.push_back(82846060463);
p.push_back(82877702047);
p.push_back(82917435343);
p.push_back(82951079719);
p.push_back(82970697495);
p.push_back(82990671591);
p.push_back(83014834639);
p.push_back(83039450015);
p.push_back(83065231679);
p.push_back(83094355887);
p.push_back(83127131967);
p.push_back(83163964879);
p.push_back(83204792223);
p.push_back(83246581687);
p.push_back(83285296663);
p.push_back(83332788439);
p.push_back(83392503535);
p.push_back(83470878623);
p.push_back(83517344687);
p.push_back(83555158959);
p.push_back(83604117207);
p.push_back(83664983151);
p.push_back(83743833919);
p.push_back(83772399519);
p.push_back(83797108199);
p.push_back(83825092447);
p.push_back(83858269543);
p.push_back(83892510639);
p.push_back(83932512159);
p.push_back(83977674591);
p.push_back(84023295951);
p.push_back(84049702095);
p.push_back(84073346975);
p.push_back(84104452055);
p.push_back(84137755095);
p.push_back(84173023071);
p.push_back(84211342511);
p.push_back(84260171727);
p.push_back(84307902271);
p.push_back(84359021991);
p.push_back(84422993871);
p.push_back(84497164191);
p.push_back(84574507935);
p.push_back(84625654247);
p.push_back(84684387063);
p.push_back(84763197359);
p.push_back(84831303383);
p.push_back(84860310759);
p.push_back(84882915135);
p.push_back(84914939239);
p.push_back(84948111263);
p.push_back(84985819039);
p.push_back(85027803039);
p.push_back(85075074543);
p.push_back(85107680231);
p.push_back(85132976047);
p.push_back(85162287007);
p.push_back(85195570127);
p.push_back(85228912543);
p.push_back(85266143183);
p.push_back(85307104751);
p.push_back(85359673055);
p.push_back(85402654439);
p.push_back(85463473071);
p.push_back(85531315311);
p.push_back(85619168159);
p.push_back(85669978031);
p.push_back(85728564151);
p.push_back(85798692815);
p.push_back(85883676511);
p.push_back(85916982875);
p.push_back(85939224787);
p.push_back(85964500599);
p.push_back(85994080215);
p.push_back(86027781047);
p.push_back(86067700351);
p.push_back(86108663647);
p.push_back(86167584479);
p.push_back(86187412027);
p.push_back(86209172183);
p.push_back(86235657563);
p.push_back(86267346303);
p.push_back(86301291991);
p.push_back(86339237727);
p.push_back(86384056783);
p.push_back(86439445463);
p.push_back(86486738295);
p.push_back(86545553335);
p.push_back(86626128735);
p.push_back(86719544695);
p.push_back(86764444031);
p.push_back(86830761399);
p.push_back(86920919551);
p.push_back(86982525261);
p.push_back(87007237275);
p.push_back(87028932319);
p.push_back(87058110581);
p.push_back(87091150687);
p.push_back(87127609183);
p.push_back(87167499903);
p.push_back(87221657311);
p.push_back(87254174173);
p.push_back(87277536579);
p.push_back(87299425239);
p.push_back(87329669915);
p.push_back(87362712151);
p.push_back(87399395551);
p.push_back(87442185951);
p.push_back(87496093535);
p.push_back(87545331327);
p.push_back(87598379223);
p.push_back(87673953919);
p.push_back(87778833011);
p.push_back(87824550079);
p.push_back(87883530455);
p.push_back(87963402879);
p.push_back(88051290137);
p.push_back(88081009567);
p.push_back(88108265183);
p.push_back(88148804839);
p.push_back(88188933983);
p.push_back(88237893471);
p.push_back(88302986463);
p.push_back(88336256447);
p.push_back(88365938387);
p.push_back(88399972287);
p.push_back(88439481303);
p.push_back(88487347679);
p.push_back(88542645215);
p.push_back(88606654079);
p.push_back(88672318303);
p.push_back(88768648315);
p.push_back(88872779391);
p.push_back(88937823103);
p.push_back(89028320511);
p.push_back(89126153055);
p.push_back(89156387639);
p.push_back(89186178267);
p.push_back(89224494943);
p.push_back(89267705049);
p.push_back(89315605759);
p.push_back(89380562783);
p.push_back(89411138267);
p.push_back(89441481843);
p.push_back(89475937119);
p.push_back(89517215647);
p.push_back(89563392351);
p.push_back(89624228315);
p.push_back(89684572927);
p.push_back(89752191927);
p.push_back(89847616351);
p.push_back(89949263831);
p.push_back(90015835999);
p.push_back(90112245375);
p.push_back(90205863271);
p.push_back(90242322143);
p.push_back(90283006623);
p.push_back(90331942223);
p.push_back(90394705631);
p.push_back(90465138647);
p.push_back(90500569191);
p.push_back(90538546581);
p.push_back(90584874495);
p.push_back(90643403983);
p.push_back(90716102495);
p.push_back(90788879479);
p.push_back(90886517119);
p.push_back(91016557943);
p.push_back(91092242751);
p.push_back(91207892607);
p.push_back(91288323575);
p.push_back(91324261215);
p.push_back(91369080231);
p.push_back(91419905247);
p.push_back(91485138783);
p.push_back(91545717917);
p.push_back(91582728655);
p.push_back(91623262111);
p.push_back(91671790925);
p.push_back(91732278911);
p.push_back(91809125397);
p.push_back(91882823359);
p.push_back(91990988543);
p.push_back(92107182295);
p.push_back(92190839255);
p.push_back(92322462463);
p.push_back(92378838743);
p.push_back(92429084119);
p.push_back(92492947071);
p.push_back(92572599551);
p.push_back(92633449687);
p.push_back(92682155871);
p.push_back(92742418143);
p.push_back(92816310111);
p.push_back(92909992703);
p.push_back(93015791199);
p.push_back(93168336511);
p.push_back(93269874135);
p.push_back(93419939047);
p.push_back(93466163159);
p.push_back(93518843807);
p.push_back(93585749231);
p.push_back(93671755615);
p.push_back(93721700191);
p.push_back(93772071639);
p.push_back(93835519327);
p.push_back(93915840223);
p.push_back(94007230079);
p.push_back(94131713791);
p.push_back(94267350719);
p.push_back(94385569023);
p.push_back(94496360059);
p.push_back(94522948047);
p.push_back(94544270299);
p.push_back(94574663127);
p.push_back(94608678751);
p.push_back(94646023007);
p.push_back(94688319327);
p.push_back(94744030591);
p.push_back(94774763027);
p.push_back(94797554527);
p.push_back(94822805975);
p.push_back(94856052575);
p.push_back(94890102039);
p.push_back(94929659743);
p.push_back(94975984987);
p.push_back(95030909499);
p.push_back(95078843351);
p.push_back(95142738431);
p.push_back(95222365439);
p.push_back(95313223295);
p.push_back(95360066803);
p.push_back(95430075511);
p.push_back(95521111679);
p.push_back(95576786151);
p.push_back(95600874515);
p.push_back(95624115315);
p.push_back(95655810999);
p.push_back(95689922007);
p.push_back(95731539583);
p.push_back(95773380319);
p.push_back(95831781495);
p.push_back(95853220883);
p.push_back(95876711655);
p.push_back(95903066975);
p.push_back(95936753135);
p.push_back(95971825503);
p.push_back(96012894047);
p.push_back(96064240127);
p.push_back(96117290871);
p.push_back(96163926391);
p.push_back(96233602687);
p.push_back(96324047711);
p.push_back(96397853623);
p.push_back(96450470775);
p.push_back(96523606655);
p.push_back(96625540735);
p.push_back(96660063475);
p.push_back(96690110303);
p.push_back(96726930271);
p.push_back(96771803355);
p.push_back(96819432703);
p.push_back(96879333215);
p.push_back(96922953567);
p.push_back(96950959359);
p.push_back(96985577983);
p.push_back(97027340115);
p.push_back(97076035323);
p.push_back(97131363711);
p.push_back(97195911031);
p.push_back(97261846143);
p.push_back(97357757183);
p.push_back(97462156927);
p.push_back(97527072727);
p.push_back(97617313407);
p.push_back(97716458335);
p.push_back(97747013211);
p.push_back(97778033111);
p.push_back(97817483223);
p.push_back(97863950975);
p.push_back(97914511199);
p.push_back(97980219879);
p.push_back(98008632539);
p.push_back(98035932379);
p.push_back(98078465471);
p.push_back(98119261023);
p.push_back(98168471167);
p.push_back(98234314591);
p.push_back(98294037759);
p.push_back(98369627999);
p.push_back(98483567999);
p.push_back(98557137783);
p.push_back(98635196255);
p.push_back(98741156735);
p.push_back(98809124191);
p.push_back(98848210175);
p.push_back(98894171039);
p.push_back(98952826719);
p.push_back(99023573855);
p.push_back(99074551135);
p.push_back(99112326975);
p.push_back(99158985199);
p.push_back(99215171199);
p.push_back(99286867807);
p.push_back(99360677503);
p.push_back(99447096759);
p.push_back(99589763447);
p.push_back(99662431831);
p.push_back(99770497791);
p.push_back(99872247519);
p.push_back(99909982071);
p.push_back(99955522783);
p.push_back(100006821119);
p.push_back(100073543519);
p.push_back(100137077935);
p.push_back(100176297695);
p.push_back(100219033303);
p.push_back(100269381471);
p.push_back(100335058303);
p.push_back(100414084823);
p.push_back(100495804983);
p.push_back(100615382879);
p.push_back(100714750423);
p.push_back(100805486431);
p.push_back(100936116183);
p.push_back(100983201631);
p.push_back(101038117335);
p.push_back(101107760991);
p.push_back(101200515799);
p.push_back(101244206335);
p.push_back(101301675871);
p.push_back(101369328847);
p.push_back(101456434015);
p.push_back(101552805847);
p.push_back(101693609567);
p.push_back(101808438911);
p.push_back(101943453535);
p.push_back(102037147327);
p.push_back(102086195711);
p.push_back(102147337423);
p.push_back(102229610335);
p.push_back(102296821599);
p.push_back(102346280799);
p.push_back(102409248607);
p.push_back(102486189551);
p.push_back(102580425175);
p.push_back(102694420095);
p.push_back(102840639167);
p.push_back(102946613087);
p.push_back(103081617371);
p.push_back(103098626843);
p.push_back(103117699691);
p.push_back(103136930255);
p.push_back(103179194271);
p.push_back(103216375711);
p.push_back(103240481503);
p.push_back(103266279231);
p.push_back(103314571183);
p.push_back(103352197415);
p.push_back(103370228383);
p.push_back(103388382603);
p.push_back(103414234367);
p.push_back(103453019439);
p.push_back(103487782767);
p.push_back(103516447851);
p.push_back(103538961711);
p.push_back(103589486511);
p.push_back(103640866623);
p.push_back(103698950639);
p.push_back(103784335791);
p.push_back(103885122283);
p.push_back(103925482415);
p.push_back(104008077119);
p.push_back(104073285439);
p.push_back(104157291211);
p.push_back(104174993751);
p.push_back(104193363919);
p.push_back(104218041671);
p.push_back(104257699695);
p.push_back(104292368303);
p.push_back(104321417023);
p.push_back(104343859103);
p.push_back(104394008527);
p.push_back(104427798991);
p.push_back(104447283007);
p.push_back(104466168427);
p.push_back(104492134895);
p.push_back(104532844495);
p.push_back(104564280223);
p.push_back(104592869327);
p.push_back(104621382079);
p.push_back(104675655487);
p.push_back(104725583083);
p.push_back(104792984359);
p.push_back(104864142511);
p.push_back(104963170111);
p.push_back(105008944319);
p.push_back(105096089455);
p.push_back(105163051903);
p.push_back(105233594331);
p.push_back(105262490731);
p.push_back(105283831711);
p.push_back(105332849519);
p.push_back(105368933215);
p.push_back(105399264939);
p.push_back(105432911791);
p.push_back(105496019097);
p.push_back(105516390685);
p.push_back(105538235343);
p.push_back(105574223343);
p.push_back(105630269343);
p.push_back(105653109851);
p.push_back(105682572059);
p.push_back(105734220751);
p.push_back(105798425007);
p.push_back(105898133935);
p.push_back(105968489343);
p.push_back(106067887339);
p.push_back(106167560559);
p.push_back(106239682991);
p.push_back(106308304511);
p.push_back(106336945835);
p.push_back(106359176331);
p.push_back(106408613199);
p.push_back(106446954223);
p.push_back(106474256335);
p.push_back(106508887435);
p.push_back(106570825679);
p.push_back(106591267279);
p.push_back(106616532719);
p.push_back(106654009247);
p.push_back(106705359403);
p.push_back(106730487711);
p.push_back(106757988747);
p.push_back(106810218459);
p.push_back(106874347439);
p.push_back(106974194411);
p.push_back(107052678639);
p.push_back(107143771371);
p.push_back(107244171183);
p.push_back(107326603071);
p.push_back(107392087247);
p.push_back(107423682239);
p.push_back(107473927647);
p.push_back(107523546543);
p.push_back(107564447183);
p.push_back(107643222991);
p.push_back(107670957279);
p.push_back(107701065631);
p.push_back(107760408479);
p.push_back(107807054109);
p.push_back(107853033391);
p.push_back(107932933951);
p.push_back(108034498367);
p.push_back(108164201855);
p.push_back(108245875967);
p.push_back(108359946159);
p.push_back(108456558511);
p.push_back(108487576783);
p.push_back(108531064207);
p.push_back(108586997711);
p.push_back(108628692143);
p.push_back(108697832911);
p.push_back(108736880031);
p.push_back(108768140327);
p.push_back(108819580367);
p.push_back(108869123711);
p.push_back(108913319775);
p.push_back(108990191927);
p.push_back(109075043775);
p.push_back(109191282607);
p.push_back(109296622183);
p.push_back(109410615103);
p.push_back(109526561743);
p.push_back(109562826191);
p.push_back(109626574159);
p.push_back(109679869855);
p.push_back(109736397231);
p.push_back(109801876719);
p.push_back(109842382687);
p.push_back(109910192031);
p.push_back(109960234959);
p.push_back(110025785295);
p.push_back(110115126911);
p.push_back(110252523199);
p.push_back(110383816511);
p.push_back(110522203839);
p.push_back(110616422863);
p.push_back(110655200159);
p.push_back(110730756047);
p.push_back(110770585439);
p.push_back(110847934367);
p.push_back(110894915263);
p.push_back(110936180639);
p.push_back(111003713391);
p.push_back(111051423551);
p.push_back(111135162175);
p.push_back(111265443775);
p.push_back(111403896239);
p.push_back(111534978991);
p.push_back(111669750735);
p.push_back(111686978919);
p.push_back(111707042699);
p.push_back(111725911535);
p.push_back(111766404543);
p.push_back(111806187179);
p.push_back(111832013263);
p.push_back(111856683227);
p.push_back(111906366255);
p.push_back(111942950815);
p.push_back(111962654623);
p.push_back(111981952927);
p.push_back(112008194375);
p.push_back(112051634127);
p.push_back(112082898847);
p.push_back(112110180971);
p.push_back(112141143983);
p.push_back(112197045119);
p.push_back(112244835895);
p.push_back(112321138607);
p.push_back(112389811311);
p.push_back(112483834603);
p.push_back(112531717951);
p.push_back(112619491247);
p.push_back(112701995967);
p.push_back(112751286387);
p.push_back(112777004139);
p.push_back(112794176059);
p.push_back(112822844911);
p.push_back(112867446687);
p.push_back(112896351835);
p.push_back(112919617487);
p.push_back(112958905295);
p.push_back(113013359055);
p.push_back(113030839515);
p.push_back(113050188239);
p.push_back(113069805471);
p.push_back(113113805775);
p.push_back(113150052815);
p.push_back(113179437291);
p.push_back(113201053503);
p.push_back(113251740111);
p.push_back(113303196859);
p.push_back(113359465831);
p.push_back(113447681967);
p.push_back(113548509103);
p.push_back(113589105903);
p.push_back(113672219071);
p.push_back(113737137983);
p.push_back(113821743007);
p.push_back(113850944107);
p.push_back(113871815771);
p.push_back(113920675247);
p.push_back(113957930667);
p.push_back(113988949199);
p.push_back(114022446415);
p.push_back(114085988971);
p.push_back(114106987423);
p.push_back(114131774699);
p.push_back(114170418591);
p.push_back(114221776799);
p.push_back(114252850283);
p.push_back(114275592031);
p.push_back(114332850639);
p.push_back(114393355499);
p.push_back(114493427567);
p.push_back(114588393391);
p.push_back(114662312683);
p.push_back(114762852971);
p.push_back(114859136303);
p.push_back(114907427851);
p.push_back(114929739727);
p.push_back(114960796079);
p.push_back(115014445391);
p.push_back(115045687199);
p.push_back(115075183519);
p.push_back(115125593483);
p.push_back(115164948431);
p.push_back(115193991071);
p.push_back(115215427423);
p.push_back(115264577439);
p.push_back(115301364687);
p.push_back(115331753887);
p.push_back(115366668251);
p.push_back(115431784367);
p.push_back(115497740143);
p.push_back(115597546731);
p.push_back(115701111215);
p.push_back(115768303535);
p.push_back(115867098991);
p.push_back(115967897039);
p.push_back(116000169255);
p.push_back(116035686863);
p.push_back(116099497935);
p.push_back(116138439759);
p.push_back(116204382159);
p.push_back(116251809695);
p.push_back(116284196767);
p.push_back(116337546703);
p.push_back(116388044703);
p.push_back(116434878383);
p.push_back(116513734519);
p.push_back(116607659887);
p.push_back(116736167855);
p.push_back(116824361527);
p.push_back(116941797295);
p.push_back(117044905167);
p.push_back(117077463455);
p.push_back(117122278303);
p.push_back(117178075087);
p.push_back(117223101343);
p.push_back(117295453023);
p.push_back(117331355487);
p.push_back(117363063847);
p.push_back(117424087831);
p.push_back(117474275247);
p.push_back(117524561727);
p.push_back(117605289847);
p.push_back(117710921583);
p.push_back(117844016959);
p.push_back(117917816103);
p.push_back(118034456383);
p.push_back(118131602895);
p.push_back(118170556847);
p.push_back(118247557071);
p.push_back(118291865327);
p.push_back(118369243999);
p.push_back(118415224671);
p.push_back(118464991135);
p.push_back(118531249055);
p.push_back(118581384527);
p.push_back(118669643583);
p.push_back(118800154431);
p.push_back(118938201919);
p.push_back(119068835647);
p.push_back(119190697935);
p.push_back(119231491023);
p.push_back(119293710287);
p.push_back(119353870287);
p.push_back(119413210591);
p.push_back(119473970383);
p.push_back(119513055135);
p.push_back(119589855071);
p.push_back(119634319791);
p.push_back(119711752095);
p.push_back(119827758911);
p.push_back(119975902079);
p.push_back(120096522047);
p.push_back(120244862783);
p.push_back(120291146971);
p.push_back(120329099167);
p.push_back(120400189311);
p.push_back(120454528763);
p.push_back(120535011551);
p.push_back(120570973679);
p.push_back(120630384047);
p.push_back(120693743455);
p.push_back(120767315327);
p.push_back(120864331127);
p.push_back(121046859135);
p.push_back(121164069375);
p.push_back(121334658911);
p.push_back(121368874295);
p.push_back(121412603255);
p.push_back(121484306271);
p.push_back(121540334431);
p.push_back(121616611711);
p.push_back(121652434847);
p.push_back(121712782303);
p.push_back(121773216607);
p.push_back(121857580415);
p.push_back(121963015167);
p.push_back(122142657471);
p.push_back(122262802239);
p.push_back(122411960159);
p.push_back(122458957663);
p.push_back(122542084959);
p.push_back(122596446047);
p.push_back(122683347807);
p.push_back(122730228095);
p.push_back(122813852923);
p.push_back(122872774395);
p.push_back(122993969723);
p.push_back(123186068863);
p.push_back(123354349183);
p.push_back(123497310047);
p.push_back(123537905567);
p.push_back(123621801599);
p.push_back(123686043119);
p.push_back(123768456095);
p.push_back(123816538975);
p.push_back(123900363231);
p.push_back(123968639839);
p.push_back(124091518783);
p.push_back(124295478527);
p.push_back(124457746047);
p.push_back(124585746111);
p.push_back(124661669695);
p.push_back(124752969343);
p.push_back(124849987263);
p.push_back(124927702359);
p.push_back(125015402335);
p.push_back(125163420023);
p.push_back(125393772351);
p.push_back(125627866133);
p.push_back(125680658271);
p.push_back(125775845743);
p.push_back(125886562143);
p.push_back(125947611735);
p.push_back(126039103821);
p.push_back(126150682463);
p.push_back(126332739199);
p.push_back(126538829631);
p.push_back(126723696479);
p.push_back(126825561951);
p.push_back(126937546591);
p.push_back(127024603039);
p.push_back(127138090847);
p.push_back(127278751551);
p.push_back(127543299903);
p.push_back(127781866703);
p.push_back(127870476191);
p.push_back(127975685855);
p.push_back(128082085791);
p.push_back(128190381791);
p.push_back(128316940095);
p.push_back(128581345087);
p.push_back(128835812735);
p.push_back(128883557727);
p.push_back(128923035487);
p.push_back(128999070159);
p.push_back(129055926735);
p.push_back(129134559835);
p.push_back(129170276191);
p.push_back(129237589919);
p.push_back(129292922719);
p.push_back(129388382779);
p.push_back(129507655039);
p.push_back(129672292735);
p.push_back(129803124351);
p.push_back(129931709659);
p.push_back(129971292623);
p.push_back(130030342047);
p.push_back(130094074991);
p.push_back(130178836319);
p.push_back(130224809567);
p.push_back(130262663563);
p.push_back(130335461215);
p.push_back(130394160991);
p.push_back(130497535167);
p.push_back(130638647039);
p.push_back(130781150847);
p.push_back(130933652863);
p.push_back(131031209167);
p.push_back(131093536671);
p.push_back(131166898395);
p.push_back(131259301343);
p.push_back(131304838559);
p.push_back(131382576479);
p.push_back(131444358879);
p.push_back(131552261243);
p.push_back(131712908543);
p.push_back(131887898431);
p.push_back(132074126975);
p.push_back(132121125727);
p.push_back(132204925035);
p.push_back(132259897183);
p.push_back(132349466859);
p.push_back(132395340891);
p.push_back(132479666015);
p.push_back(132544407023);
p.push_back(132664053567);
p.push_back(132877319807);
p.push_back(133032558207);
p.push_back(133169753951);
p.push_back(133249791839);
p.push_back(133342346495);
p.push_back(133446111591);
p.push_back(133527403903);
p.push_back(133618902879);
p.push_back(133786033983);
p.push_back(134000814463);
p.push_back(134222354079);
p.push_back(134282690175);
p.push_back(134385864543);
p.push_back(134492997535);
p.push_back(134557080959);
p.push_back(134657856863);
p.push_back(134789496575);
p.push_back(135023959871);
p.push_back(135208959615);
p.push_back(135343640415);
p.push_back(135459360607);
p.push_back(135577241503);
p.push_back(135671090575);
p.push_back(135782489951);
p.push_back(136000831103);
p.push_back(136264605311);
p.push_back(136412258207);
p.push_back(136522088287);
p.push_back(136641584991);
p.push_back(136737076575);
p.push_back(136841584479);
p.push_back(137058770559);
p.push_back(137322528383);
p.push_back(137443915483);
p.push_back(137456299707);
p.push_back(137472544971);
p.push_back(137481027295);
p.push_back(137494667735);
p.push_back(137510688567);
p.push_back(137528415527);
p.push_back(137546566511);
p.push_back(137566093527);
p.push_back(137584058735);
p.push_back(137607250539);
p.push_back(137624087391);
p.push_back(137646918831);
p.push_back(137677285743);
p.push_back(137707557035);
p.push_back(137716130135);
p.push_back(137729869879);
p.push_back(137744190127);
p.push_back(137755702827);
p.push_back(137770308619);
p.push_back(137785428463);
p.push_back(137807771135);
p.push_back(137823060311);
p.push_back(137843856727);
p.push_back(137861189983);
p.push_back(137881223407);
p.push_back(137900774847);
p.push_back(137927761391);
p.push_back(137956232559);
p.push_back(137982398491);
p.push_back(138010511127);
p.push_back(138032437951);
p.push_back(138066202423);
p.push_back(138105119223);
p.push_back(138145738875);
p.push_back(138186850543);
p.push_back(138246464523);
p.push_back(138268584191);
p.push_back(138292812735);
p.push_back(138322938607);
p.push_back(138360652343);
p.push_back(138399623931);
p.push_back(138441881791);
p.push_back(138500131007);
p.push_back(138519672183);
p.push_back(138533081495);
p.push_back(138548351415);
p.push_back(138558270567);
p.push_back(138571687051);
p.push_back(138587473879);
p.push_back(138607706335);
p.push_back(138624725087);
p.push_back(138647008431);
p.push_back(138663698475);
p.push_back(138684205679);
p.push_back(138702358267);
p.push_back(138727664751);
p.push_back(138756007087);
p.push_back(138783369051);
p.push_back(138793779339);
p.push_back(138806970559);
p.push_back(138820002011);
p.push_back(138832610231);
p.push_back(138848608951);
p.push_back(138864350903);
p.push_back(138884471391);
p.push_back(138901315167);
p.push_back(138920410139);
p.push_back(138939493087);
p.push_back(138958620015);
p.push_back(138982695195);
p.push_back(139008725471);
p.push_back(139037261103);
p.push_back(139061563703);
p.push_back(139087823479);
p.push_back(139115828855);
p.push_back(139151842927);
p.push_back(139188048151);
p.push_back(139225138023);
p.push_back(139278235839);
p.push_back(139323849455);
p.push_back(139351913079);
p.push_back(139372983415);
p.push_back(139406463031);
p.push_back(139444098679);
p.push_back(139486345007);
p.push_back(139526488671);
p.push_back(139587108027);
p.push_back(139599501047);
p.push_back(139619732703);
p.push_back(139630524139);
p.push_back(139649361067);
p.push_back(139670558491);
p.push_back(139692626487);
p.push_back(139718768631);
p.push_back(139739709535);
p.push_back(139761333103);
p.push_back(139790155803);
p.push_back(139824202443);
p.push_back(139856336279);
p.push_back(139869896855);
p.push_back(139888829275);
p.push_back(139900871135);
p.push_back(139920286907);
p.push_back(139940630623);
p.push_back(139962160823);
p.push_back(139989467567);
p.push_back(140009830623);
p.push_back(140031500475);
p.push_back(140060420703);
p.push_back(140094406939);
p.push_back(140127606475);
p.push_back(140159285175);
p.push_back(140191775983);
p.push_back(140231658863);
p.push_back(140280907967);
p.push_back(140332788607);
p.push_back(140396299275);
p.push_back(140428202719);
p.push_back(140461071039);
p.push_back(140501844151);
p.push_back(140551143871);
p.push_back(140604425151);
p.push_back(140662929503);
p.push_back(140677742651);
p.push_back(140695709935);
p.push_back(140709499287);
p.push_back(140728458543);
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(i * (ll)(7e5) <= n)
i ++;
i --;
ll mask = p[i], x, idx = i * (ll)(7e5);
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| 4 |
Correct |
1 ms |
468 KB |
Output is correct |
| 5 |
Correct |
1 ms |
468 KB |
Output is correct |
| 6 |
Correct |
1 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| 4 |
Correct |
1 ms |
468 KB |
Output is correct |
| 5 |
Correct |
1 ms |
468 KB |
Output is correct |
| 6 |
Correct |
1 ms |
468 KB |
Output is correct |
| 7 |
Incorrect |
827 ms |
524 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| 4 |
Correct |
1 ms |
468 KB |
Output is correct |
| 5 |
Correct |
1 ms |
468 KB |
Output is correct |
| 6 |
Correct |
1 ms |
468 KB |
Output is correct |
| 7 |
Incorrect |
827 ms |
524 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| 4 |
Correct |
1 ms |
468 KB |
Output is correct |
| 5 |
Correct |
1 ms |
468 KB |
Output is correct |
| 6 |
Correct |
1 ms |
468 KB |
Output is correct |
| 7 |
Incorrect |
827 ms |
524 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| 4 |
Correct |
1 ms |
468 KB |
Output is correct |
| 5 |
Correct |
1 ms |
468 KB |
Output is correct |
| 6 |
Correct |
1 ms |
468 KB |
Output is correct |
| 7 |
Incorrect |
827 ms |
524 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
