이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/**
____ ____ ____ ____ ____ ____
||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 = 7e5;
vector < vector < ll > > st;
ll gcd[maxnum][maxnum];
vector < ll > p;
void precompute()
{
p.push_back(0);
p.push_back(9564415);
p.push_back(24351991);
p.push_back(39311191);
p.push_back(54219543);
p.push_back(71702511);
p.push_back(90883007);
p.push_back(111611247);
p.push_back(135872863);
p.push_back(155518319);
p.push_back(177042815);
p.push_back(204020671);
p.push_back(236979263);
p.push_back(268961851);
p.push_back(279613179);
p.push_back(294690527);
p.push_back(308706239);
p.push_back(323921531);
p.push_back(341606511);
p.push_back(362021431);
p.push_back(382573487);
p.push_back(405605979);
p.push_back(426053963);
p.push_back(448618207);
p.push_back(474584431);
p.push_back(507589687);
p.push_back(540019239);
p.push_back(570504811);
p.push_back(595688247);
p.push_back(638826359);
p.push_back(678626151);
p.push_back(726011963);
p.push_back(793610079);
p.push_back(826389943);
p.push_back(854721463);
p.push_back(891401143);
p.push_back(938045119);
p.push_back(979963451);
p.push_back(1042874047);
p.push_back(1078990197);
p.push_back(1092852607);
p.push_back(1109409423);
p.push_back(1122047951);
p.push_back(1139893599);
p.push_back(1157126975);
p.push_back(1178677551);
p.push_back(1198958559);
p.push_back(1220551247);
p.push_back(1244387135);
p.push_back(1265520255);
p.push_back(1295885951);
p.push_back(1328708095);
p.push_back(1348560047);
p.push_back(1362695899);
p.push_back(1378557103);
p.push_back(1392250783);
p.push_back(1409940287);
p.push_back(1427444831);
p.push_back(1448428447);
p.push_back(1470770559);
p.push_back(1491402959);
p.push_back(1514509391);
p.push_back(1537643519);
p.push_back(1567125311);
p.push_back(1600515903);
p.push_back(1628776287);
p.push_back(1657087207);
p.push_back(1692561279);
p.push_back(1735988767);
p.push_back(1782900799);
p.push_back(1842813439);
p.push_back(1887919423);
p.push_back(1918114351);
p.push_back(1950397775);
p.push_back(1990559663);
p.push_back(2036655551);
p.push_back(2086866751);
p.push_back(2149615658);
p.push_back(2165312383);
p.push_back(2184136063);
p.push_back(2201334879);
p.push_back(2221846399);
p.push_back(2250662847);
p.push_back(2277536703);
p.push_back(2302090239);
p.push_back(2328804095);
p.push_back(2361168127);
p.push_back(2401546447);
p.push_back(2423174879);
p.push_back(2442814463);
p.push_back(2459301631);
p.push_back(2483205983);
p.push_back(2504636543);
p.push_back(2531592383);
p.push_back(2556805567);
p.push_back(2586302079);
p.push_back(2614886911);
p.push_back(2652909951);
p.push_back(2688911263);
p.push_back(2723589375);
p.push_back(2765834239);
p.push_back(2821243483);
p.push_back(2875599615);
p.push_back(2955191823);
p.push_back(2989818143);
p.push_back(3026760255);
p.push_back(3085183487);
p.push_back(3137894047);
p.push_back(3221366479);
p.push_back(3235107583);
p.push_back(3255846975);
p.push_back(3272050559);
p.push_back(3292835855);
p.push_back(3321103519);
p.push_back(3344193663);
p.push_back(3371116031);
p.push_back(3396170239);
p.push_back(3427851359);
p.push_back(3466109183);
p.push_back(3494979711);
p.push_back(3512710399);
p.push_back(3529941711);
p.push_back(3549854719);
p.push_back(3574404351);
p.push_back(3598259263);
p.push_back(3627815423);
p.push_back(3656620031);
p.push_back(3680557183);
p.push_back(3716455583);
p.push_back(3759182495);
p.push_back(3793916223);
p.push_back(3830220351);
p.push_back(3882707711);
p.push_back(3938559487);
p.push_back(4017706751);
p.push_back(4060193567);
p.push_back(4095518335);
p.push_back(4145578623);
p.push_back(4200697887);
p.push_back(4276418047);
p.push_back(4309730503);
p.push_back(4333352623);
p.push_back(4358999183);
p.push_back(4384441877);
p.push_back(4414457623);
p.push_back(4448075679);
p.push_back(4484999535);
p.push_back(4531004623);
p.push_back(4568235343);
p.push_back(4590691927);
p.push_back(4614042983);
p.push_back(4639241895);
p.push_back(4668951471);
p.push_back(4700785743);
p.push_back(4735999055);
p.push_back(4775073023);
p.push_back(4822429535);
p.push_back(4867949799);
p.push_back(4915759423);
p.push_back(4975106735);
p.push_back(5057146687);
p.push_back(5121976183);
p.push_back(5169866327);
p.push_back(5225202999);
p.push_back(5302005167);
p.push_back(5373179191);
p.push_back(5394645695);
p.push_back(5418169575);
p.push_back(5443491463);
p.push_back(5473673575);
p.push_back(5504816221);
p.push_back(5540744015);
p.push_back(5578731727);
p.push_back(5625426079);
p.push_back(5651659103);
p.push_back(5675431507);
p.push_back(5700916383);
p.push_back(5726524247);
p.push_back(5756305751);
p.push_back(5789878911);
p.push_back(5826908319);
p.push_back(5872952655);
p.push_back(5915414583);
p.push_back(5961356983);
p.push_back(6015023031);
p.push_back(6084724655);
p.push_back(6175262695);
p.push_back(6216291431);
p.push_back(6271017791);
p.push_back(6333575871);
p.push_back(6416709103);
p.push_back(6460585687);
p.push_back(6489526975);
p.push_back(6522422999);
p.push_back(6560278103);
p.push_back(6600451231);
p.push_back(6648325455);
p.push_back(6704631247);
p.push_back(6732977511);
p.push_back(6762940735);
p.push_back(6796613279);
p.push_back(6833870927);
p.push_back(6879315023);
p.push_back(6924805327);
p.push_back(6981912167);
p.push_back(7035970647);
p.push_back(7106004671);
p.push_back(7201744031);
p.push_back(7282090815);
p.push_back(7342546367);
p.push_back(7421137103);
p.push_back(7518438695);
p.push_back(7548397247);
p.push_back(7574921383);
p.push_back(7611035583);
p.push_back(7651167407);
p.push_back(7690792271);
p.push_back(7742469471);
p.push_back(7789711183);
p.push_back(7820057167);
p.push_back(7852021095);
p.push_back(7886639911);
p.push_back(7923732559);
p.push_back(7968961999);
p.push_back(8021587407);
p.push_back(8075403479);
p.push_back(8136991319);
p.push_back(8216785599);
p.push_back(8321901671);
p.push_back(8374127935);
p.push_back(8442467927);
p.push_back(8533317039);
p.push_back(8595227991);
p.push_back(8609859863);
p.push_back(8626381643);
p.push_back(8640234735);
p.push_back(8658003823);
p.push_back(8677070391);
p.push_back(8698052887);
p.push_back(8723207863);
p.push_back(8743205051);
p.push_back(8764991343);
p.push_back(8792113355);
p.push_back(8825701579);
p.push_back(8858732299);
p.push_back(8870200983);
p.push_back(8887037407);
p.push_back(8899795247);
p.push_back(8915484095);
p.push_back(8933899999);
p.push_back(8959296779);
p.push_back(8978023479);
p.push_back(8999403675);
p.push_back(9026270875);
p.push_back(9045725791);
p.push_back(9074853359);
p.push_back(9108486751);
p.push_back(9137663983);
p.push_back(9167042487);
p.push_back(9200222679);
p.push_back(9242917871);
p.push_back(9291280059);
p.push_back(9340788079);
p.push_back(9400391535);
p.push_back(9431166447);
p.push_back(9461458679);
p.push_back(9501306223);
p.push_back(9544931183);
p.push_back(9595906815);
p.push_back(9664017067);
p.push_back(9675461815);
p.push_back(9692273207);
p.push_back(9705054295);
p.push_back(9720755127);
p.push_back(9739178839);
p.push_back(9764545335);
p.push_back(9783294999);
p.push_back(9804661783);
p.push_back(9831544071);
p.push_back(9850957663);
p.push_back(9880027999);
p.push_back(9913648063);
p.push_back(9937293167);
p.push_back(9951854711);
p.push_back(9968453403);
p.push_back(9982071487);
p.push_back(10000052683);
p.push_back(10019083231);
p.push_back(10040136023);
p.push_back(10065098079);
p.push_back(10085283739);
p.push_back(10107074651);
p.push_back(10134170479);
p.push_back(10167789743);
p.push_back(10201038135);
p.push_back(10228092727);
p.push_back(10255452863);
p.push_back(10297691071);
p.push_back(10339477183);
p.push_back(10385331963);
p.push_back(10450380143);
p.push_back(10487905403);
p.push_back(10516241647);
p.push_back(10552877751);
p.push_back(10597739455);
p.push_back(10642450671);
p.push_back(10704451423);
p.push_back(10743162327);
p.push_back(10761447871);
p.push_back(10778725487);
p.push_back(10801398711);
p.push_back(10825599151);
p.push_back(10852474351);
p.push_back(10878337887);
p.push_back(10908179163);
p.push_back(10938242527);
p.push_back(10976084703);
p.push_back(11009202543);
p.push_back(11026732383);
p.push_back(11044783447);
p.push_back(11062939851);
p.push_back(11088548575);
p.push_back(11113619807);
p.push_back(11143066843);
p.push_back(11173235455);
p.push_back(11196804527);
p.push_back(11236561631);
p.push_back(11276478575);
p.push_back(11310921407);
p.push_back(11347817687);
p.push_back(11403609847);
p.push_back(11458217455);
p.push_back(11542761019);
p.push_back(11577022143);
p.push_back(11613008983);
p.push_back(11664210815);
p.push_back(11718075119);
p.push_back(11796836703);
p.push_back(11822502107);
p.push_back(11845219803);
p.push_back(11861541815);
p.push_back(11882488919);
p.push_back(11911941551);
p.push_back(11934941879);
p.push_back(11962786555);
p.push_back(11988200159);
p.push_back(12020201839);
p.push_back(12063102303);
p.push_back(12086552347);
p.push_back(12107242207);
p.push_back(12123894519);
p.push_back(12147218231);
p.push_back(12170350943);
p.push_back(12198221079);
p.push_back(12223103711);
p.push_back(12252387759);
p.push_back(12283521903);
p.push_back(12321162187);
p.push_back(12357414651);
p.push_back(12394181867);
p.push_back(12440366527);
p.push_back(12493147631);
p.push_back(12554637679);
p.push_back(12622907759);
p.push_back(12657438935);
p.push_back(12702857079);
p.push_back(12756237039);
p.push_back(12817854143);
p.push_back(12888246199);
p.push_back(12911369663);
p.push_back(12935431511);
p.push_back(12961540727);
p.push_back(12992489007);
p.push_back(13024822871);
p.push_back(13061953967);
p.push_back(13105604447);
p.push_back(13154137627);
p.push_back(13175558615);
p.push_back(13199765719);
p.push_back(13226071735);
p.push_back(13258270895);
p.push_back(13289675951);
p.push_back(13326061743);
p.push_back(13367278431);
p.push_back(13416318687);
p.push_back(13460338231);
p.push_back(13510696639);
p.push_back(13573350239);
p.push_back(13658776663);
p.push_back(13719908151);
p.push_back(13764662999);
p.push_back(13826430703);
p.push_back(13900991983);
p.push_back(13965407959);
p.push_back(13992750431);
p.push_back(14014158711);
p.push_back(14042954103);
p.push_back(14073230967);
p.push_back(14107248111);
p.push_back(14145149663);
p.push_back(14193654623);
p.push_back(14231701463);
p.push_back(14256890615);
p.push_back(14278924215);
p.push_back(14306860599);
p.push_back(14336982751);
p.push_back(14369821039);
p.push_back(14407960239);
p.push_back(14451619639);
p.push_back(14499898551);
p.push_back(14543101495);
p.push_back(14599474487);
p.push_back(14666172079);
p.push_back(14751927999);
p.push_back(14802171831);
p.push_back(14852363447);
p.push_back(14915164863);
p.push_back(15000163823);
p.push_back(15049490903);
p.push_back(15078559959);
p.push_back(15112391855);
p.push_back(15151181535);
p.push_back(15196407231);
p.push_back(15241381231);
p.push_back(15301470559);
p.push_back(15330612663);
p.push_back(15357805787);
p.push_back(15397663671);
p.push_back(15436520175);
p.push_back(15478663919);
p.push_back(15536232623);
p.push_back(15589410167);
p.push_back(15647231215);
p.push_back(15725426367);
p.push_back(15832815359);
p.push_back(15888205175);
p.push_back(15955448503);
p.push_back(16044380271);
p.push_back(16115925463);
p.push_back(16146085335);
p.push_back(16179019119);
p.push_back(16217156591);
p.push_back(16260589279);
p.push_back(16308731247);
p.push_back(16364127583);
p.push_back(16396795375);
p.push_back(16427255255);
p.push_back(16462984535);
p.push_back(16501723575);
p.push_back(16546855087);
p.push_back(16597228383);
p.push_back(16651678455);
p.push_back(16712488759);
p.push_back(16783062895);
p.push_back(16883683055);
p.push_back(16950709951);
p.push_back(17016787383);
p.push_back(17101022047);
p.push_back(17186198743);
p.push_back(17213948319);
p.push_back(17239426495);
p.push_back(17275365087);
p.push_back(17315836031);
p.push_back(17360751999);
p.push_back(17418952319);
p.push_back(17460899455);
p.push_back(17487007903);
p.push_back(17516518655);
p.push_back(17552952447);
p.push_back(17592939007);
p.push_back(17639687039);
p.push_back(17702638719);
p.push_back(17757857151);
p.push_back(17827710719);
p.push_back(17924380255);
p.push_back(18015592831);
p.push_back(18077520951);
p.push_back(18170003583);
p.push_back(18260131991);
p.push_back(18288031707);
p.push_back(18313970047);
p.push_back(18350152479);
p.push_back(18390147327);
p.push_back(18435543423);
p.push_back(18493350399);
p.push_back(18534909021);
p.push_back(18561134815);
p.push_back(18590743935);
p.push_back(18627103167);
p.push_back(18667577855);
p.push_back(18714050943);
p.push_back(18777326079);
p.push_back(18832625151);
p.push_back(18903167359);
p.push_back(18999734015);
p.push_back(19090627327);
p.push_back(19153102591);
p.push_back(19244909055);
p.push_back(19334926575);
p.push_back(19368062847);
p.push_back(19408459207);
p.push_back(19456809983);
p.push_back(19512752511);
p.push_back(19584243583);
p.push_back(19620312799);
p.push_back(19654202751);
p.push_back(19700770015);
p.push_back(19751922431);
p.push_back(19814978655);
p.push_back(19887558839);
p.push_back(19969118303);
p.push_back(20090487679);
p.push_back(20184073439);
p.push_back(20276741631);
p.push_back(20403978911);
p.push_back(20437062111);
p.push_back(20472211839);
p.push_back(20519889279);
p.push_back(20573099263);
p.push_back(20640481663);
p.push_back(20688650335);
p.push_back(20722205279);
p.push_back(20762698495);
p.push_back(20812165887);
p.push_back(20872254559);
p.push_back(20945646303);
p.push_back(21022153087);
p.push_back(21129177599);
p.push_back(21242319415);
p.push_back(21327184767);
p.push_back(21462074239);
p.push_back(21511308927);
p.push_back(21557403135);
p.push_back(21613336159);
p.push_back(21686391903);
p.push_back(21757071599);
p.push_back(21799134431);
p.push_back(21849657695);
p.push_back(21914762623);
p.push_back(21997872511);
p.push_back(22084147319);
p.push_back(22213107967);
p.push_back(22333023615);
p.push_back(22448079615);
p.push_back(22563558575);
p.push_back(22605321567);
p.push_back(22656079295);
p.push_back(22721195391);
p.push_back(22805190527);
p.push_back(22851930079);
p.push_back(22897066223);
p.push_back(22952715135);
p.push_back(23024741855);
p.push_back(23113780735);
p.push_back(23210088383);
p.push_back(23362852607);
p.push_back(23455876319);
p.push_back(23605978623);
p.push_back(23666143999);
p.push_back(23728561023);
p.push_back(23810585983);
p.push_back(23899618815);
p.push_back(23956960511);
p.push_back(24025024383);
p.push_back(24113346943);
p.push_back(24220272063);
p.push_back(24381508351);
p.push_back(24515711583);
p.push_back(24696176703);
p.push_back(24746961791);
p.push_back(24809800639);
p.push_back(24892737279);
p.push_back(24981321055);
p.push_back(25034970975);
p.push_back(25103624959);
p.push_back(25198970623);
p.push_back(25305097087);
p.push_back(25474434431);
p.push_back(25602416863);
p.push_back(25771715711);
p.push_back(25798117631);
p.push_back(25825040319);
p.push_back(25860440543);
p.push_back(25901973727);
p.push_back(25946822239);
p.push_back(26007068927);
p.push_back(26050916223);
p.push_back(26078204767);
p.push_back(26108200735);
p.push_back(26146191323);
p.push_back(26190442751);
p.push_back(26239385983);
p.push_back(26305984895);
p.push_back(26359645783);
p.push_back(26434067455);
p.push_back(26544701695);
p.push_back(26616058591);
p.push_back(26686587071);
p.push_back(26783201143);
p.push_back(26857970047);
p.push_back(26884229823);
p.push_back(26915087687);
p.push_back(26953410943);
p.push_back(26997696083);
p.push_back(27047104847);
p.push_back(27112444055);
p.push_back(27137772479);
p.push_back(27165897439);
p.push_back(27200594047);
p.push_back(27240517823);
p.push_back(27286470895);
p.push_back(27345899903);
p.push_back(27404577535);
p.push_back(27467546847);
p.push_back(27555469951);
p.push_back(27663930615);
p.push_back(27719635711);
p.push_back(27804985087);
p.push_back(27919131743);
p.push_back(27953037591);
p.push_back(27987906927);
p.push_back(28037117151);
p.push_back(28091156351);
p.push_back(28160715775);
p.push_back(28207481503);
p.push_back(28241402239);
p.push_back(28288815127);
p.push_back(28340414847);
p.push_back(28403930075);
p.push_back(28477276639);
p.push_back(28558240511);
p.push_back(28679352063);
p.push_back(28773419903);
p.push_back(28865025919);
p.push_back(28993946847);
p.push_back(29027841759);
p.push_back(29063613439);
p.push_back(29113030847);
p.push_back(29167244031);
p.push_back(29242204927);
p.push_back(29282878687);
p.push_back(29316687199);
p.push_back(29364588911);
p.push_back(29416805887);
p.push_back(29481355647);
p.push_back(29555241207);
p.push_back(29636032223);
p.push_back(29765501823);
p.push_back(29850121951);
p.push_back(29948773119);
p.push_back(30070975231);
p.push_back(30116010175);
p.push_back(30168716775);
p.push_back(30233863535);
p.push_back(30318100863);
p.push_back(30369179359);
p.push_back(30417403263);
p.push_back(30474268031);
p.push_back(30553483135);
p.push_back(30642145023);
p.push_back(30750435071);
p.push_back(30893471711);
p.push_back(30991993087);
p.push_back(31141293823);
p.push_back(31184912991);
p.push_back(31236889983);
p.push_back(31298332159);
p.push_back(31381231615);
p.push_back(31439230399);
p.push_back(31483801343);
p.push_back(31542285535);
p.push_back(31616787199);
p.push_back(31709135039);
p.push_back(31808861439);
p.push_back(31960669055);
p.push_back(32053202495);
p.push_back(32211703807);
p.push_back(32264139487);
p.push_back(32331045247);
p.push_back(32418066815);
p.push_back(32502449087);
p.push_back(32561721823);
p.push_back(32636733311);
p.push_back(32737799679);
p.push_back(32852506239);
p.push_back(33027501567);
p.push_back(33147935487);
p.push_back(33302773823);
p.push_back(33357583455);
p.push_back(33429035263);
p.push_back(33527238111);
p.push_back(33593598687);
p.push_back(33659172223);
p.push_back(33740571007);
p.push_back(33846037887);
p.push_back(33976255871);
p.push_back(34137645823);
p.push_back(34280593279);
p.push_back(34367542119);
p.push_back(34394692223);
p.push_back(34414927359);
p.push_back(34460526399);
p.push_back(34499267663);
p.push_back(34530555007);
p.push_back(34564507007);
p.push_back(34629201599);
p.push_back(34648391743);
p.push_back(34669011679);
p.push_back(34699125119);
p.push_back(34749011839);
p.push_back(34781979263);
p.push_back(34812891167);
p.push_back(34865231135);
p.push_back(34922106229);
p.push_back(34999995327);
p.push_back(35082679039);
p.push_back(35185038911);
p.push_back(35253621631);
p.push_back(35341474543);
p.push_back(35437879663);
p.push_back(35458484415);
p.push_back(35483066079);
p.push_back(35517371751);
p.push_back(35568519919);
p.push_back(35595372927);
p.push_back(35624477887);
p.push_back(35686302591);
p.push_back(35715529663);
p.push_back(35739183327);
p.push_back(35760789759);
p.push_back(35807586751);
p.push_back(35845049071);
p.push_back(35876062559);
p.push_back(35917437951);
p.push_back(35978832319);
p.push_back(36039698223);
p.push_back(36139022063);
p.push_back(36244003775);
p.push_back(36297311103);
p.push_back(36396448639);
p.push_back(36508114479);
p.push_back(36531272831);
p.push_back(36561552959);
p.push_back(36613571871);
p.push_back(36658585183);
p.push_back(36690558911);
p.push_back(36746233823);
p.push_back(36788443823);
p.push_back(36815754719);
p.push_back(36855438271);
p.push_back(36913260511);
p.push_back(36946048479);
p.push_back(36982100799);
p.push_back(37052385215);
p.push_back(37151346623);
p.push_back(37249481727);
p.push_back(37353367151);
p.push_back(37467967359);
p.push_back(37582867935);
p.push_back(37608054719);
p.push_back(37636359103);
p.push_back(37689239519);
p.push_back(37733889919);
p.push_back(37766343615);
p.push_back(37822236639);
p.push_back(37866217055);
p.push_back(37890176991);
p.push_back(37934648607);
p.push_back(37988148335);
p.push_back(38020812671);
p.push_back(38058076127);
p.push_back(38134617279);
p.push_back(38237466495);
p.push_back(38334159295);
p.push_back(38433430255);
p.push_back(38547799807);
p.push_back(38658688703);
p.push_back(38692917551);
p.push_back(38740981087);
p.push_back(38804274367);
p.push_back(38856951135);
p.push_back(38929065343);
p.push_back(38964204575);
p.push_back(39021689855);
p.push_back(39078653119);
p.push_back(39133756383);
p.push_back(39227450479);
p.push_back(39350075135);
p.push_back(39487630911);
p.push_back(39607336703);
p.push_back(39733654975);
p.push_back(39768138207);
p.push_back(39819931135);
p.push_back(39881641183);
p.push_back(39935218655);
p.push_back(40005343375);
p.push_back(40042601951);
p.push_back(40100218815);
p.push_back(40155718879);
p.push_back(40217793983);
p.push_back(40305213375);
p.push_back(40435650495);
p.push_back(40569323391);
p.push_back(40691326847);
p.push_back(40811270079);
p.push_back(40858574783);
p.push_back(40940640223);
p.push_back(40991956863);
p.push_back(41075986751);
p.push_back(41122981759);
p.push_back(41205446111);
p.push_back(41255875519);
p.push_back(41346849983);
p.push_back(41495854847);
p.push_back(41647470015);
p.push_back(41803906559);
p.push_back(41903275967);
p.push_back(41960674111);
p.push_back(42031383871);
p.push_back(42097487199);
p.push_back(42165946655);
p.push_back(42216769471);
p.push_back(42295471327);
p.push_back(42351564255);
p.push_back(42461343679);
p.push_back(42619191231);
p.push_back(42782955455);
p.push_back(42950297743);
p.push_back(42970437567);
p.push_back(42991193695);
p.push_back(43021997455);
p.push_back(43073924991);
p.push_back(43106452351);
p.push_back(43137179583);
p.push_back(43191910367);
p.push_back(43229211583);
p.push_back(43255031151);
p.push_back(43276296063);
p.push_back(43324349743);
p.push_back(43363381215);
p.push_back(43392994271);
p.push_back(43439076735);
p.push_back(43501686575);
p.push_back(43564403503);
p.push_back(43659428463);
p.push_back(43763972847);
p.push_back(43825613247);
p.push_back(43925005503);
p.push_back(44025959359);
p.push_back(44046814687);
p.push_back(44070240127);
p.push_back(44103129567);
p.push_back(44158200047);
p.push_back(44186836735);
p.push_back(44214690895);
p.push_back(44278449503);
p.push_back(44308796959);
p.push_back(44330663247);
p.push_back(44358078207);
p.push_back(44406254559);
p.push_back(44443628479);
p.push_back(44472863343);
p.push_back(44526969663);
p.push_back(44583630015);
p.push_back(44661899135);
p.push_back(44744853375);
p.push_back(44847935807);
p.push_back(44916846463);
p.push_back(45004865407);
p.push_back(45102218863);
p.push_back(45133501375);
p.push_back(45165715391);
p.push_back(45231533503);
p.push_back(45263919583);
p.push_back(45294993151);
p.push_back(45366446047);
p.push_back(45390778303);
p.push_back(45420676767);
p.push_back(45474185087);
p.push_back(45519220319);
p.push_back(45552469343);
p.push_back(45611950015);
p.push_back(45685002111);
p.push_back(45802071663);
p.push_back(45911300543);
p.push_back(46010281919);
p.push_back(46108360639);
p.push_back(46187827071);
p.push_back(46212196319);
p.push_back(46258412415);
p.push_back(46310560735);
p.push_back(46343738303);
p.push_back(46391365951);
p.push_back(46445306847);
p.push_back(46476448703);
p.push_back(46509503295);
p.push_back(46574281839);
p.push_back(46607602495);
p.push_back(46641329551);
p.push_back(46712160879);
p.push_back(46798389119);
p.push_back(46898081535);
p.push_back(47013279615);
p.push_back(47120923311);
p.push_back(47245081535);
p.push_back(47280523231);
p.push_back(47325502879);
p.push_back(47391485919);
p.push_back(47446243295);
p.push_back(47519575663);
p.push_back(47557242335);
p.push_back(47617834495);
p.push_back(47677542335);
p.push_back(47740918239);
p.push_back(47829626751);
p.push_back(47959392127);
p.push_back(48090693567);
p.push_back(48222124991);
p.push_back(48332299631);
p.push_back(48370108703);
p.push_back(48433683327);
p.push_back(48489404383);
p.push_back(48559877471);
p.push_back(48611394895);
p.push_back(48653967327);
p.push_back(48723285343);
p.push_back(48772247487);
p.push_back(48859565951);
p.push_back(48964582191);
p.push_back(49124162863);
p.push_back(49225559415);
p.push_back(49375793023);
p.push_back(49430758367);
p.push_back(49499652063);
p.push_back(49564532671);
p.push_back(49649093087);
p.push_back(49699178431);
p.push_back(49768046559);
p.push_back(49832956895);
p.push_back(49917474143);
p.push_back(50064162687);
p.push_back(50218303231);
p.push_back(50367753407);
p.push_back(50485675967);
p.push_back(50537235423);
p.push_back(50617009087);
p.push_back(50674483135);
p.push_back(50754074559);
p.push_back(50805650399);
p.push_back(50885429183);
p.push_back(50942863295);
p.push_back(51054587647);
p.push_back(51217132543);
p.push_back(51376371647);
p.push_back(51541851371);
p.push_back(51579847743);
p.push_back(51646429055);
p.push_back(51714948863);
p.push_back(51812176767);
p.push_back(51850795455);
p.push_back(51922714111);
p.push_back(51990462207);
p.push_back(52097779061);
p.push_back(52251229951);
p.push_back(52410404415);
p.push_back(52614836703);
p.push_back(52653214047);
p.push_back(52718585791);
p.push_back(52787777871);
p.push_back(52884956415);
p.push_back(52923223935);
p.push_back(52991892863);
p.push_back(53061097951);
p.push_back(53169697791);
p.push_back(53322481407);
p.push_back(53479870079);
p.push_back(53688175487);
p.push_back(53739083647);
p.push_back(53827703119);
p.push_back(53909593599);
p.push_back(53990279039);
p.push_back(54064022879);
p.push_back(54142762879);
p.push_back(54272769787);
p.push_back(54498914047);
p.push_back(54683299583);
p.push_back(54797763807);
p.push_back(54881180607);
p.push_back(54951247743);
p.push_back(55048773215);
p.push_back(55110450671);
p.push_back(55199218143);
p.push_back(55308238587);
p.push_back(55493967359);
p.push_back(55712873471);
p.push_back(55865245183);
p.push_back(55961648127);
p.push_back(56084344831);
p.push_back(56158506879);
p.push_back(56271267711);
p.push_back(56417623807);
p.push_back(56673722239);
p.push_back(56913185663);
p.push_back(56984669661);
p.push_back(57096322943);
p.push_back(57210376991);
p.push_back(57309634047);
p.push_back(57430069119);
p.push_back(57643450111);
p.push_back(57889701631);
p.push_back(58038947775);
p.push_back(58168412031);
p.push_back(58290118527);
p.push_back(58418308319);
p.push_back(58592894847);
p.push_back(58909134719);
p.push_back(59096628991);
p.push_back(59224552319);
p.push_back(59348729727);
p.push_back(59468275455);
p.push_back(59627249535);
p.push_back(59916193663);
p.push_back(60144372799);
p.push_back(60185523807);
p.push_back(60268531583);
p.push_back(60335805311);
p.push_back(60419229791);
p.push_back(60465193823);
p.push_back(60549596255);
p.push_back(60629540735);
p.push_back(60753116159);
p.push_back(60952139647);
p.push_back(61104586495);
p.push_back(61225441791);
p.push_back(61272576799);
p.push_back(61356521087);
p.push_back(61440270719);
p.push_back(61504769919);
p.push_back(61557008895);
p.push_back(61635911551);
p.push_back(61729959807);
p.push_back(61875662591);
p.push_back(62046191359);
p.push_back(62212283903);
p.push_back(62315765631);
p.push_back(62405365247);
p.push_back(62478424027);
p.push_back(62569336255);
p.push_back(62646289759);
p.push_back(62723563263);
p.push_back(62849994623);
p.push_back(63075023871);
p.push_back(63257493247);
p.push_back(63386191743);
p.push_back(63467535871);
p.push_back(63540129663);
p.push_back(63638944991);
p.push_back(63704131455);
p.push_back(63791163263);
p.push_back(63907530303);
p.push_back(64106823167);
p.push_back(64312251391);
p.push_back(64461206911);
p.push_back(64564252543);
p.push_back(64694948735);
p.push_back(64765920127);
p.push_back(64881246079);
p.push_back(65064547711);
p.push_back(65308938239);
p.push_back(65520832383);
p.push_back(65618270143);
p.push_back(65739202431);
p.push_back(65822520191);
p.push_back(65937690495);
p.push_back(66090094463);
p.push_back(66345700607);
p.push_back(66588974975);
p.push_back(66707406591);
p.push_back(66843645407);
p.push_back(66949195647);
p.push_back(67093134847);
p.push_back(67382619903);
p.push_back(67652861823);
p.push_back(67769298815);
p.push_back(67914652543);
p.push_back(68016750463);
p.push_back(68153368447);
p.push_back(68440571391);
p.push_back(68720023057);
p.push_back(68730753259);
p.push_back(68745781151);
p.push_back(68759766503);
p.push_back(68775027803);
p.push_back(68792693711);
p.push_back(68813102477);
p.push_back(68833777383);
p.push_back(68856681263);
p.push_back(68877129963);
p.push_back(68899839211);
p.push_back(68925691867);
p.push_back(68958664667);
p.push_back(68989424871);
p.push_back(69000874911);
p.push_back(69016799135);
p.push_back(69029238439);
p.push_back(69044934019);
p.push_back(69062436327);
p.push_back(69084920735);
p.push_back(69104647783);
p.push_back(69126730923);
p.push_back(69148187387);
p.push_back(69170786111);
p.push_back(69196328911);
p.push_back(69229359055);
p.push_back(69261146731);
p.push_back(69292005987);
p.push_back(69320941247);
p.push_back(69361275111);
p.push_back(69403542763);
p.push_back(69452471551);
p.push_back(69524848693);
p.push_back(69548978391);
p.push_back(69577535831);
p.push_back(69615437751);
p.push_back(69661373011);
p.push_back(69704687471);
p.push_back(69767132623);
p.push_back(69799640271);
p.push_back(69813932887);
p.push_back(69829666923);
p.push_back(69843502911);
p.push_back(69861121501);
p.push_back(69878602047);
p.push_back(69899571463);
p.push_back(69922184639);
p.push_back(69942538047);
p.push_back(69965610815);
p.push_back(69988866975);
p.push_back(70018334527);
p.push_back(70051737503);
p.push_back(70068865259);
p.push_back(70083483033);
p.push_back(70099416899);
p.push_back(70113132611);
p.push_back(70131003795);
p.push_back(70149144903);
p.push_back(70169469459);
p.push_back(70194118559);
p.push_back(70213245467);
p.push_back(70235802767);
p.push_back(70261430175);
p.push_back(70291799039);
p.push_back(70325192543);
p.push_back(70351454015);
p.push_back(70380302191);
p.push_back(70416928575);
p.push_back(70464355947);
p.push_back(70505385599);
p.push_back(70568573295);
p.push_back(70611198183);
p.push_back(70639526375);
p.push_back(70672318271);
p.push_back(70715541423);
p.push_back(70764689215);
p.push_back(70813888367);
p.push_back(70869975855);
p.push_back(70886343639);
p.push_back(70904962879);
p.push_back(70922553759);
p.push_back(70944401359);
p.push_back(70972072919);
p.push_back(71001528797);
p.push_back(71024303007);
p.push_back(71052195743);
p.push_back(71085825855);
p.push_back(71125042015);
p.push_back(71144445163);
p.push_back(71166860687);
p.push_back(71181961191);
p.push_back(71204346575);
p.push_back(71226675103);
p.push_back(71254246887);
p.push_back(71278531801);
p.push_back(71307697103);
p.push_back(71338041295);
p.push_back(71374855375);
p.push_back(71410525427);
p.push_back(71445349071);
p.push_back(71491913687);
p.push_back(71544582763);
p.push_back(71606240207);
p.push_back(71676817767);
p.push_back(71711496623);
p.push_back(71753743343);
p.push_back(71809171263);
p.push_back(71863545663);
p.push_back(71941817191);
p.push_back(71957619731);
p.push_back(71976662707);
p.push_back(71993458803);
p.push_back(72014140391);
p.push_back(72042761423);
p.push_back(72066577895);
p.push_back(72093842767);
p.push_back(72119347663);
p.push_back(72150463439);
p.push_back(72192415647);
p.push_back(72215736723);
p.push_back(72233721663);
p.push_back(72250861131);
p.push_back(72274230411);
p.push_back(72296457175);
p.push_back(72322060207);
p.push_back(72348701769);
p.push_back(72378318687);
p.push_back(72403787007);
p.push_back(72444293771);
p.push_back(72480850407);
p.push_back(72515577783);
p.push_back(72553367527);
p.push_back(72612314943);
p.push_back(72665109407);
p.push_back(72747107431);
p.push_back(72781837555);
p.push_back(72818168783);
p.push_back(72870715199);
p.push_back(72926508267);
p.push_back(73005819743);
p.push_back(73032079003);
p.push_back(73054562151);
p.push_back(73082077581);
p.push_back(73107916727);
p.push_back(73137461207);
p.push_back(73171461983);
p.push_back(73210539215);
p.push_back(73254399903);
p.push_back(73289250279);
p.push_back(73314348135);
p.push_back(73335877279);
p.push_back(73362595037);
p.push_back(73391017319);
p.push_back(73422704591);
p.push_back(73459042255);
p.push_back(73501005141);
p.push_back(73550476655);
p.push_back(73590582135);
p.push_back(73641064023);
p.push_back(73704136319);
p.push_back(73789416775);
p.push_back(73849249655);
p.push_back(73893367607);
p.push_back(73954695087);
p.push_back(74028257199);
p.push_back(74093838503);
p.push_back(74118285119);
p.push_back(74140041687);
p.push_back(74165830887);
p.push_back(74195113295);
p.push_back(74227208095);
p.push_back(74262527951);
p.push_back(74303307247);
p.push_back(74352693151);
p.push_back(74374103967);
p.push_back(74396597711);
p.push_back(74424116711);
p.push_back(74449951965);
p.push_back(74479474583);
p.push_back(74513284735);
p.push_back(74552082239);
p.push_back(74596427727);
p.push_back(74640924263);
p.push_back(74689041335);
p.push_back(74742584023);
p.push_back(74813955903);
p.push_back(74898075455);
p.push_back(74941092967);
p.push_back(74996528615);
p.push_back(75063254655);
p.push_back(75148361343);
p.push_back(75183235431);
p.push_back(75213092767);
p.push_back(75246544799);
p.push_back(75283855319);
p.push_back(75329740239);
p.push_back(75372170415);
p.push_back(75430920095);
p.push_back(75455990959);
p.push_back(75485610911);
p.push_back(75519790383);
p.push_back(75560046015);
p.push_back(75602432335);
p.push_back(75650481535);
p.push_back(75705024127);
p.push_back(75766285799);
p.push_back(75836528591);
p.push_back(75936105935);
p.push_back(76005298903);
p.push_back(76070380903);
p.push_back(76152270655);
p.push_back(76240224915);
p.push_back(76270413799);
p.push_back(76301027287);
p.push_back(76336864207);
p.push_back(76374183215);
p.push_back(76416671647);
p.push_back(76471174607);
p.push_back(76511086543);
p.push_back(76542099687);
p.push_back(76573583335);
p.push_back(76609258983);
p.push_back(76646883247);
p.push_back(76692987711);
p.push_back(76745133919);
p.push_back(76806275559);
p.push_back(76863236023);
p.push_back(76944812975);
p.push_back(77045311463);
p.push_back(77100863167);
p.push_back(77175215007);
p.push_back(77267934655);
p.push_back(77315983067);
p.push_back(77330951771);
p.push_back(77347262415);
p.push_back(77361153755);
p.push_back(77379184431);
p.push_back(77399083423);
p.push_back(77420079055);
p.push_back(77444634527);
p.push_back(77465097055);
p.push_back(77487686095);
p.push_back(77514457039);
p.push_back(77548101487);
p.push_back(77579391335);
p.push_back(77591808295);
p.push_back(77609632499);
p.push_back(77621147111);
p.push_back(77637036267);
p.push_back(77656232911);
p.push_back(77680638743);
p.push_back(77699879379);
p.push_back(77721116591);
p.push_back(77747614559);
p.push_back(77767916383);
p.push_back(77798413359);
p.push_back(77832024855);
p.push_back(77861174819);
p.push_back(77889550951);
p.push_back(77923939815);
p.push_back(77968061879);
p.push_back(78016373935);
p.push_back(78069491615);
p.push_back(78122107479);
p.push_back(78152786579);
p.push_back(78184399335);
p.push_back(78224494511);
p.push_back(78270416703);
p.push_back(78320734127);
p.push_back(78384685415);
p.push_back(78397098447);
p.push_back(78414919143);
p.push_back(78426437335);
p.push_back(78442332915);
p.push_back(78461488959);
p.push_back(78485937751);
p.push_back(78505172895);
p.push_back(78526400415);
p.push_back(78552887135);
p.push_back(78573200223);
p.push_back(78603706967);
p.push_back(78637305263);
p.push_back(78658144371);
p.push_back(78673076695);
p.push_back(78689416167);
p.push_back(78703277651);
p.push_back(78721323075);
p.push_back(78741128087);
p.push_back(78762103207);
p.push_back(78786761519);
p.push_back(78807216731);
p.push_back(78829717359);
p.push_back(78856463719);
p.push_back(78890154959);
p.push_back(78922728091);
p.push_back(78953722995);
p.push_back(78979093943);
p.push_back(79022849855);
p.push_back(79062990655);
p.push_back(79110931223);
p.push_back(79178858303);
p.push_back(79210896575);
p.push_back(79239497535);
p.push_back(79277663191);
p.push_back(79323996775);
p.push_back(79366789039);
p.push_back(79429671855);
p.push_back(79463916939);
p.push_back(79484710815);
p.push_back(79501255911);
p.push_back(79524576207);
p.push_back(79547770207);
p.push_back(79575666591);
p.push_back(79600621519);
p.push_back(79629731355);
p.push_back(79660889051);
p.push_back(79698593071);
p.push_back(79730024851);
p.push_back(79748136575);
p.push_back(79765639087);
p.push_back(79785737951);
p.push_back(79811437015);
p.push_back(79836787175);
p.push_back(79864630507);
p.push_back(79895037515);
p.push_back(79920871595);
p.push_back(79961902943);
p.push_back(79998256615);
p.push_back(80032868071);
p.push_back(80074578863);
p.push_back(80130486191);
p.push_back(80184837307);
p.push_back(80264542827);
p.push_back(80299108327);
p.push_back(80335971815);
p.push_back(80393573303);
p.push_back(80447081659);
p.push_back(80530754463);
p.push_back(80545686771);
p.push_back(80566374887);
p.push_back(80583090907);
p.push_back(80604050919);
p.push_back(80633505767);
p.push_back(80658841503);
p.push_back(80685671039);
p.push_back(80713289647);
p.push_back(80746962847);
p.push_back(80787023807);
p.push_back(80808017823);
p.push_back(80832130783);
p.push_back(80847089615);
p.push_back(80868771815);
p.push_back(80895696319);
p.push_back(80920820943);
p.push_back(80948215727);
p.push_back(80973967311);
p.push_back(81006150991);
p.push_back(81046478319);
p.push_back(81083619255);
p.push_back(81119174463);
p.push_back(81169927999);
p.push_back(81221275455);
p.push_back(81285908383);
p.push_back(81346437039);
p.push_back(81382514607);
p.push_back(81430398903);
p.push_back(81482718959);
p.push_back(81543598543);
p.push_back(81609646311);
p.push_back(81635923671);
p.push_back(81657603667);
p.push_back(81685318575);
p.push_back(81715792999);
p.push_back(81748670415);
p.push_back(81787178191);
p.push_back(81831910847);
p.push_back(81875713999);
p.push_back(81898737343);
p.push_back(81923151579);
p.push_back(81949005743);
p.push_back(81979981743);
p.push_back(82012298447);
p.push_back(82049443759);
p.push_back(82092586847);
p.push_back(82142435623);
p.push_back(82184270951);
p.push_back(82242002279);
p.push_back(82305474239);
p.push_back(82387804015);
p.push_back(82444858319);
p.push_back(82491869159);
p.push_back(82552566703);
p.push_back(82634098263);
p.push_back(82687826215);
p.push_back(82714162279);
p.push_back(82737170727);
p.push_back(82766539351);
p.push_back(82796905767);
p.push_back(82831777183);
p.push_back(82869376599);
p.push_back(82917435343);
p.push_back(82953032999);
p.push_back(82980493775);
p.push_back(83001694623);
p.push_back(83030594903);
p.push_back(83060709279);
p.push_back(83094355887);
p.push_back(83132330191);
p.push_back(83180426703);
p.push_back(83223381991);
p.push_back(83269611735);
p.push_back(83323914023);
p.push_back(83392503535);
p.push_back(83484476647);
p.push_back(83525841383);
p.push_back(83583655743);
p.push_back(83646740223);
p.push_back(83728539503);
p.push_back(83772399519);
p.push_back(83802644951);
p.push_back(83837134055);
p.push_back(83874982783);
p.push_back(83921483727);
p.push_back(83970315167);
p.push_back(84023295951);
p.push_back(84054679887);
p.push_back(84084207295);
p.push_back(84122301399);
p.push_back(84159598031);
p.push_back(84205689759);
p.push_back(84260171727);
p.push_back(84319084223);
p.push_back(84377263935);
p.push_back(84458907599);
p.push_back(84560093103);
p.push_back(84613996351);
p.push_back(84684387063);
p.push_back(84779803551);
p.push_back(84841469415);
p.push_back(84869415887);
p.push_back(84903239631);
p.push_back(84943406311);
p.push_back(84985819039);
p.push_back(85032877935);
p.push_back(85094306963);
p.push_back(85121157023);
p.push_back(85149994911);
p.push_back(85187707863);
p.push_back(85228912543);
p.push_back(85270203343);
p.push_back(85327142815);
p.push_back(85380404183);
p.push_back(85437240679);
p.push_back(85515509375);
p.push_back(85619168159);
p.push_back(85678235567);
p.push_back(85744977839);
p.push_back(85835558767);
p.push_back(85908172031);
p.push_back(85936063447);
p.push_back(85964500599);
p.push_back(86000817751);
p.push_back(86039657311);
p.push_back(86086688507);
p.push_back(86146514303);
p.push_back(86184606427);
p.push_back(86209172183);
p.push_back(86239481189);
p.push_back(86276060887);
p.push_back(86319572863);
p.push_back(86367330015);
p.push_back(86430795615);
p.push_back(86486738295);
p.push_back(86558148055);
p.push_back(86661955199);
p.push_back(86741817727);
p.push_back(86808732119);
p.push_back(86900989183);
p.push_back(86982525261);
p.push_back(87010174935);
p.push_back(87038717791);
p.push_back(87075088087);
p.push_back(87113899083);
p.push_back(87161097055);
p.push_back(87221657311);
p.push_back(87258567803);
p.push_back(87283502219);
p.push_back(87313665951);
p.push_back(87350552415);
p.push_back(87393915359);
p.push_back(87442185951);
p.push_back(87506110303);
p.push_back(87560905299);
p.push_back(87632918231);
p.push_back(87738662143);
p.push_back(87816372467);
p.push_back(87883530455);
p.push_back(87977024767);
p.push_back(88060569063);
p.push_back(88093585119);
p.push_back(88133871575);
p.push_back(88183724895);
p.push_back(88237893471);
p.push_back(88315474907);
p.push_back(88347411643);
p.push_back(88382140127);
p.push_back(88424694231);
p.push_back(88480214751);
p.push_back(88542645215);
p.push_back(88618225471);
p.push_back(88702539223);
p.push_back(88835931775);
p.push_back(88909388475);
p.push_back(89011183231);
p.push_back(89126153055);
p.push_back(89159272091);
p.push_back(89195369431);
p.push_back(89244389847);
p.push_back(89298517247);
p.push_back(89371451103);
p.push_back(89411138267);
p.push_back(89444896607);
p.push_back(89490879959);
p.push_back(89541351647);
p.push_back(89598541663);
p.push_back(89676532543);
p.push_back(89752191927);
p.push_back(89867842559);
p.push_back(89968181491);
p.push_back(90061250175);
p.push_back(90195506503);
p.push_back(90235076447);
p.push_back(90283006623);
p.push_back(90341443917);
p.push_back(90417715423);
p.push_back(90481831295);
p.push_back(90525918967);
p.push_back(90576930623);
p.push_back(90643403983);
p.push_back(90731246039);
p.push_back(90818344663);
p.push_back(90954884319);
p.push_back(91063980407);
p.push_back(91185856127);
p.push_back(91288323575);
p.push_back(91332223863);
p.push_back(91383685023);
p.push_back(91450337119);
p.push_back(91536809631);
p.push_back(91575642071);
p.push_back(91623262111);
p.push_back(91679722463);
p.push_back(91756406623);
p.push_back(91843778007);
p.push_back(91946876543);
p.push_back(92094424535);
p.push_back(92190839255);
p.push_back(92342682047);
p.push_back(92394110591);
p.push_back(92459495895);
p.push_back(92543585151);
p.push_back(92627917919);
p.push_back(92682155871);
p.push_back(92751284063);
p.push_back(92847300447);
p.push_back(92955638271);
p.push_back(93131663199);
p.push_back(93252064215);
p.push_back(93419939047);
p.push_back(93471592919);
p.push_back(93537914687);
p.push_back(93623549791);
p.push_back(93705429975);
p.push_back(93761094911);
p.push_back(93835519327);
p.push_back(93930354175);
p.push_back(94041642455);
p.push_back(94222245503);
p.push_back(94339077023);
p.push_back(94493705667);
p.push_back(94522948047);
p.push_back(94547809887);
p.push_back(94586429247);
p.push_back(94626657535);
p.push_back(94674195195);
p.push_back(94733483391);
p.push_back(94774763027);
p.push_back(94800608895);
p.push_back(94831482771);
p.push_back(94871560095);
p.push_back(94915200855);
p.push_back(94965390175);
p.push_back(95030909499);
p.push_back(95085142643);
p.push_back(95165841023);
p.push_back(95282275551);
p.push_back(95345017075);
p.push_back(95416747607);
p.push_back(95521111679);
p.push_back(95581071743);
p.push_back(95607592863);
p.push_back(95638533223);
p.push_back(95679419495);
p.push_back(95722520315);
p.push_back(95773380319);
p.push_back(95834511131);
p.push_back(95862963963);
p.push_back(95888446707);
p.push_back(95925282295);
p.push_back(95966777695);
p.push_back(96012894047);
p.push_back(96072224607);
p.push_back(96133538935);
p.push_back(96198163327);
p.push_back(96288747739);
p.push_back(96389605107);
p.push_back(96450470775);
p.push_back(96538295935);
p.push_back(96641292087);
p.push_back(96675025367);
p.push_back(96711556959);
p.push_back(96761334687);
p.push_back(96819432703);
p.push_back(96892430175);
p.push_back(96930789111);
p.push_back(96965298135);
p.push_back(97012474839);
p.push_back(97066920187);
p.push_back(97131363711);
p.push_back(97207625591);
p.push_back(97291896735);
p.push_back(97424350463);
p.push_back(97499029311);
p.push_back(97600372351);
p.push_back(97716458335);
p.push_back(97750427475);
p.push_back(97789583847);
p.push_back(97839312607);
p.push_back(97896755039);
p.push_back(97969842015);
p.push_back(98008632539);
p.push_back(98043027167);
p.push_back(98088834975);
p.push_back(98146814555);
p.push_back(98213412575);
p.push_back(98284314239);
p.push_back(98369627999);
p.push_back(98505760127);
p.push_back(98578070783);
p.push_back(98684151647);
p.push_back(98797065447);
p.push_back(98840277975);
p.push_back(98894171039);
p.push_back(98961198943);
p.push_back(99050680159);
p.push_back(99092913311);
p.push_back(99142934103);
p.push_back(99204775775);
p.push_back(99286867807);
p.push_back(99373909463);
p.push_back(99489824383);
p.push_back(99625326039);
p.push_back(99727572607);
p.push_back(99865085599);
p.push_back(99909982071);
p.push_back(99963121239);
p.push_back(100028278359);
p.push_back(100113861471);
p.push_back(100163516375);
p.push_back(100211428439);
p.push_back(100269381471);
p.push_back(100349093727);
p.push_back(100437659455);
p.push_back(100547179743);
p.push_back(100688875383);
p.push_back(100786779735);
p.push_back(100936116183);
p.push_back(100989238623);
p.push_back(101058684887);
p.push_back(101151960927);
p.push_back(101230924759);
p.push_back(101289391063);
p.push_back(101369328847);
p.push_back(101472800575);
p.push_back(101589464279);
p.push_back(101760290623);
p.push_back(101890604671);
p.push_back(102027074975);
p.push_back(102086195711);
p.push_back(102161303391);
p.push_back(102262308223);
p.push_back(102321716959);
p.push_back(102387213271);
p.push_back(102472310015);
p.push_back(102580425175);
p.push_back(102717723999);
p.push_back(102868752087);
p.push_back(103029445471);
p.push_back(103091362719);
p.push_back(103115826283);
p.push_back(103136930255);
p.push_back(103183809919);
p.push_back(103220982735);
p.push_back(103252243407);
p.push_back(103289465807);
p.push_back(103350346859);
p.push_back(103370228383);
p.push_back(103392282859);
p.push_back(103422124887);
p.push_back(103475989815);
p.push_back(103504952655);
p.push_back(103535308607);
p.push_back(103589486511);
p.push_back(103651781867);
p.push_back(103734663615);
p.push_back(103815872319);
p.push_back(103914241215);
p.push_back(103990447479);
p.push_back(104073285439);
p.push_back(104158914399);
p.push_back(104184946591);
p.push_back(104205525043);
p.push_back(104241901471);
p.push_back(104290158555);
p.push_back(104321417023);
p.push_back(104350510911);
p.push_back(104415121311);
p.push_back(104438891035);
p.push_back(104460326503);
p.push_back(104488328095);
p.push_back(104532844495);
p.push_back(104571427279);
p.push_back(104598208415);
p.push_back(104645415775);
p.push_back(104707528251);
p.push_back(104773262127);
p.push_back(104864142511);
p.push_back(104969082995);
p.push_back(105029885759);
p.push_back(105128469099);
p.push_back(105229558891);
p.push_back(105260393263);
p.push_back(105283831711);
p.push_back(105344483231);
p.push_back(105381343439);
p.push_back(105414020927);
p.push_back(105474924463);
p.push_back(105513291055);
p.push_back(105538235343);
p.push_back(105583945055);
p.push_back(105634952399);
p.push_back(105667759339);
p.push_back(105713775967);
p.push_back(105784825663);
p.push_back(105898133935);
p.push_back(105998873903);
p.push_back(106085502783);
p.push_back(106201922795);
p.push_back(106304382927);
p.push_back(106334848395);
p.push_back(106359176331);
p.push_back(106421124959);
p.push_back(106456383295);
p.push_back(106489486507);
p.push_back(106554476447);
p.push_back(106588323035);
p.push_back(106616532719);
p.push_back(106660601135);
p.push_back(106709801391);
p.push_back(106742859615);
p.push_back(106791129951);
p.push_back(106862509759);
p.push_back(106974194411);
p.push_back(107078732207);
p.push_back(107162890047);
p.push_back(107277957039);
p.push_back(107380228381);
p.push_back(107415410023);
p.push_back(107473927647);
p.push_back(107529778079);
p.push_back(107585616751);
p.push_back(107653640143);
p.push_back(107691388879);
p.push_back(107748370255);
p.push_back(107807054109);
p.push_back(107867739551);
p.push_back(107955314231);
p.push_back(108084866927);
p.push_back(108217716071);
p.push_back(108347647151);
p.push_back(108456558511);
p.push_back(108494129447);
p.push_back(108551608271);
p.push_back(108607291007);
p.push_back(108669493087);
p.push_back(108733046703);
p.push_back(108768140327);
p.push_back(108827287503);
p.push_back(108885139263);
p.push_back(108952784751);
p.push_back(109037584247);
p.push_back(109169954623);
p.push_back(109296622183);
p.push_back(109426554735);
p.push_back(109540035679);
p.push_back(109590017487);
p.push_back(109663422415);
p.push_back(109724131167);
p.push_back(109801876719);
p.push_back(109847517087);
p.push_back(109928876335);
p.push_back(109980976591);
p.push_back(110085099199);
p.push_back(110232062319);
p.push_back(110383816511);
p.push_back(110559919551);
p.push_back(110630796927);
p.push_back(110696227279);
p.push_back(110762458847);
p.push_back(110832899471);
p.push_back(110894915263);
p.push_back(110949971743);
p.push_back(111019820479);
p.push_back(111086991263);
p.push_back(111200845679);
p.push_back(111373483839);
p.push_back(111534978991);
p.push_back(111671652899);
p.push_back(111692501919);
p.push_back(111715834783);
p.push_back(111748358095);
p.push_back(111803896939);
p.push_back(111832013263);
p.push_back(111860363435);
p.push_back(111923900223);
p.push_back(111954483103);
p.push_back(111976350251);
p.push_back(112003586619);
p.push_back(112051634127);
p.push_back(112089274939);
p.push_back(112118472655);
p.push_back(112172595663);
p.push_back(112229252983);
p.push_back(112307189679);
p.push_back(112389811311);
p.push_back(112493558327);
p.push_back(112561908087);
p.push_back(112650137455);
p.push_back(112747398351);
p.push_back(112771550111);
p.push_back(112794176059);
p.push_back(112831021983);
p.push_back(112880013215);
p.push_back(112911704991);
p.push_back(112942702495);
p.push_back(113011444943);
p.push_back(113030839515);
p.push_back(113052035307);
p.push_back(113082193823);
p.push_back(113133391679);
p.push_back(113166852959);
p.push_back(113198002079);
p.push_back(113251740111);
p.push_back(113314518191);
p.push_back(113396072367);
p.push_back(113476959935);
p.push_back(113577766075);
p.push_back(113654388023);
p.push_back(113737137983);
p.push_back(113823841183);
p.push_back(113855139759);
p.push_back(113890147279);
p.push_back(113953333151);
p.push_back(113986674923);
p.push_back(114022446415);
p.push_back(114088086763);
p.push_back(114119385007);
p.push_back(114143529887);
p.push_back(114206743887);
p.push_back(114242556299);
p.push_back(114275592031);
p.push_back(114343331743);
p.push_back(114418208447);
p.push_back(114527683759);
p.push_back(114644197183);
p.push_back(114757090027);
p.push_back(114859136303);
p.push_back(114910352287);
p.push_back(114940770207);
p.push_back(114991529791);
p.push_back(115032909663);
p.push_back(115065805263);
p.push_back(115125593483);
p.push_back(115167046607);
p.push_back(115198187423);
p.push_back(115234068383);
p.push_back(115296150635);
p.push_back(115329468379);
p.push_back(115366668251);
p.push_back(115441008111);
p.push_back(115543374783);
p.push_back(115636551535);
p.push_back(115740090287);
p.push_back(115853807423);
p.push_back(115967897039);
p.push_back(116003200359);
p.push_back(116055674319);
p.push_back(116119309519);
p.push_back(116174819247);
p.push_back(116246256591);
p.push_back(116284196767);
p.push_back(116347226575);
p.push_back(116403365791);
p.push_back(116473777487);
p.push_back(116565109879);
p.push_back(116702713775);
p.push_back(116824361527);
p.push_back(116958353215);
p.push_back(117057683263);
p.push_back(117094133375);
p.push_back(117163784983);
p.push_back(117213115855);
p.push_back(117295453023);
p.push_back(117340441039);
p.push_back(117379128119);
p.push_back(117446981071);
p.push_back(117497910687);
p.push_back(117590482095);
p.push_back(117710921583);
p.push_back(117850846447);
p.push_back(117966919103);
p.push_back(118113331039);
p.push_back(118156963791);
p.push_back(118234847135);
p.push_back(118291865327);
p.push_back(118381745615);
p.push_back(118425234895);
p.push_back(118503237471);
p.push_back(118560079599);
p.push_back(118653331375);
p.push_back(118800154431);
p.push_back(118954761135);
p.push_back(119105355391);
p.push_back(119211601103);
p.push_back(119270557599);
p.push_back(119341930335);
p.push_back(119413210591);
p.push_back(119479951039);
p.push_back(119538952031);
p.push_back(119610341215);
p.push_back(119681367535);
p.push_back(119795093423);
p.push_back(119975902079);
p.push_back(120126738287);
p.push_back(120264930143);
p.push_back(120308645751);
p.push_back(120381043551);
p.push_back(120446420059);
p.push_back(120535011551);
p.push_back(120579604095);
p.push_back(120655826847);
p.push_back(120717887327);
p.push_back(120832892543);
p.push_back(120997453183);
p.push_back(121164069375);
p.push_back(121337943391);
p.push_back(121380416631);
p.push_back(121453065563);
p.push_back(121519160959);
p.push_back(121608110875);
p.push_back(121652434847);
p.push_back(121726018907);
p.push_back(121790555999);
p.push_back(121905077887);
p.push_back(122064289407);
p.push_back(122229324671);
p.push_back(122411960159);
p.push_back(122463703967);
p.push_back(122559730427);
p.push_back(122648883039);
p.push_back(122714410847);
p.push_back(122804140543);
p.push_back(122872774395);
p.push_back(123014364031);
p.push_back(123237980863);
p.push_back(123452382591);
p.push_back(123521897311);
p.push_back(123616625243);
p.push_back(123686043119);
p.push_back(123773228895);
p.push_back(123849560991);
p.push_back(123924432735);
p.push_back(124051002555);
p.push_back(124270402943);
p.push_back(124457746047);
p.push_back(124592731999);
p.push_back(124695029599);
p.push_back(124824180959);
p.push_back(124891860463);
p.push_back(125003103487);
p.push_back(125163420023);
p.push_back(125414444863);
p.push_back(125644661983);
p.push_back(125726969759);
p.push_back(125833748943);
p.push_back(125935579999);
p.push_back(126039103821);
p.push_back(126174125823);
p.push_back(126432308735);
p.push_back(126657477503);
p.push_back(126778014207);
p.push_back(126907066831);
p.push_back(127024603039);
p.push_back(127149670111);
p.push_back(127374376575);
p.push_back(127671237375);
p.push_back(127830626207);
p.push_back(127960052575);
p.push_back(128082085791);
p.push_back(128202903391);
p.push_back(128378203903);
p.push_back(128687656767);
p.push_back(128869543775);
p.push_back(128914169279);
p.push_back(128999070159);
p.push_back(129074818911);
p.push_back(129145014939);
p.push_back(129194794847);
p.push_back(129275663995);
p.push_back(129370099071);
p.push_back(129507655039);
p.push_back(129687880443);
p.push_back(129845280507);
p.push_back(129953627391);
p.push_back(130006714303);
p.push_back(130083786591);
p.push_back(130178836319);
p.push_back(130228342399);
p.push_back(130292259111);
p.push_back(130363668587);
p.push_back(130466777787);
p.push_back(130616323711);
p.push_back(130781150847);
p.push_back(130983370111);
p.push_back(131046375135);
p.push_back(131135777631);
p.push_back(131217628543);
p.push_back(131300593967);
p.push_back(131382576479);
p.push_back(131454496607);
p.push_back(131588300607);
p.push_back(131819654783);
p.push_back(132008705407);
p.push_back(132110193867);
p.push_back(132204925035);
p.push_back(132274175471);
p.push_back(132363991291);
p.push_back(132441576287);
p.push_back(132522491615);
p.push_back(132645789503);
p.push_back(132877319807);
p.push_back(133060316799);
p.push_back(133190465999);
p.push_back(133299457887);
p.push_back(133422251743);
p.push_back(133507129247);
p.push_back(133618902879);
p.push_back(133825183359);
p.push_back(134073982783);
p.push_back(134252822271);
p.push_back(134356079967);
p.push_back(134487002015);
p.push_back(134557080959);
p.push_back(134672070495);
p.push_back(134846478207);
p.push_back(135092660095);
p.push_back(135317135039);
p.push_back(135442958175);
p.push_back(135577241503);
p.push_back(135695763295);
p.push_back(135845346943);
p.push_back(136134508159);
p.push_back(136386930527);
p.push_back(136506077023);
p.push_back(136641584991);
p.push_back(136758634335);
p.push_back(136905162367);
p.push_back(137193873215);
p.push_back(137441268951);
p.push_back(137454034987);
p.push_back(137472544971);
p.push_back(137483363531);
p.push_back(137499977143);
p.push_back(137518940887);
p.push_back(137542436683);
p.push_back(137562635135);
p.push_back(137584058735);
p.push_back(137609371487);
p.push_back(137630368831);
p.push_back(137661587295);
p.push_back(137695176603);
p.push_back(137714409019);
p.push_back(137729869879);
p.push_back(137745609387);
p.push_back(137760085879);
p.push_back(137778058615);
p.push_back(137798203291);
p.push_back(137819591255);
p.push_back(137843856727);
p.push_back(137864717119);
p.push_back(137886957935);
p.push_back(137913609071);
p.push_back(137947252171);
p.push_back(137980065019);
p.push_back(138010511127);
p.push_back(138038449087);
p.push_back(138080020343);
p.push_back(138122051311);
p.push_back(138170290559);
p.push_back(138242523583);
p.push_back(138268584191);
p.push_back(138297127995);
p.push_back(138336131775);
p.push_back(138381398683);
p.push_back(138425377467);
p.push_back(138488386159);
p.push_back(138519672183);
p.push_back(138535110039);
p.push_back(138550891319);
p.push_back(138565358603);
p.push_back(138583311703);
p.push_back(138603445855);
p.push_back(138624725087);
p.push_back(138649130651);
p.push_back(138669986075);
p.push_back(138692071535);
p.push_back(138718842415);
p.push_back(138752438555);
p.push_back(138783369051);
p.push_back(138796119179);
p.push_back(138814503135);
p.push_back(138825468059);
p.push_back(138842018923);
p.push_back(138860933271);
p.push_back(138884471391);
p.push_back(138904444511);
p.push_back(138926118959);
p.push_back(138951470779);
p.push_back(138972439603);
p.push_back(139003651551);
p.push_back(139037261103);
p.push_back(139066393811);
p.push_back(139094661175);
p.push_back(139129670951);
p.push_back(139173672503);
p.push_back(139221418879);
p.push_back(139278235839);
p.push_back(139326663991);
p.push_back(139357078551);
p.push_back(139389403159);
p.push_back(139430546367);
p.push_back(139476461951);
p.push_back(139526488671);
p.push_back(139588813079);
p.push_back(139605587419);
p.push_back(139624422459);
p.push_back(139641987131);
p.push_back(139665150615);
p.push_back(139692626487);
p.push_back(139722182127);
p.push_back(139747927007);
p.push_back(139774888319);
p.push_back(139810938159);
p.push_back(139854980363);
p.push_back(139869896855);
p.push_back(139890599771);
p.push_back(139907310699);
p.push_back(139928277175);
p.push_back(139957732023);
p.push_back(139982964215);
p.push_back(140009830623);
p.push_back(140037454559);
p.push_back(140071151791);
p.push_back(140111196443);
p.push_back(140146652187);
p.push_back(140182459579);
p.push_back(140231658863);
p.push_back(140292300527);
p.push_back(140361337071);
p.push_back(140411049659);
p.push_back(140446593847);
p.push_back(140496887831);
p.push_back(140551143871);
p.push_back(140617860991);
p.push_back(140666274607);
p.push_back(140684511031);
p.push_back(140701807727);
p.push_back(140725194923);
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 |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
