MTCTF2022 Crypto 复现

发表于 2024-01-18 更新于 2024-01-18

一共有三题，还是很有意思的。感觉不是很水啊。

strange_rsa1

题目描述

strange_rsa1.py

from Crypto.Util.number import *
from sage.all import RealField
from secret import flag1

Bits = 512
p = getPrime(Bits)
q = getPrime(Bits)
n = p * q

gift = RealField(prec=Bits*2)(p) / RealField(prec=Bits*2)(q)
e = 0x10001
m = bytes_to_long(flag1)
c = pow(m, e, n)

output = open('output.txt', 'w')
output.write('n = ' + str(n) + '\n')
output.write('c = ' + str(c) + '\n')
output.write('gift = ' + str(gift) + '\n')

output.txt

1
2
3

n = 108525167048069618588175976867846563247592681279699764935868571805537995466244621039138584734968186962015154069834228913223982840558626369903697856981515674800664445719963249384904839446749699482532818680540192673814671582032905573381188420997231842144989027400106624744146739238687818312012920530048166672413
c = 23970397560482326418544500895982564794681055333385186829686707802322923345863102521635786012870368948010933275558746273559080917607938457905967618777124428711098087525967347923209347190956512520350806766416108324895660243364661936801627882577951784569589707943966009295758316967368650512558923594173887431924
gift = 0.9878713210057139023298389025767652308503013961919282440169053652488565206963320721234736480911437918373201299590078678742136736290349578719187645145615363088975706222696090029443619975380433122746296316430693294386663490221891787292112964989501856435389725149610724585156154688515007983846599924478524442938

解题思路

$n$ 的大小在1024bits，而给出的 $gift = \frac{p}{q}$ 的小数位也在1024，那么 $n \times gift \approx p^2$ 基本覆盖1024bits。至于为什么 ‘ $\approx$ ’，是因为无理数变整数过程中有精度损失的问题，不过问题不大，解决办法上也可以爆破。

n = 108525167048069618588175976867846563247592681279699764935868571805537995466244621039138584734968186962015154069834228913223982840558626369903697856981515674800664445719963249384904839446749699482532818680540192673814671582032905573381188420997231842144989027400106624744146739238687818312012920530048166672413
c = 23970397560482326418544500895982564794681055333385186829686707802322923345863102521635786012870368948010933275558746273559080917607938457905967618777124428711098087525967347923209347190956512520350806766416108324895660243364661936801627882577951784569589707943966009295758316967368650512558923594173887431924
gift = 0.9878713210057139023298389025767652308503013961919282440169053652488565206963320721234736480911437918373201299590078678742136736290349578719187645145615363088975706222696090029443619975380433122746296316430693294386663490221891787292112964989501856435389725149610724585156154688515007983846599924478524442938
e = 0x10001
p = int(sqrt(n * gift))
q = n // p

d = pow(e,-1,(p-1)*(q-1))
m = pow(c,d,n)
print(bytes.fromhex(hex(m)[2:]))

# b'flag{a5537b232c1ab750e0db61ec352504a301b7b212}'

这里的 flag 同时也是下一道题目的参数。

strange_rsa2

题目描述

strange_rsa2

from Crypto.Util.number import *
from secret import flag1, flag2

def generate_poly(modulus, num, root):
    poly = []
    res = 0
    for i in range(1, num+1):
        poly.append(getRandomRange(1, modulus-1))
        res = (res + poly[-1] * pow(root, i, modulus)) % modulus
    return [modulus-res] + poly

Bits = 512
p = getPrime(Bits)
q = getPrime(Bits)
n = p * q

a = getRandomRange(1, p-1)
k = bytes_to_long(flag1)
gift = [generate_poly(p, Bits, a), generate_poly(p, Bits, k * a)]

e = 0x10001
m = bytes_to_long(flag2)
c = pow(m, e, n)

output = open('output.txt', 'w')
output.write('n = ' + str(n) + '\n')
output.write('c = ' + str(c) + '\n') 
output.write('gift = ' + str(gift) + '\n')

output.txt

1
2
3

n = 109378672508048135963067490399488700128935926221280999153728844885929604845257426753717908439401874480024019118872754964261258108802571658255339464890951241819976505839994513576969957522261002976457875212789578122239936311323485029004004912939615422858758136864345993327406831607042382680866135088327787314829
c = 61096919929881310428894191710952858437645791015485294654216810138762365245120062231010883735176746978988525785740831464359931515321125687001265045043159129956161430769831055702925714734122241244821002610843626827278607544140144147218576488074446083867851070586032996978232665711198148263862578701336391259501
gift = [[5427094460745472513593814790243139230026320357992492902728810995081053349454308946008416635445657899000855266472167839129495101472281709819578765877508334, 3659753770713515104438717002369092210983243997726518470157715995904031367307112152623885718173000315559168347405966155370122642619140595935099712886900029, 2771718158411886260624807584148482499076277008370807860195384738386946463894609681647156387215117854732506453647913225451721574589741556932406708826480583, 4839508482251668561826534869483621571823696936064296259490472377786306591292411150322538411254090574445173450257859112647310296473815822761683723031365666, 8192716547770587839310362320145694758895069600682953185672510355539089258563772951223148260225583248091143982146079184852220534950827218762594517471425106, 3705885639764540562727152188573846387951562091900805741694702876675514336652120517330912655986361766355214283039445407144731030511370922697720650839042884, 7242262436882661868316925636203263738800345312340108455842019070934141047094701026311774690730199062086269124033233167362570586232788786949618151602033700, 5613045859428988038749655700549273995973590966288156410924028250464874416830723423274793918804722458908046845356603570838852171891009477801666765401740615, 8103452282915737457382606396732739504067996236907931550851401015136921073984503203849410710591499489210699144271779748763093071456984188682155852904907087, 7988504483666488420445351269107060119213416874953238825364298715218766065003479337106464268344596807547920947017354143222429229145065218822226572443533244, 2754163461208203664576107184293744819122319303016059827799496508478435199539183332108144071632257221582454920473180752073463761477679247023729139710044582, 5297841410559812304652102809801213403340834555035728004063846117087921364835152931741250074591143848704571132532633559410893980696742994384993068557980013, 8674691757302312940403872699395246631205901515134756479685006176079195981185410741062402375431683953083567450804351203486623411084645817197227477032530834, 3141450219046789563667689861249509242938442226779664279101832973672919347817887205410722873180868826865331267871826406089418972003256435407887268010001064, 1918075323093221354079490612350475943951319964473881230087478656746080284253876126040621631396265876541701307568188944386094785259550008451149380525984288, 5118965189766897877863394373271458279858868539429125884982195328391751457704095145301002598126165522345967319016246498037184291520240136565807335960660016, 1184685164185331139004976381073320943902240418268117800210058362615284109368325773142468208795415129465784675421225862883141979659250558931716700140956256, 2649769352962272556480698191538996897508459223382004970480640174431696048132772372223760318410924688794907982653050007624916681025668290041325265146963010, 4324044139422813464708811806114987540900680055808777820132113065367226999710329350680461801032473435766559869911004227733791685228606518056910709038248496, 8334405900269336364601118840982290685589640748778389317173395511553146284952237814202069748562378283085790512661437811116421433220298708508745090033316375, 6974407600208086751351188659291612075228498316907547611326988707077073944198551040680974086650275651522194892430557819432561513420911688755679048541398539, 1015699516006156447840934030568707632653692322619960079466769578682666960664750960806775500869983033941476461244103330044166463705025692989293353577803491, 2722995385228778698070273867729273222364539928031679488531646041739812359330385111679755615695814608566074844920312210113206201051367038769279081974509261, 8661967989577808443465144306368439766693734335349312258230728478983667298112711072221619787831385893616845943564380033004618043306628442706460193540089098, 8139646911594681152997749836632098372853696378411523354407553904570676321519209058808107376517162936413925990462206258653803447615672820515101109341419223, 1949709757368791951559875347594321173062889391038503783817637509309210362080377452821128174493411584772082420539233677158973447412304176932027263850463338, 999303915113065643989306193782643512910091960408974565889335266119033550484242825672787431650435560632945429082677388255080803090335857257066036682485087, 8731959002784171751117666240151336726138687615717951389905750628130311478204199445779471087189032302791275973489167319526217240108573269625798515431984699, 300491291368080479213894773872665342633630825308833289090675398104083852119050541721732653306896255896808185687817884800935474916789218890491182333604797, 618191477519714557845945209322365841841289911346759921904334650557410207834263650786416222589684642965626951603569108233658243743969149060616311112203928, 7885981133538522738688268842142791677865918471793846930048447360955287931817540296065155193664572838876455271570118192470800166960775869948023726046562603, 7240987138692759799628562117246037077704557193483773802468185428324942920136597943742451812483731659152374103461577502381439114503077364396684589578496681, 70573727649781403224679602461294643697569836281321908853993089075564115511260222407305571970738203692175154606619135854947817554194952779271157766056778, 5843794970306350571536951293450872345720336841252406700322625105396015675057126597656098813837587225661077319690206735852847818963838552339533500906407485, 295958101144092812092723194144611361420313051143769406202178679966246605228342853494480829877954257296969881923970984008534003143257592629732041149686718, 7101008917765843080973775218399223558273627575555771193965443436181005906213577167418928349920178458421150302528966027925196326117779058821420154036534336, 3235911542970864286937055646502181174834989247904694015955459055679244023935847210117517087507069141974006060636737939364706576737603239290858372130197949, 5622989102769561469876294742124070831472139940203371936235168653516187861584589381425038606215809371553203622410945189759164195239476890449044751119415305, 1229069100970048628741366373000827090698672589180318955389726889536022340522989477637349259226111665747151694639738009190536144780963938057103876900678421, 8792790542038446141270179777108797025896203587240700168403963647185967084199748410437133323352123759299593622714604699359812158172414769525315045139309831, 7743407072769937355093744811415636593488766513147767137619777706616827393975333569832657176984216211153085601813516406042814891454222314896838825624793470, 4489360908752348972859176805034070947262295713222556899712436246553551536078070077765498981367477223018754381608518830699669413468886142036378734506936420, 3827094088100707179590757460877586470939809215290216062399380974205493326764083872194604223302562725434122357023295842278558416588576827061576225510846235, 7343541280658560542621066646825675151600883306530343807793469940804466798490581164356096430842915896359706874704188763774615062109598059629646511473729969, 5226729846421240006725573196787596245247720170548456063220431356015332016618043937460484938185699808923160817140379131515859432788197366531607991629139739, 410948123929147635350066597784735696488205306930880615397364015367449846041856733719169925051570288530150078140820444743934387227859609702543331090768334, 2949351837660529017601529933694684984335903574541030000417679364023913164029243743292345336035180971569675460160775952879986872224382925576865428833991117, 1247221319380745778753350272699575000859336863814314674048622218737518045469146528181141618233265498521828552092126303555150290253198040496005410138463994, 4524277668732435037495922654973862780062022134271983675959274609625268857135480127543069255516007346716391069076404499228156623271904182219312031978739519, 6816532994167722569751545883747508887132958448813006048215089258235438546886212870069016580337736157014896227538048413500367374543624946260815702453175161, 5337590384278906735655771491324731233316180546354607186049839303323695510689045441403207595443888441940559701684014325093967280764007245479756614510301354, 6139207438550856376936494519685879832207045646132140435476315931327685173596140136822413468371694836034718903707276658315425892827939858885041631370736025, 6950405135977477974033649315934558178088627656479656053531071656433346542631835445814167352899266904962752662815117095167674988141990755171562315874831612, 2088281613807738507566795794705470926534707929142487786381801158888152073892672498186893617701473475732524297507102573346400419502584079991561573912090450, 5680859286584086014824384202850384542912251144944201693956276239198636464532484604952351530606010401811279198868494058061450908551682749978139705087468339, 7983082929753570770024419226172839462961021921375801694864690786916552712936815921104221214133302207320569824081225136767170235662582264433340009912561853, 5473518387137130915661835318038405824217671552820274510632022524632798553380883871539859913434443976732344912891418159551745569439074417787478158991304198, 7358447190862276196905135140395596752972624751589996398439411771966618059808796684259736922828187217853487282916673896203588291238432401075538231358457183, 5156835833772001482398651125597619829054091677188058089598285283644485814448169930379400117732803925865339792149330518219473761894388854116216197783509345, 6844779441000988337204283016331918066478362748551748769105176790069526752419387574790088771703504095235466005196588240535279638380408625126979963829819740, 5101882692405795263416440141641951704169721937914653978981195780530424936133316119169167316354749580473663705049560007449853912216086376425323183312605630, 3374571875107157689092328312173893343207111354656523667568935847899982751632335960026968514769265372801840496011046402975953999248479173077186586825718393, 8676119768098799417341283977003493829225035721485741650215717055192594324783159555191996846295666131440553886662972364574976403345864393639295282168607383, 457853114617993432823735133783803798123127341151230474342351131136233493669479192379832103401189285016701326723251304255643877464148459173868296003885183, 8562533180096815206735608019913449786773492127272352951711161337803348539754285238185657134518122729172475242166403549506680769380199131352046495851663821, 3309809700456698416904490173000432922707818868751967949299450984905696810246597436211132689739699347048601781507016273550695086935502779749023260119179832, 7385627596911334442871698254789267994244605338387462642042161502013470331146624041121818771442848269902503350898519915252649589681710648560965861877988917, 2113787728440875983952323812426263212621632500312980999366593565547217820010291257326608244255623305440501463319268529324024685088322893159770674707933809, 4462815769432021175207417524023355077357274087042702307009852962575749918692078105610333946963537120072377515006513422438610039282188124295751994213241318, 8374983517828002330507661989421205240962084543570653833316160049009703923652305601767843098213891575590598457143027883324544638450554085849759377937276789, 6050468252416784560052140435395239980509665683554247853981302418870309447496992028237090097469434724234408288823798704725740925519868047583196031465564205, 834181031417120541044134825888167126399968614515640372838764744205240503716696463424818001914098989872579840970905667654550551895151887007678758399677704, 833565533134890554678155421185947022339210763844039481251290639681904466255028439411245596328598805521535226954162589225908828881832708824218700069858808, 2912009622814941205034275727576732382736306648132557559705336581627063576186793152321395316522977799313857925449464250195244555713227741554066752460997255, 3878582437986841165153871151384775911768992914467003795785978204068029733542627398987973525311201725658651705660700693524336143059688666305696908283380866, 1846534818787936946721060196506475369510509279624669704551964001463813344014931449284118829708557899849968881528023149187543984528022441027052713590900263, 5370327520091204589842363089609452484804506280615251646567424469945493291502868652223657393771453334503419202436087866082229665000163661645907420840279133, 6449395573364194082138151578723816799997056233966396762405939036558728506586346725747686120289590617251484371738007298429995659960475442510616323500211242, 4757881226219036276754744484662997917848888272666041917648749968161877275335207518431234620205541754287427841394966175020036763832960875638279151695746113, 5987912019479065374404145860752597494344678096135208776023899275988250364020820991399648844560388034949050908475879496469949981148420443850268045802919185, 2794619921992011452815185631713612807170860934839437203850861104092458715050552767287808851792513070524812492807516103355599200923694256212327866272058861, 1271538151500614405732189010046058147872483472280508639578826683985683639412232384096185132496916648711019167078433041359438892414685855961671007951620936, 2957999335958738077661071215833152390196569624881867446271479893146800798388534205514029781787022927675271118626916569564062443945335806489628832872986273, 2489873701435290892113604492166321970661112367127092308513059789342007573500892204517416594239295155796525846074753235146402730041644057106859670366364593, 8544822098211948796529794221829016997693537856695753582544986375767429255900382260461868825029617847488763332368978646728668006702646221062685629507827911, 8719198609118861474903109485410110709321227778346343205119342415643912586475547803970452850816938021694025713524141586226395209195849356247834510227244545, 5055025465563991948499339863430542097839935404067633242119282349436701336103378388099141260537422673129650660331222870599282451217579360966246496750563793, 8526068042644041910587833203878176278915530987821285945957873989455884810790284355700081382314910706959363838142666775905904032477862575334026414502248768, 8770559327924339310537590459704471305738482670030590540116972564915788694708017546041284328342486737179364784051371303037237953787785017698814395950964931, 6568907083381127146770994704103355244380684878689660429833721384340004452042241990627190995912408410785891564475671758547330970913489127016608768864831314, 5952955876089081079839064259611490232988847139782754528889680317747131712191712206374816225101500123157070216448917860851253747077931034648054744686930856, 6606323636966973978645505861706951287802675489483757990388627740302148583694571161382275167279725078658930716597350690868580241989559842837285889376786257, 7205968103842868269583809923501498023321445359796827019007596599684578094952240775867506920168580289808940045045293952097654682975186524840995459074527320, 167314832186482465807489400256283947163887785572933816775175495684789285935814739042663982060728543381268227857379406964114895948747301319523872277245256, 3967992268571539410696027581420764020192697278168720039093579790628146384106941147324218366291265984126559202949612696326147221147808741133644903622768108, 4569532082142928453913305684900873814836754495720117327192318361198738097909877608677503283404529613422905264508782418807129956411531324133159179907446493, 6250654363752414979782306104855138400660179715843247026011898744276561033889140582386654556519671636633790445524519048622842199200017206428044049701504093, 4605487472019237838314631554795043409741010665895250598061768754199679709083692471962022724738810013616335252055813995424814964506107303145681704552229053, 6998305923302975706217157029183402370843461584915334729487924601972273081461772322086966050666851253706605995973594774850625708686039140186024339813772890, 4884811997366819857768685108974106793270077124112857267446452731624661436388298237204660861717381302104562089783393285504355646234955826576683775189265980, 4340430005832259393693117671316517396378035006546519999557455377948410764589739789454681629092663726947245821490649018198107207281762982588463599820840634, 2812959538000543687350345470490318298080273558796968636039929138071891076059992102960988698252609767795285066121934507803031820790450282628621021578162859, 7822437172223233146999107283419055641582260408017186055840669355599543942530890257473291324030624288658618230101646862036515368610230460652238044461999950, 69299084505374440658688410802929270806699265979593546334666245816849649641473144430777230386655008465870428011344185630839511701840821696791119117817755, 7695315549743789374011630142044097854503155746908569835003276389634391791906460476667407857399137011468686869919486358344710737167393435196112510397553413, 5829833440902514158445043046084967469824241891823636918679215914539146325957411621031955556348191609789669124837510475608335456774113490426076143568098731, 37733081223065109370747991749900264169068054139992113292256957749356074695276400106625769283954663952899226008469003213416427560544518926963774878352431, 479774861694081815410983384058441425989217755537554848476859552725113705567698722739260065035538086533095287665949313726456889553075349010120836982502395, 2318455003369600307728457816117888647429318897862222778269548397566396963975969686471503894565216772800619311614806763572040863944147382536126783679515784, 2484079269726284648848371381238197009242177392171897538514816085326004922076621007112141726448739705049543649620113295636329485078990711253888601487241155, 7512136281074265981510038210684023621807559535049397265486912808766247270865756614494991165357930706944184384494625392394673295501657875101062864295863999, 6173436054660314148620312816562216477505027366319189135987543590110858012420200709603496857540981861617046873477031489666739986848149189686223582854035086, 6365410425510128056047551104409542269523712429275943333225260225807508573852239737116054715839389627713748253469865768381267420068690103056362015640355252, 1836936882971476123837314246449863709997205796168260708762814317241378080654770958197085779786426261315120839795801345499569068424370926979766531821135063, 7745861634074944112793479969678708515884967326405997335743155875359993856114844752888106330968655921225564465083239964414850101363516960170341984149648736, 3240836266703539185188621399842500722866078714209081472670491721124498050133692476691231432432539589085636538417423506857389060595968699412451458272229023, 6463458936553972112817828500010677682282819391555052257941997667560381222840997699014401662781924237419154492222697536088989933794819262175692130751221922, 3572829713408416066088566754005266085258102277569497199816057642874591826736273938912215332160320551245219126971305998726629542744892926611032533133345540, 255131078341038405826635226230583032291856271468479276829714119536471611849235196211501042311580914030799778930473747616147873414875367339595959199598342, 7357737996708478439832457656408620272224146089534134900046183961014671060163755643007063717384732526312490915556633086585108989896699405944821465969205857, 1935084139033231252831557739008203747124873349425774157155069035011704693095465987401663708247381606936648201971880718701379259330044713234382728397341566, 3474070307432018016345618584552385495698151508582061395426324921392228236115833344613085768399178162983179218765849987340883147876942124783926273200169456, 1554465236452996304914897124036313641926166941589817420397823662373290486530925397176353775168166512484327865756338976314635937106908521776633407294549950, 5002163385685932990697470208563522933230506439441747559210067721809425507583266838784070280784914984510201957046297231383520251978258983404363178843508633, 4414530670977226389646094760338812189075035273994889866314447126984414538805351569729183309731428071585176416802804111602447833191381002268641562156018739, 8836246696825655768345933510905877983784812225892937987242504395622554328741055840752582715704861589279901289069405622746442349815756369909642261605261076, 3947114427973901898168303542725341175683566641898312461301353519238972287312874928709389156542002078173125869010179838747120395927579389399897955219262724, 2859209417546076854977098151125423189696443041148594520394935661783076053754096409146627359054050930890690721719031209129718049721519857166501785603197769, 8254896535401906778088665753617821659709978993075752276742988385404818002505266540826098035702498712085110656034073591894438523677391461716102539398801531, 1360508308949013614536255849022502827468339820928261837139335118815640551094941105361941420861717949326284427987458954944674877042529867096725404156036534, 1979420045570773962289880721728459789264181723170356622541065047445635209537061455580277618516218634331928159713925488211115564729153993044495374662017304, 7064900831994839305978603028773887608980918932291031952523711078457205156181297692216432072088294206028099829924911072758366796475259355220320828371215602, 1934081306896662437276475077609963144767085693344122875094009374295662806172446869179126649229103039759251711595732750369744580379179884285222329276089101, 4671953152432954074619829113706234820674782641078740330089059188660888556030113527651584695660239899452363064972403007787046807980053259669938840826912864, 8818083378479414011372807876023494100665545202118963347279721085917560922850997567792796425812317970898271627398789383370821913120042213212921362140486343, 1836366263298176029735564000678454225698473503580710829323410317109215011788440132250552587878664705409909785426399313780938516858814556904069910261834051, 7842961692259167079888424504544462105987454770292688246084685222192105630626655903058627981999399915911860490915620448393594406243726830845916421108925230, 4153399577676027241233879369364797517821573330146539310104038733248361988059713284849937720620595813028991787830374744572937446378615245200716064807279101, 3065459836664722906617812535227174505853774112277996450850458088677374217198372759524550902569783890712199315941581578796238717590597171778999724370760789, 474569318911880222628787498994703325283471411548809004850711281646633584530714413319894989472448992170656478794849320256415019360078446166817701165298751, 8577895540091214088574025948261529158364797680154371642058802253111232394182799606210843962426569463626760826409017768210969153193302404795597491134281418, 7477519133750195300278041665762264065087965808749618677064761913233984670280186831051098254943502470730568389709799632732344389987331084217610965760023759, 4328855859433790016361939155366323634291513962054701830358585893581078007425423974543333881339513943653161487884358671437169620790330890960436273396992789, 6434175195010159196792096607677909136638356080632818217768833835617142218966025648201588338738752615405398369956267182307366155250226618341137246129456003, 1429441661058981788529532242286799111184743134428722021870194637186612586080960888548924080161387606571990238272880932729576816426677666775230483660557445, 479078728411203357147023198344661760436280768912412865704567628355408763771200680522624123093918761890053206635151775954939159248496405479925509171068525, 4879853700592220998501957353756404099702697829431633055532306780001459093338885834701851502422594777289086786547443319479087768014470818131823528017699312, 7824020875001557217855788808158378814089426273518397777366443862043150693520823790113363940944898736683905316232620187210006445602825811134008475120112877, 2817259883764990645635607080715769659657702362458258669741681561040725042752812075700530571586205582335378714513394548784184832836497919661147792716952612, 8683210684472674609747950731768813918189209862193008862847922356336293432394091065057391288114031961704120837713741537563092783171226914221001827483831068, 313421217144003466361315939060013329705598262173872504399447695659883369638844308572312223911995880165409520263501039169909939149108636869589805843239271, 4663627889286815319054923926763113486272343680390668034522188861269524905478222028720980557208705633078244656410564045621954643289063432025954534950699794, 4773616604872961739989852370995388196205895864955107828668017685722806318010904886686709681715965505654448116304175186818273947811642880630746845814865539, 7798776104648351662666955455302853659721880801461193796177062370832206587574291062797556462765939361757667110470025952836973672378777698227943842839248752, 107055736910285374929373473653492729453876473621090056891000963135602620087713123937769824615175595290240202929834150595587632817591952860175083986458299, 294010887714000925910894914079098249522014194003595041494424101486526091422740280918333615998136918592078266420162127769780720349141077236244357210775933, 8193643602229338924626985552051375904489302016043605127621551548517521556641172021970727737286163497726494708434741194954907076256005036419095553882774663, 6456418822976253506706916106156875769635574661701115926137403623518469152368545748953439419147545920419757304256539415080210733870806115818674776481587634, 4537363887235138226166142769578258921537746964367783276385937389425494366834445745449714215570344345355128156775164635455029336251920129281717920695360692, 5300839483324774217285694935318554869686893777209289570365164651510478714778114791830591290989813930461663520197859193391592692742283770865968940717233774, 4171504010617422554690200675992185887338177587999242449529035901791735748089135259729170301694865998173918543749744480513044419773109478052325336757689059, 7912361144680503732918279758821858270381347715237451548858427722432843923088435673514626365086769440315983250464122742661609443212474475361542988480819035, 6596615543412858058246536171927452910459513683830566522404607874296934477715674615461856736258439158264492967499850389382240183470508731510806429504379636, 4663389442772551246968470288438211111793954317414947660269677480964819649918277587665413145770912717189082088904058296996762586366883003066383690584237568, 2080834440501921286942976439110187897604551747909179133144743019269253576473707990317305186688210195849728812433224885427410519936496271192748231861852653, 2551460255374382516853947723252069510549622634093858695735796707067575606095276716586214137204931322220828639135575127239245088893455071109750514241933296, 4229756985821581544898829328523535450460190178100854804584122379385224322414267745004095287587888464545289913602723577217599649816503833125416620841924494, 4671409727051430268801481135756765814260669539266620603323338408965265919428300488280074865249596003862069537640697383582133704446640972250252671242059930, 4109230881736472024258094762252839757705067328719294812138111780694775082839018784862535215368872756965426554744800529437323294474238654957883161219363265, 208932081814195624508081789625380838442643827362051954752504220173734491133780078242081396422147993806141922892703671497797022880867575375402588347678898, 1703863393146181618043171862621899784118484227315305106061553317916124268031547278493702894302444770688318390953609322439654654735636044559415603917458323, 2073460985942099771055602388805859815448452113116125207936981324228697723290248793767207225299934092149914672626695133295449021782532118051145131863824742, 458457461712996471831819155721396889860384123825795499860309595489373065695145181251758728485368848630900677426716348820488339352995727280812326733814486, 4538439538935856870040784604639335381066442549214610075445191540876889299596196537028234475865049168467563236775346288923206103735091328392407032138707661, 6469740562076593283269916445266486894745108395982274080393900535538164763102003819031626646238914208625456959207349998255308726543838710811980842366185436, 8641065974375587969393310916828815407503086399896513440339130762200711297115805885306003978640295254168655723967384527452015674100331595983801511144956179, 303858994759849430620106439196252076135511081715482144413186661955708048764535591450629553330787967371565028479895243549734855820148205520320736048365767, 3825892491829933177832279040031654773125233619946513931447230683138220136981183640802163883399109223574956786680066380692036982432154391521145631671180782, 966798719167703035581957246860182980954043010096131132592413669435151377067596523551276806607010314110178686155147833261824871441175038512128996901007553, 8125985332305291324469818677001752508356538920557977971724787470996289454270858551373143679996923507630700956385731858887291684189514277663051793636434853, 5969113476377903341439988479060926574549041799502060396152113063544409275967928520930504250464603373354150201532303143126092736883708981025237317077735028, 3663647796642032714280073014486647491636699242261182270174428659345747254353754459098728984224210452071536895498819600839803874854773334881266768140324831, 8836090193833414784699360865357928884468967110456414366275141083036337769822630443710141488064361894495727303226033932816595396801379537864203518304867185, 4273446045701792919650608668044170533379471611133050662273935055884488717791491093464513817755488906428226925889410281775620298045484511774469610501079419, 5218514070366383040148627479774497617507407040827746313423205879770726844715021030453434318643855735325971586944052661647583599709547328540094779455610775, 4791149481404899208692359828261117852198882079096812774149782155645048399157086700202966654272229686159125207783263994446644681253171906761996705134788849, 1673885594007342340671465631681067374575817339350399353240073305947812639897454165153472446869309066445019562584103679034726464307963338056506694230605454, 3520924776936982012798608222872162609831692681124383685212076012661696266238256212565426545901684857234193581185752894075178779744940219515854277384750649, 3610711363274807612587486347242404546772991398190143506308046870387730096356635810483399840610448254364330959351850414087022541534580393389438330334589836, 4976404809682707590540662323935474663534671338630489942798260300718007443138783205893158193392860646711583291724419756904543360790757053366867050276008263, 6346093747214010769174343252637351466174962058839371168443061185400526754351261043047222916932430840123160282086871643117987655070587804893773704084729018, 5371842131128247165055349552254415002206685370955388491251732856819420073032235599316297029264449887557428149421934406365749311080619622193603394722771045, 3455569969548313460997589951281039794156844671358794468343759405205663535148209672959070290160322739000205124847376696828980023355117529155748848861479036, 7796686120570455360582585276452269292022742358383829460120644956357500542837783688627667285661879067954088534797762782419273799033110579484199759357995499, 146060225315438674632539905288977158572004540720715149698357898148694184241965430586553032366213897448683395378974128823199037394366366176979095205659159, 8643419492860627526672215667011025831277049122026437066417830377675636844537906741422524443079139153360732808180890795837926237105201176869609292298463953, 2908687746500200732289382479585291811072920070463076389443044143653207043209885094842343564781268242686465473998000873684779598596743727259566571627715188, 5232916547846259815126501661280815281682913480788165934348617342747798045155412292869451198716964186305907058053559815526761753573806532107219137142425107, 6094525128830557499411977958834983243249505629830301084294965912630785656498142891534738338280526116453253834855243794811513512031185269275671249437173155, 7603935575825742277164179994166529766483156626060244846075392690489595193553781260171779041129719553320517188019913431185164921540579557123739972863182245, 8149209190061470095866785721227758102145095877941878596601566467149739552992166102223978323001941404122044910956212423735905473280199420824614572362165100, 3372590071569472625987826768823677749173100691143456183872104490977904430983281046915631019453293906740350500490933709124067662352506721051497733068468201, 5879861329700063174897577192895920245575126086814284260098644062199241254007401900204459414861991203505318256907098164063624790005164242318236704539592616, 8691128610906877223027751831450467455950268001024870667738288550247667499645316702640423864120505383016962428927069700423070065429590835559169919192191213, 5453309114358013628833028231044475744759702385527076688160738383313462917320112725322754453800856380309777793553465734051188908983046640127394859703157054, 206768780685852196902488224761501594813251658789972858060797790292846407593136968607824919499147987129114749111753221027295392118741900875612652304818763, 8453308285530096757490401003091868027829451577660353473466319761539468042740508141559058830791208711924234071746013970253513923843236332232448827207038281, 6306579114643413480552501791362140374051502379959976902498709016935967655190183063247582683104946063165147744266075702303048315711265258012591591338720828, 3152410849604417533696433929034587923802816800447094717789941543515463215510135067191025688729054062416105926341411763087544614539691977657087194105451792, 7477299326505921302335193238363367412499923273895709455198005474070481728880294552642223533789028453443106772272786388769396892339214231983683809884205112, 4503249049607657419890039219159212454861520327088063011549045837162445938064025293035349348883125823843696159347473503835025316068950289356805363139971249, 374717559231584583300905132963284249189002406339131724390279720741049702998037529029493809190824939001821346988417740229000727305675299623367461251011041, 5590463836036526867776387104005256274432226889132941346969499738019396965082865901291152489641806441170226469455668123741860326209790310533096973448449502, 7990460202572387502392814818406162580661428629829748970630343588268083892488583974967507753171647361765901080336591578037316433417499076218868361434639086, 6525023071234986771935294492993618273243531484169550599253695438676952989370738179284521055498324431541755984307760393907787714043805039980813833978702256, 1701720473437802325511355474167158662007034885183537692491246559572282610536111321700163086234875178042729290908561019777152407832268123102598642043425188, 7421097600172239667099703607100184027655001597312922014345917105792975344392847727984985679198228334891535102324048868509386079815115400416478493017828406, 7433067919738623188613987753166027204881941753046440829416252852349659993865129869957934234736208760864731772586050146621264492976899513201813173151969590, 314787582293935922598708935366733926181085798950174203665156027412208569896338957395106015747618825175168153581165162732601943664140877563095680341309406, 3132610059618456467808970806108539518721941219802928164528319593150326324953818983504463382566201592633256711039315936186690889996676265458348403996481177, 6993083657051733294632382180105349058521718362980880426999445266382579550424509453801200236273547292333361339428143895673849404633142374109686936628837192, 5303365832277439497093344484001489314767712281078542492748007520119582225709501208798060658726806785025627954790812818338166134900380291653143200905666243, 1506455442416971367101099973791699389703667819481737122179152214471839197776904693022455879612893031793000440133276207700780291991766270425661100494774837, 5003867525484815366083054193993861295746526434146320258221744682037824941706755177126630858617708834175336380017967361692403674541269454309388406079836076, 4885349457654311361661519946808249726505242269185111478973960072009075692456477375567625793752029365681023742429546482093090292854074374961932190340090768, 8625935566970452559534520058487318614120175680415961333299333530563522138534977326808520198589818187457370689897527643334371370649748677168210349962263969, 8379227511426820269871451652601470959369521730922181067516536351965458376595043917312641553329193608320442883151334691802036027122367504183761931257022828, 1169373061150536200039472591044957575519337181505725404858045377588016114080837031473435482466286027862707161570535156629375828190402988077127578028256989, 1799517725416635313454117611274346729726529694289099997182054756446811557607766922521872832803499502973837369268137128193733645006285284140158542055210426, 4331547065477570764632299216685036382785898032886597855058209843762394585032628948557452692985320911361807666027016360899592858127161019367604126928694540, 5348051104821264195485525398740340831017038905482268137721141379918827342830489524766382429577763823959122468011167078504894984181927845856778357488909422, 6029335051326365757696120315691953007687076145748259895731585807107193778431264936922615288758396432897301613914374748406835029989325649634239171178600487, 4108196305230072409219822072538665033986883720851484971235261900871206900920665986255429031293274201212504783443312766980784774880968579263522857640546200, 8345061401034245011288927973913086828399905361822028721006546321239477311226163384693370481587630120985486317108244232517640195009132916207197425770750757, 5213826819643032329934437081874107026347033837811269608122140619132416209940928616813978978354569292336096900126937269591294375196091202598971279913946893, 6085787909235257769984617534863877211890366042912449791947126413301455828658476214061873353103723934140710444993692859974363931919314293504823131194420976, 8824901869739856329117668917812452921653879696029265286836525998672756066924880409621532289568888901673708717815354894256622207510350108643002506485732177, 7986899486941981648180889372637959844191819131084573270184263427493093683970548490152215995728749865476316187957804278856733886041758556744474537256487324, 1530871504700998773230889308717012386196664871108636742583317876070356844353807848527159261098827562355619299487635431993986503375011681695219326543990248, 4755233278641411909483796257004436706234578638974783479808437405526897133093457396830501876788867200062571784772006091744531071092054687687746162599319409, 8403634975018145551679379884729766472110862480230933197491173747023161930573870696184908003984750049661180133813827386126463431569776842690528110900819854, 8638214401204576436588563802539195882066871543047571930608382351138461413355250864209372171386347648516142737134038982089068908103668235475774423580054695, 7298030926357251091547700831182704991229273888263415875884607304475032748869759160233777188136884592325575333152801366406963705455456033570459404463668325, 785187493933403494205716390888265912160617319567856482872300083389257472108480967817924944674915879787935697092182423643016100867443107804476140824294493, 7276859464970546746140430615447164601253007177403500988854258185824159300797891789327186459394059808317593676370037605071028056438360199574553989244903357, 7546439123566741332763958156542195773375224710811071888449662292404507735272380501018588608856735607525442616151123779255121405211488971604348667654575991, 310333753057458420130091330785563622169565659834239264736491854001539917253623209536195933582180197326427277128929459425259327645074138431726666989120603, 5010616386296282427950221980316485170352962115403092005410313782229345577074581120934493844403138463500826669576535318434347909865715680551774958333121457, 4412505565984406764360421574900863561670345903721505069921597599670823168645600986727818639115592377715169967789643389454114700341578535718483514050067537, 8008547842649544803416231002194318547051356073808760052679815299121649500692033620579712238691002306175172292008380993247165558670997654973110557558760278, 1575049552431588056517635998670588166287189956500690781568779965098585152526477643510122443350784878521602085094862440323327186613238716635527696248555701, 8394926894466325375749139753950872425768002559608279812199814863878396642506341985984970370738771385328736000861934623977935648844401185553292989946619962, 2814928708938513109863335245937311920234481116480270036860592421408334273346394458016842117553879199481644439378272899129904875070345976636596540084410345, 6092926254415738021309493820807759893626076984167442526726245406092120822284627133692909249618668317594010374514388311264953655826409975092302894818690505, 2116901809033799921107659489778535945812636785777579167044512590880628630931828956628966077121897010652380034838385828141480248996840694060505608450021855, 3362680476451345269058608726891774877882673734687857385925380295413959016589936990092763247330841947541426517502435342886130021133506432751782061493333322, 2529120930684767196353918764774083990069973366390893794709547847119930970861958317840507970497732675991714699386059804849513681420106453407564081071797766, 6049132520018083875107708495335138917525798333647989391267703501650317408237645345089571598828475251915254621415961969651677935094574616653992573003481012, 8746119530541922052097160552045878173114880611610460438017571546454723529321608197856593756017970913455105652172349867130925527754860765128120531128908745, 2738623339128273629497107350654963125338736659896303244938445500741513055613578804303287379030720725252100090004316467927856053630358229518829128078012607, 4878920768443498718022594791078581350008674640739648718258821236042603831778610559431235468858322602106816584738313819420995973988962822769716685224755031, 62029796413979254879303328426292759463226361997054448760303210834670766956209517716129229355271103377177087207280272571736460209979789500688245839722008, 5255580103620922250833951933172302277075664601239699412014464325266022522148589942045013662931211372666128771010264721788060254289829850257074123134333771, 1552236907658737988082939464542186966448930390810059901028756974819009066474729727900190466103169395340725142418611007169184953115148839634274454941434003, 5823330202400467468201298761744979420878272728199888903948072856571894584824937626360665798289181359085033815450336492538056126074800183906553022346934882, 988571381929785489162657997264856799382930883094831124389397586960085084518728262310934820631990062099890914796721504297745715854019670925784587735645574, 4736134367629786227096432075555749791210139338865620543950539027367472477854895382298615769474299918284552318009186015959103039248404289044698286912219199, 1176435742356706794139650071128194875208556675105924042142705410837501686095194307733089977708134233153160512560399211741317675297193373278048371075530051, 3253262386633509570278789597507900908335435611565352236862175689284662735814027510354519650462194143220613601819961465825107790502809551307336397587551040, 4917836975247609861214004651296930087334737082161325512846328245928429469400276011076855758987531852973099134957745394418732461302589568013254722531938503, 5899836393459224993230578726136213184113187439372683335117218978008779666328976574126902853747832895082694256172182899877106264213746042237744150975309059, 7210848493304107905909304645595376981368230586351678710185507882066803311118568429075212263329474347517014079619216118980501599840041308938948859839005054, 8366627690930574895630293458257430616621617717731558840235641655894760377885230323868869351248534469932122386044631427619830432402982932961850775185981908, 5064447098687503043750149912274216286610748788833570895176718987690185795543101701243606773665099530162947626356402852231937181941290557688000381979944587, 2983731994442580906515125289569195482406296081945101828167847247882902475962489579510418421914811417433556586807291492480552854951754813960046873514105002, 3281215567075698880671593190640113817371108526361569148696516457145466682209731832283470211832540479325230560673811700509510024662050165861007192443294258, 1916167086394436235517060516117296860245387329101882029043845155736820350573498305677600077071255417156693052424405321559160441413475295492102038970348994, 1215368335230248157056992609671829958063426248051063227792637787221593328842314706135324447516671685244147941262885197966101816544971392494498872185635669, 5545457487326799595147411952088460978944148512080980701055547144198118407385644845273961604738120787924941108705105996282157040557872771417071872707935702, 7291379615841717313539815343210824744224292078153885416684025623375016985830821649516595406500481602501664482851276566053747333261567418759256347614941480, 8462434030615373660974194067520295299623640767548264618171163110595718504624326313099653650538518424969153230812686505858195705136251592349756786542175451, 4968588393609325283316082116957768369201146671450746686931594421609748446117196865028717487753303124372714726954024190113110293654067971980314993335518448, 6203956423809187161535413034735741691660310369843727001120308948661387597251199509359941951631439243429610228224345384044911132850565299324893128403245227, 4571369813010543636333116215118782533439215518748971019000731766662413551508103561981694525308643561199098228086049839379019308587186810683847690341816136, 1559129983757164947394863853329572145954799769360806049687754125307082924876814185434337134453716289849661006445851569500457713476129597768589200882603810, 8403436988296334607272570415259261996836575422055098505458836163383851233554215878604055467544609095540875647448566648164644339621843150345936350489216692, 2898709034884930427621301465068636183858191028466905627870257093766022575857079542547790732647425831870696876448123183740977607605122034422187945470048689, 4822664841716463328548964158629300753278018364050890293747063520936124335581590070771891198053285279121254749795129702957640645224406123072526211902167071, 1072278862772639701936162354088181728258626808572021478583550481277413264881376044235597788387464763775239711685919592943755802888641546923803906442942938, 7797725298911739802178507277871835430326372406702378210527585998937582941658875325091485280386957057906549452796656851397999795943663832173184204186750684, 4969652915226258679087246947878673004420974247449902245320198337724855068182603574232572845084507063185072189935399590113777967992235310926576324270712799, 8145775380084304834313391716506444752862893093745972466103750539251117949376683655337922981647545211349597759918219359271284740879831821347671502303561956, 5474497622829424837380238004326929307885475327983396282008522276976315685576931530053031145430519727275138237862194619930839661522332917732088202691583920, 1726910766007391517847296380037839936215081751603959435422231449397639309170494131077194070323708857454694957494591821109346787975911816522355087453904300, 6187413314623025006683794291870747590889253442216217635853683123007712320682682219347652913177325049833839709509609144915402236143083173203246759685244604, 616855814708298971930754840620503615298605475062971829003297284866810070397311466130814651024875645344856341530904292438300169197387441438292742788117160, 1962917560502313173023030631679481990384419652168762972958497528218623801934214128659655261635769081393351246501879358835000732681425475176930249106716993, 4017003124176261697228180165342325889843962903206923297174706836130901745940919452948242801072561675428899371068471078581753303861299620010604284044269407, 5945583217213483521381760323666621047154420346625372979320410537728000371513994042079847745085283867012964104561215105737463081411154016334296098099700699, 5265852107256140992031854974113638738647309358601801581630357451420564228708028731083138364773483145996078673635627946969277926787326120160176822611062213, 4270494582333059486147135677286169494296112366687278040271027436961848323765666626773999230502173909664021582848613471707388973918028870126978404937280810, 6074479351472810380120860817284156304064430367441850940181850835012173163691829843303997342509968426837975672528581076064750254190551956400085000386114309, 1703337488396544901137387254960304581595457113959839136017459594245894631602561218532577221632695520765213092685088092192373124978715831515938967553224093, 5915259605644020908795410007685843940191455606990247135602815518523421054675656711297939526812259033223564202943658762275981912250789005774982599153157475, 2992601768356695555549494074209463372175809326470578209305632209269208527631925269556443823915430151927506471700770002984423967507520453746092645942902150, 1152408143548940030421752368824588287128614397060678052010928325211083363270779692430688733566508210255555991523402560885098120741795826845013836152826874, 5360830439806465166048638957227091515816207127079886639050813176207114338016900579180442078037709252856934493467767811889302618422146337021535560922870488, 6301195089618102636033958263165494062526321566001538678097996330124846814403806958076980106365897132497971364781966330431670505222651668851241359483484499, 8418953928187375566067508663402579117801323664088744218928131123765371923860376474433986909021801275480275025254665578864394105780753768779553996358574504, 332332345857787864998612660526601437428346834172418627806779107312408122854635468809187361518766068299230770422165886134482007539406504484829017999610141, 2216723424860464286944977072412625531995809872886757315676197515052351900928443752098619562045678906592380167965871617335649518035766037484382347469309286, 1311380859514359001200808604268179974712561585137967423131438533223968183599776315790725210026941584883996993605212465898585962909542605257945902850361251, 3634465372025149997595734804824974506925061374000031307161707778581557132333149722123739708583606459197208401227516954022200853730358471541381838553754755, 5999885067589140522091278130813693031693645561819743633127498814473912004865552273259579805323283248205330079482027253621937210468745707692893027139028720, 3188664427290999849784319406911062042127427574347525994607636909545560568177918246029538646262549022338871773823134144197172028828865222732388872230937307, 5239867957409335511059808245754276148706525740929666212331627210454785646200474111143421264369585352458815805951114933594220697981077364276380334633896642, 8816577077369948108628426668951693271165708373487636897987770688131709946357406759648037618896055700124094096094484388478176072227658093148353724685653055, 1718210821894724253391408766283969448567653879853113129515679262766789783322331011879354368563301021297845192935404964967039010990842346271530603478663927, 5957436449373159564586503507731737122010909898708056310829863694737993948629561074359030574999909787259437465632649341496234338100882396467153821576531165, 5554096605567624660626651997131307958856025685811794358238380372801488969028150749163143223522928210177883300232599991077703394895546695070523861368588613, 1601353237168852055421497985824549823569805548378973198911405209840594448396510568888081999571660549056021858749050670494258392175005377101708114760166362, 2241265592757052533950967615275897913211565870628590995929985028051200507194512236544833333506495842436827767554594423114787226637744153289320510321413953, 4712711887697188082057034228094211878618113497995933860206900541173470143667298398030483339650250606772850210765343762706334222716549271782578788420861734, 5588268457822154890358829170763591015617018012547475622056835677706060576579157691846816757089539064757862129944281674227757751049860060268717638264823095, 5565544188381338173754051762461290904226842527280574151512753319477454317103552441865179759852248850336378055148877529003132657751363115133558055533527658, 4961796693626239335292710909731349033986546921324889341030109922261979083434303937106229442854542894595717709287842170164801282972208506650743360455036425, 4523873146901738974117728080155291535060465497726944456919917984692628960377664156566129421785868257922887350916869008305665290054074756997007013064970861, 2259858245764355534727600198537529744106293696877274005190774252167896948378581397042939587088984654706888362009997099907495146520957475659856938663981239, 246322568653840721060525207626570980999452386242290559162972119552892912325081357162097026943078789999726384029495715494295874385240138983802792091993208, 5295678502065811753463035735226921516842234126505935237537722789891672434692737337291148114048892829076380956764185529705224850323102877514996368251644446, 7445731547117394941386130857861319511416097398484256861915161130196000796971877188730923114054801675031421371593539997816162561129784056400240689414614996, 6787991124065633448605919012390908012056755224763571847070016271962320170522547135753541836055383025811898631053836589885606477844036516230360315953200788, 7596261878522400427914226697700156410971344794676789712658597509598950417960796470558112903549917840360817681073832054225608618832053746030214070480404568, 8816782369962095924290726776696069643523145141550149756195776523057744109393994953933725704960421898211492182587484782014569497423357316732642105556783682, 4287179140193802453502428474813259984223831021555889955247911882308544634853705045288266944056218211325855763655590898629842248539002590551113487046319608, 2704595751705990690109082304028251602552681538713866962475611087159896672605746534595034010806342612304497394800380478325493808879945251996154797673130397, 3999096230349922465982467808518469497919241027033782795292168252763749772631784945829878828936724752989488116401794281009842180647019851650120600616277652, 6757365331816777507138419510443291632157892423313921554552721482369031711653422968345253941716606806802238281841509121654860286147912965362834180576816324, 6160845094511446265423875031782303543169007806377358738849145880403644149758793879649836629328698554662656606722246830047999938280968364709515123365558663, 1623706250368066548132592933416193675757235732944485631310571191268974406063828059684837392815527515828742165549761991138449090245359010120923673414800358, 6297516798164189266605921609567795633258853419586369687330150623726292229936220252163023817004307956039083216928776285194274772033254999610339834845229461, 8272892461391336123779802728224199913898233651065416480621495886561767190827741224180832107948058440804589553161449492391356496740221890489667228374922198, 5547783958231259825485204103348549300447188149368669457282394800722934624673440597405433177544563029929915315121488137562567488371154664148798575186150001, 7773075934325363371300426560330882179455404426845305775221837873957206903522078400639557576453136079131535004480715057357265557013281098913506349556886593, 6940423915742131491242070670480803150157143143571388581611724115320090363812094224357473280872381721362120038707558792225791338465942599731614153018408875, 8326637280022229330758889578778968255357707432396328338594112917046068348532757602521056801971655691797318566727497404851120304638814515144696397462904105, 7514518649231293053352549680630364154539252253001155114722509637286194573298823561903353425292257077655831646042078977245567555894649214227757132153021816, 2018623202915768204760650900443843830228785963571484945133032489614949295877593440808260022926688352728207244241588423515474027701948483194153822981849872, 5767248564399951868188782728966810789240063987470658830352237155413501307791736016062668959930500398709030255088635671996024116492017380064010200127237447, 6912504876019896825924874344407860942366618570455242569440623855924403230118978760658990885715003436042857578186691213894278119937513319148770663003951139, 6084670388643003537852572087915323968056710144737829082573767992876610976234885663823060466383865279730374326305910103471524005969791551817345528481515337, 8697150805964064300893133269588006275822054538561767059886769344951952057071686542552990467354221628885259355390538941768120229017741375078170002740668737, 227614845803375087306012672214482030646902986931063377544809997246254386817461097502652403809697376021557431407633080931210610471493405880862992045396863, 5434531341683511828374828162910339303242863377246017674042174345994803407096445629286555391901472001855574992744042297763377875361972391157120603558671553, 1687215977747075395617246979155398054180245442536143133969769389493450891478372927419722081519571241409709082793511391937486053322454868687459755642043162, 5511353442387022941620747072063367932136561881135208545513838955718131814301293110551825676483489431289677063835578643531245560301750802802626752150955832, 2510266946707769198870837220347611646286359129070830527949147788347322767654940284873249370442429591089768843884234740821318555932279869454978949028915762, 532904546924346995810649613632864361479517963801906244536037268838584175537805489066515960989058303962429277330090753348857530721028139571828165539976026, 2906941088105988507200015157815968690279644066354720049933765002779218946662065576840430214427268796651200891814034040930725953576720821943754559680664540, 1005266209341963162876398142456726656960021036513439552617517963154537350497689743910468114121865728915923185177082209198793592265726293059322220441017922, 7206642960278191019051535432398824158928490205051598146951818977091784466795148238823132127545599521446846988686506361482840845793783990872057864363038577, 4030506600197913376752728066961551393333560620230225968579084989061651465582087115299601534689814588033750188207139421735974122788084159486750886198481794, 3162288236761485460259300151190882312461994295137495867211926091126161855156362959560992943620678412363254618411006296521018694084764538303797880533171318, 3449190415432893764085949329914414599383026327490844118896160296478717315010162288154419396757550061606167920917587955291529512420570466629227971247916555, 8569240185536536108948778821052611160715215459548542214045352982308573988365538801604344177319442717693893425157955756779001610332995394111017964089661542, 4623599643962156426620093141483827578694761831509720698179959498553970803233442069908694632579597906521941922750764156939912006170096124409592569122950185, 5424952804609020449248453984167158335829594053659847514111052629533048872550372531366613467894598793702293282177371150785907199498691282211575721258968390, 2747337713007737515494469217906687892777878250756694821215733749533524735324891993872778086474629906535687364525017897357487107089306250762710579840344027, 1485062657276868132513544679173512079488278531670886596361140249298492222077122112548905811617590130324190538686981078239643242001453503452394913356670450, 814062828796946133633232382478925866822050070661789416739152337486590608659817270074322130765561049901587062482746304484863177777445275517708747041133377, 3552744809578702815419661999291842120839105459646218208773685480547847376613050839715717333244704352169470320977486715936449052272744201755112590727034923, 7562623463594311674360454543768459878507826754277709563460938435965090524870313529580472483531934904367721893079293036382252443436383753685476621516728236, 1001230136426411927541348788457617950915210178967998797727892932317011474612088811903115020435528016287847852942398292622095936679769372338095231797674144, 8513148387795506272695269907150998257734323996692029254294138541839010051586801490189291825117300225831491572285048443694737383248464686111445111700997405, 447706342726932318103198723060993734507335646017221492925298335407335338025437679765700038520329361596291208764562325042337784558725561779021949084167899, 7680962341771066293863543543933386399249387226822976062991799363277146344700538918446439508712075041154060754398505909466639721723276694105963006039740918, 3147214705596718697292156986915055442783202520850453816741249901113387341484323632760491216840317209304115146056992009816101237724240645908376145712502023, 2582713572623709152458832086764931810706292657166329397832810805310280210239266838358085513204920932798168381595958930777450968558151731049585928245641491, 1614248419295700927582964185914729560939341677084663620574783428590566319251882636590474542417419121308828434142342527553312048589903207354057655520332615, 3786451293126430601024369096246459751846537293533171827165085610384233404851913779379322443262545070834611050360731632373177866833078724308260415195646734, 4323973921963609226390872671894136430893489525701726243994937025755017893135016267947234029442215320131413670491362803710022424633636948745288866367159606, 3646912318721611916901157678104077928557980022890263678351048968579861104748136592878041050104220117852767778862009841579224421454839351712034114027758572, 8072014830193972203733803551530800657410365674959036890372852438217292380287774123554660845699895191306072652402127114226133604334460403344181189740383482, 5803423383901542404312800891434920298255934997489767215629338935702839156490991496130028206135986537593723725496748375489477877534247135403250828045813539, 30122070648927169978758888607435360081974528366071102871133590651012097638728667299684252491707874895667153625152182177233132343943887085369432613603986, 2182818272392298436578279690040756793457658278609054841449566031438407813364771418414037275042687216211802275086194950321843347597985456530495599537554908, 941304043628748003011404712742451004978302792512244375380505414960639254580816831669284119567047531251476706870814922221179696622156131776360579309179315, 6266550426144579446487154591225149905031200987624771455924365433703446088159202264374749062964491322592015982614132375653607020595072084687443815617356398, 6598416229319625175184869992992694694899842134823014140937154675174900540917514681961349753363665160232865953160484251025229891088340725150734602568321412, 3068455399471045879223395529057963850440479520514440960390072166744387512774086481142908567785823690120403691546322463339844037446427166468055045054318983, 1187168794780585671749274676617748780235519630342925792742913905787971067564459053243782375737741021100167850983151378263877264795335314816399544064131490, 8054933493222830350925459820204339351330572231611393358429181181734275041028839113225118614887573125367351743337814699966445463360842570855415263219461092, 256042103591325520469549467107535533012558196434498555635761126783949799365301329638058339819410789527815949071508162044319598543754159164975843889357581, 8023793978514822792880473951018223646508377205044652649127121954120925211437348882637437386909465084334192483082896365940051277311966182949801320414923574, 5339513526733846515143298118356057255901782753288556512848538272037739592478300868192421902481920788411512914359424859509992169551929855629102077355816604, 8141217806448540434012160798758684752544213503915081503188358320454000372585510786521694615842126650530447868464753958484289471405658921127926878041106123, 5701830973335212218627324025501681934239696015861617605012172672340378166200633747316775799705161953340986236638673937788693861986083507926500507195057704, 6036958663445624808671644225146151141273216691472928872073181931874481117899944877915430146927504462516482922544723877229876329156540841391446999776394600, 6553953543833317195571485142805924019902455782333913871251547392582472098968527967607162659184360375626226597172622844192804483639079459791563167220696466, 5813062212076173314223819952417348548399686037905365915840420775383235505122373122125040814628126835694398504601722530858221072685366410910152523929794327, 1127963120072937551772928721738299742640439117105408899056875019966973290947764819172709098773354168682639148624558273247119811282270219551157445370660626, 1166462769691305122909943656944589702281106991581819083945904744714444083500916465936863458166880129886493588479908998596840119633711708522745031426636087, 5011432712940677415439569878729874378697257142035115424444768751467391827385225446757179391842069555710834921869253224928100198392252865295045960190721189, 3637842477991303106152804329175647968586362010629172133556328962717133159441790742292983223580465626457072247161123428364398749429938364491801986693500259, 279851060729548958869822669253433229213161925060567964428607553862039056002700317934129496335365968413081730924765860423717207785452139566734372581516712, 3854512191223367544271643213892733146299581308765743968208133850777503507943062541632326972592955059073485347539945241798320552611887143995148005881232817, 369607446026029547656227516946278534329720871211424267621217024388671184050108155302427446233090828218330083832845289608689899873759342489769623306512031, 5055711033973274124226122097038262916112148248952109602945248813917657890346278251928823710583430995140534982941984082335229723722410820939090298660828635, 2957410666564651187085105768922461063663313031707614017548194149682104650913281191069369585483625250561843285554654188962718966356702755641801743059932930, 8634187475487574411292078828321883829986303708480774096512672241245674601119914376816262438110574733733678666365594554464535883072968422440281738032333791, 3712011194502600917999877053959021221191803160325361583869553902783758047347841182938464248293178679297738863001261990537666744001772386837548103847983972, 1375609270881817003177369160358403497161901634213284213633296423521346098693755256531498138393203889988667740907270884655857450936162859775196121292404776, 5837888713699416510814095844645131355954359052407538081601847102699473144364266603846483970514208059174791281459426364728780362300368185915694495308853871, 7648394063082452013494553097886041862972724175240020289872154096140967237104059949644190352057369835310708593713276323476295576091567723128117302406520306, 2689529658915522665643789099988530455651028427901674012274481709468599996643488460114047878092602846229309099366307286739927083435535617834918021664932911, 3496838979900927262473178997009842200349031652289718512315834233296376888182289421472197758649366375185174931632511143297581352639389411457342430242893135, 6824463558804780302378606052900703948517928213578335414654097179639005751228793960688395643908941390532585521656555241461752419681283222147895340540743284, 509976557002235164864750901856175722928018363394082949905895695618175427165245393754392581276140604952465751647426292155118175653764438480189755426896538, 8472429844293678845877468314782583822496343130058268679723720047746829723096611083561224387638300508054963241975189474276145605313112683048694229279784815, 8409640136554082413510344470136692034054461235114145311612021855078010814354521812454801866986353800869572429360688873028501212661264099138796591785677157, 8806689077264045839607972906511822284196183875721774013354938369032159744811669629382465879370267608934028643324792790814128997592473534508219921406442993, 7861136880934098213028911142287259187388339417871111073553643128790197489014040932567743063693142118826206232532858254786435746794271958703473753941223253, 8815066119279437282031929051586381754097809330191003837689809778235822769236117778683644109854906935680206355004339420889045416890593194361394971704104909, 5658778209498097277094545043750711640602394269498517701405777228471600328788535618987349685109195199224282950296320361913771206110643343112594336894341405, 2922208055866108051400436936765933036332955345140898573064419132589729469236499812069658346509989940453183341951463372245982890730840227126837770661853800, 1498384607974381438100261413198209764496504006553266145684584964624860234268752995450695557963317519530883311567800622629843172282810737169962872825289283, 2171126360977622728199638106035963083079133880766101928113395537302733929585065111040903199393060378271302427149137069710123429796974156958103252371091800, 5381902903260626803724855890049379558695049635850193445360169197886490755577359948469637414146489723298542421131841949568075736453714939802077274977670871, 2942943870666575517408961517841894424389371600076173064630031201635225473399756090290900484313613467136664028144918637180102832254525974440069466754504425, 756490493933559458001223448517897993661113634109159586526066730481487050966767031946936286903096891435036463557141035344542900833210560409863354531209233, 6674294862046287571767846743527318796816800976003468872917673904035256653448460083944720614890928182523574130603091087307219234034473214375104451192120541, 1174689819269097321425180487439997285241642310296633876769425809286892780962331754812300155720415308443935546373212254879738539482699374985994815638055138, 5730461491183910591103843737939208498517147187838595155815510774193398008271772820330826009258660620881852276351559300317879513043228120128575503062565209, 6073275999462461577716225047443431543148605384090178215694875135963805199278943102394984972641107886394486824450259998314613334644156063860809114998135327, 8649452521713125509042075250069323276097810938700078609027920404450414857051012588274704505835599311302030127493883275995538976659254743268783701786622934, 4808093446341466277803646435396730008181407342039516729140184280181046779896077182025950037582393517164036591692058758341322006677878824391936053910569407, 8342846169039735800581970699385142480268033295342303533661607090145334375782172270505278713858695349859914024505333790642661343548559234704873278455076555, 4012232531127193487698349183992077491716945754082634199290313388784216719063349095919470498598392310582779898158073807953105713284119325523455092587615969, 6816774992256126312827229337092082535983582537281633223690340724717225324712654979197818402347837951349714767260127968823290743027855566266065466020849250, 281774033629829795608977383836986543700511883831588861023289324154184038693654032570106331420984450101349503690851685958021891301112591197061852418768697, 3258025359254442258657076862460097090995530516346145063698956596085463762807573925691676663660225494743684213023893973318829752289786684511551002309473673, 3766373292647225288698341946701608973965336394768714692712549169946045686188013575097784117659138265430001771210625197603481867236003330816210793514785270, 1141991797074557959768797769996230237344018788628785187387329252274058692985619879709877450377918193547116961592969195089518074247141581224043489954150865, 8509990763554030484151648465161324491075367578777406904323247261884095707783493572023892308708990253554875353405111981788210687313233293061745536011638520, 4638852043629910492651364424247558489206941181461138549954497907630927443513377451464893004543176242005910447313472893474894171464457878446812384161110135, 2120296350420947375697522260532691708832129498158801521703756394520206055274991310081944536545656369991015861788297474550357538609246882600867466225510442, 1483969886775964076761402471867978346804634717836403967265796054538802754298683355565767329194181502381999384982222362186807952136185698347694984475045534, 8277877084239568176239282835857444594440243063507985529226805025003739385869778835682521182724021132841782305626459929491093285019296141140884404436657524, 3264325535946197541318991767554205197673311442979054145676088721485490853874049277011616478582137071370368208396090558614247710201507872176182008543910901, 4215720439932539822818183713039287078178568418299467264039706694994825463459361545986180866775270692944458313288423934134877796254270918934352416301154661, 7164848239084253705162233350056177497795196174339779879841657850400937931395681351374347858198460906297705739086011671293511303023141815483814240785092255, 2562892509382050327590794216732040716425937314671715390221691262934991753268612491184954172883933242231823868659952666867729021070222130953576777077293876, 8269048177854524798474876340920996751439443689895824054543545881684350265166883522791276670959301930434947868185838458082833207996342252128727314048228347, 3692355853826037246078923839563627562078488311862622637198280017636828500820698189695241993242015203352793181608478861889658526322512281012916234383729373, 3521581551652747609311642897939879559120781117283467699012836040846259201056169835877074851223661478442598222995034519505008668477025546744161608654186702, 3401472849961357491836682971506925470320801012989580231775778589867046132782799305942880606337193447906047218724917701223311082005553953706129463565547236, 1448659798530029759972472731105074608477307866355204776075947989076585890212332072901399543656264732890780969664230936149286604847930745169113152589052525, 3372643918646025000288143703639733541964155686992990525552163621199000831150015376618383281255297880763386456758836486201407845333243544732767627747109676, 6387482400654897192654319296326114720166051893720016962112783409282392042686495802976394049578762095167515652492655527937680035250913313111373197240105539, 2705880810011190488155450999454583620804825639724609622753801437860347473173051527709506521524859020587538243313467052650033231132441074429551110212083417, 6554312268492042482716518404260360239467128868431421815798492639317249266825773745244282386823594886227614214630659535119550212585364079355276434931995912, 4780865960118438606968803856568993604817015417312164442248165581796729329893606859659116159459677361089106079805785721539565138295110523319707405784219882, 6131525374831013812448562073326313881290460883017772376517853483169298726563096575667449452014089437936589425123193574740270759584255824227536789900419071, 8831485066841001279752293652291679479966773065027116384344007834203901594566943279122224769997662613715436670139815437917739139551174343176311526673204155, 107118575532952567640066222912171197743939749284458190837623804223937231619244350818406804834118578158194324808773480658416245271835056952468210830729080, 1799192252708204742800906609258875797882889436570792773728188803024796883042354224820238720217100085310981486360809113095839029939003594096284824000483609, 21680285706534296607966461124557665157208463823213595910255445129766008158815414817308199983567990615596000733504138972253832613348326415892069387691493, 3786433985416887350615080754283692031102656691904387487571777168762654371188191868187866493461414705140244977235703341507167262608458465701051963267760544, 4449532869535106524060673591837410019918942902232360184839569386151327907597190724591110755115938279910620632309519091370765541093064129530375575252522606, 3160267008984967585123766035734928825325849224353517023168767164643671320297839782114681525365092420003605235710139532431435582290832610669855801949743256, 1658270928555823925570576525828461805173671111210038151866428835024212086324274207715544420753719955533964815368053355819350205461961402792683111410463837, 5776395195311184990336052059661669855083555458823932009971783455398324839413271999283985193959905805319795118979573943864686354288310396169558451704490160, 5262022945458743313286620579076992396577529280922541446108631742137027380239372169519439260832730717690911006405609227014929124131941977736651072449934956, 496915267343737035188104265676565520326007383202288646001665717371391256103504653585142616571970023958571521360179057340122516566704983734198559594195500, 5731708503157660631751347453440814886417250498187515989201776622291339228635924730572679236799756015713293468505179062877568021806793341240631718912299308, 1030182258253327314303709211257673224874517032556015041860867048594639745871879960925690079753684967459166837164374749019614648603736782910097056836359861, 7956203246759743016636976002020736811752717757101244646851751506068528481330306705207265868935343275868305025230020959413772817050367995101252739812301819, 4055215337218192175352930074893160348346340160335621923202519192745436604008974625539999881129833249922559397353734569234612627657596891271717056271149270, 263269559724521388997183925229234132791029980953996661173801544020311238409405676695116737880542789034297474602808041919323715139178514239223162684011398, 2569847324530154252587132877966968109847503688833516990573634365350635929760637430522507960292148976737864352460452953027495753190868493785318030113554480, 6288298968802817957524080200221564654645582589971380108319408129250296422607356935204129761892857094905208526939134862849272897803466680675702895719965755, 7885532652806155394347580581453968004389480592697558485684978113354119542602812675914287978597428914057688311610608643032329938248792054426156376866135058, 7277819297603871606226978070823493963604598146391214515172297062005038340767545028162141603848441984399349602559229524382734490046313312154164758210634709, 7269203464893183181556030349174069780450036297978177212979338860769923058411593069393390155156810543423991294092917390233471434276460850526647475981396935, 3146557959663841343226172674864325030782032068048998352295616629582111427376129957748811500270754637201976975598022056915862403999490292620893281387512283, 7391040087108134331276187920007112897812559743944793140205493377554312167881765764827995414239666948816378827526891904612781664230405333601217006515220077, 1593360059956208428109154472137277081518071435920895494728285181511107057136281584539353662687283144628219147842419058362621939736798284664501494194329301, 1055929319874859517460543662291227026630255589947009381267273625479132357864983000576874086303461732557186477564612549650795085727913649288634800551794867, 3858521386745171129270767272736703040432963324387519605833298838102634164272456533116488846587387809198674436595784339233766445234316078820794632883253672, 4642372578843401564153643535618095258970951662552825726139202548531631927124926487386922206689578472717521684503406471080506081741727550487602756099675657, 3804248082696650667470922836209418090774205707953473665802841767889583272322283680446958281765012990723759801044838248909459236267111573119924647352920027, 5373149623449869455088991810691874104255379593725941655344746442754368747198942442117165496822305300060528332513371206134032827534992241155463068244505013, 5153361485032997948014598140127463326558051085800918567274791330953387147692352236247191765552528252644457382616682619734986952675605889982253919244503563, 2298000862587030453957051263878400594158392187597000438491089485428306339282329196202120114236236512373679611350193631010448524902560313896571676953100305, 874459905492754047992910402326139104624411967512546864498992552141803373966281421757525970541129114714387960776317251083141394730300713021233012989358160, 5011851390485443682793936632151764891864399471041168410361727539871792146170967584429110614070284260133360656734837357485371752869484832586916987224390031, 7149997319614274105226018030845679813256121366416864417654264612592342900597157396381215500070813886458849852024119721009897309731445086745994913472508663, 4919869569540690922479680503592913572939161349506049962155637137932523145097860390427209409931173964229227688661322428096566046497965212481289491691247214, 468083822427218890304943262090002851130403349529316887956904207643150198373663827513570924415897300382292979521214962435692709839872744124475719270496906, 3999650146829518727684028476812615906069661753472586553244566738719593086959889096132690555904985428565226762783189900613945319115349318729219774038304939, 3563744406130971359887101697549377331504122791474759604571646845586303452854618914302857605044334020661958569151329457492842452201156642230430675382036057, 4804914220333678380587496634392328665090738157130295170575730890347538317632037296005706412187590936486286815017802024096832723431086214714700059071682353, 7935341559623590414975144351517387611763116247864544452421311741494155198913090523688471776424351609816618683878723519779804822110951432380759319349486278, 5961630148762397487466123830447205436368109849926566686261915234350961118238850043339489674230395032946936863337943899387326640021918810773576369495325949, 8431308088659159553465780714651792681079788257155378121817073480756305371756770640758140076397444159079598856657146817467527810394962032201567409652025262, 6650414374270924865916801248842884512101939297948387058123842800031081006532282875189035851610513537101985460949201100120563549022283552099244486854438147, 5724059819474152546075124126776636627449751242553883095911687833821326321060092835313178716814714048372499436289965706858376553249747811330551191932755695, 5372525399234233453188486222447692809221361234726221460265424499466469577372713110410313913745785538467623507014202398593210433622793285901991449988810403, 5758711719103874602720850953938666918473438928816685799074125831604827325310115841347327586589702955433240514646868450531967261916984122449623904213180325, 4160842051712027399778335345115139624749930397247718245809234384477281016510824965589262646419410906022640968018254246850587336330253139074308716820940832, 27190405803656871573005565724922169307955066292332043352762756189360762796306433713322761448994607125562434228234735648445065714428787347641829521020743, 7836391161642412032541345459745364810634175397812840754100030602249708247104920929271882758900285084415555120958160126016618700619790360311858756205052950, 2521726821937026004594334963560397549945941788394921812725376803474687830390475207574982449006222622317443202152795227808851433261557678415908358469640968], [4279087087206631299154411600466833621745324873794665428463889581772246205318703604503913091125412611067658249454600222710553516195589206172844202542978787, 2439234061848354037927513094903357479883779919224837533492694377228073901512315356326006868325875656760910476800315943626972192671415150096948539719354997, 5541619382962371709745615115949196683061863597378976454767602793978797531316439554449159567680798094068696983762047423688216208501925335990469631675044429, 5338932157446617151833219916577261481669428617951352943730346827701847994256442314678340786035180096602463884097124887072030380628510890589170537226089293, 672188032527120110274717521053199095567032691199177261468914617017616371985042710404162243141489583488473361475810201024374994008330041999766342199147387, 4813661007234670424027090925313910110770311360935955452466556439451546445824625029793808171442277720675261709610620022196726547390045225076000510463414305, 976580091204805780176436104973437261639707534929339001410960063408083504369982073838842682690117985547779600271800794424993686495117486317245481725716009, 786865044167068262434504923714073249364186113538997308572716386801837253581067765938701212754786621125993494335741348256560918971675740036217375679859195, 2424079063859176648800249966316515255220036797172955911799325213696600062913485724699114709314435459094124123523737206191608708169561629087381161602624815, 1660966033243752415288870997419566420241351854080076152623150647397145660343064639316156674123659004091579129449051426475424963879110744359218083613707238, 7853993162725159002589152106685276781321193413093152152423962312453890884916105837633076050523780849795911064472385012759969132448569707344851711064547625, 2122034507770337449154314893472700142035621998916206364702686007120921863723140775944351006215877667829579282723694133288115635616455335714898782682578602, 3833325387178670618613134524673876352994978841207374115295737141546978745435055363289451303377132814926545266830566693316703553173090077429494064472879602, 948700703463536182093691113463216913400919904832815500710977857845058938207861895241093513288900795370075097319496416764217496667757831510051694236458703, 7162839328045931463832603212913768261831577761026658648721374769840197568135688324348074853500780461563233631280125715470570482050627955909536444689387542, 5416879771810101865114004065362107465131990944755553381077486442140112264633508097797749372448782558792913442466747845990021260462025869994559053362518855, 3928383734245671637733512212150286469165007063082811889720995779596315294614661893915959617308985866102159536897953389995387207549285042506125732740042092, 7871164431700472927568653497745476552256338533913571263926939768568970278586997646725843121836187140272808357688070233067820473524068630197995639686416816, 5333508718818887330089845136758470707412850663114460677402175115951708976656160749097069218526143935955035221639696375733108298484588907937575831947979420, 7692716491676191747512595393692455488123806628801497306486737275659510516654561086520669732142100312342021762886333883745721269466699416344985096673041513, 332290473100278628195839247986327130117793294509017743249736072624314056665828744160348885729172369824718765706710873499786651273738379509060989101266323, 4181296673240214281828513582570475763705521507885888255390482633657576210590296528662833475163359413619505517324417012464016774207771793033373495932660384, 346576375047718187099951914897979433357677318795882222255225550626429805989845788296138725233763919814083482526984941093292539999642095748339673621962410, 8537280177303262545645430884032962288314687518938148543220272685310278074195770532881087970294703874319217740669049939800148573161637677674331029023560284, 1483353320109445206777012293820622971874775235880176075922881913128584574821619455106460329178488472986048819405959790406315041582672857362227953751298400, 5104473269463402380366458377499784367196355760845686949832764146852043327152039884502507236882078174305741140828594207786081337802903904104098231149781428, 7306328612356312220199090795517963602978953391816175953341875332156340050080805197478744255232360865542756292978498733281600862238536169336390423762595690, 3921535116778446980050954937957915429722950659630168941535466298127930376260994824520635270018907489365170532737994908474795750462694803807944452188479953, 4143082173398698557673568373817113608213188545432612573006845397890159067586578088512372865563641431688848814473455129876648667259869620764831637027204375, 3352123026333614495927901987716453196886304029333958063195760376372784804183311109694901665897883701979664351024184087275528777192840650703069866641487571, 7916697614307073026904158199774883414094658922554927519560302323758505905269824483249858893235620642964782013382351152426469320815373732758458125545416047, 6290656558971528830827624752468906858513029637995494209081595255260081925193719292447092632833442386437545744842039623159058083339392615494148729558324236, 3346423436540672093681344898027447833633568010717817467011536224284015259741894601144206327541278989114730977112948964429232931492680997169097338858366180, 6289424772830119278371995215330789087677672580563569408657924804990281319268072183469692820943573476995268863114614020208154005570517677537178855127746144, 3343205057945442923400381692275808660800819393219481893317610882192773095917856774235244807415804392678106443498381301904871774003893149001974335561077530, 7455882994014672384030614148082449763970578500155495219274844006993123576919589297424395686959803222033953225205889667661385917405691926265460849162165547, 8301971383436748419805813812671558258406661445795863580338309272948913323179016179972167347627744547285393645411781001968934786181312897152437805485506205, 6706862240959675399817248538550085366580623693448604741178693197689175364252228686654025032645114109222254858142591465626627718688727897719493837561579711, 6484216175311678437169710503795539340200919988608397009236474041340160053019983591361912765744798086039786403043576762217531634751529654977940288662605597, 1527271593816988694455709880659546067756737840790014818994103133976891620896187725374468836760121948207183458662036007250785057043918156373861467114640361, 3206019650008970857204410194377300188102683472463823760722439012037762978196828641240623200518154479618988229360589743546963923169564839662682704142443074, 952027765648744072955055837646257856470991354107553324249665071736239797488319917253497681037652368574951734166836184156328964503809408763171547171908492, 7418048394841065534051673785135554896444784031445847911655306332256638487863201758379914697014229905973050167097222277398856497655302582703705739782149693, 925609446647041038917783049167011337983946871781919859889524449422819207734817586507830915561321788656509531103006770530995850166486602216962919034914804, 5290788654060350299759368235147004733908544088519118543124678216428641499750472315787393258772702790336413849439964831119223114106150255722435455767663184, 3633213165503578623227693795602279712294670748594775811736712328159777903487369657902927027840724154310147391051264414841006549208964104257977096510134377, 1441701711318421314043314239424105272623970858748910895133137385133904058904007034653347489046968972821266791766221728947887989545993932310113232305860877, 1821583926490352655255319992938643021423004421110092684533231957715938597008563608290426611010913816717207810514620967673952672410814972265693792218326084, 2272412118451426628236164841941881212546849748967307907642295008245811105154687270052442147202974881462899666399927243369797449617798727440645978459612899, 4887579532787157446982187687308401483104398751352243671151657983860230596199861322448610049033414178506160176095075944302243813034365268738955004709468151, 2060804177464979888756090934324925364454420262686752438149013255681218624088757017514285201032900653493477420703327318434213382571189633002806264752616997, 1490251865299349702547300002815201048535296131608696542584535311506187060459143091324699113080495942329567087343752331970556840827020871295285258750804025, 3154866175058867342197665595983853631790182757711665060988151299855231744769132979890545594350729569665999448848672871766444123921360494044525470008827576, 6486433000907179135419519938086836209194956611832561682623669851630464850575538564000868010199492282293806202841940061365955551868363980484526803850441801, 2428829786620450400750237765030217297500568575847338928629975855526889092458155058759331102648041845255481415607776717506226241559409137623877685237800968, 327960260682911134481862091347054497004500020949078314288809199891020201519435107108851414061955948421916567195862920027177387164090805192481963569474174, 2909534758971799837125812394726560682061773561897440768046699144608790919506470070949587919907943798296880070794508098654003936590863710158427665113676036, 929683067279149141252469661354669323599306127536931033520151733536955569839168698143372970639822779219019544869465426044674816083449519251728698682302290, 6919417312615826747189290644288608425657059113060890462413565397345411506107860772026362752715793812875586453703852288194680108217236307495234097307801106, 4669816077845440506796654591207586536947045060115288332795405774962655428097951226103641065003935898351412534987004760033087980893003343499926221191854403, 8337882289302848440200180879710677787539198242652765328791411813204612650441634850945560441197163770137821894506857851800848320920959027188857827509416515, 5458939015354621820105698119179712521746418361677822274267595609621406704277532074321796847739276507342459167331242561248531514211867312383122960499429628, 3045232360530493210235092777409540623956224219152004780588364663213763201001469726194114441754709555699840087758599582677179128896975020098812595202221911, 2689527831302338501719238195660069723205170170766660197081787381855481523246018108407708263721646617688691355060247060556711070894132725623815843068466100, 8523668477057171784169756614116081506979475769906270206665720891428835702412574551646165834562989095318420645968192362755640606164955353044893764991037421, 1088976264032445609659340030746285144541984586858497717177467636497081899791727962815926743151103449272892069965609013136714588948426075955032881542100493, 1129508215468373895449640362019354435879118034930549194554726356990361278629801784271308952474454432634555514909908918018455719096859796258864503255962393, 2480493240113986299199280099037303245470894057141568552302241272707600406421583002150313139565823037038765469195392273851338482581855285514051202044393075, 8020431265948383516295789733451792989264683978380687855996267973524023073602355994460602990521380041509734715110306279908946461399043541260822034932672353, 2162296611100809583197236734524311113354150691545010264494322487009943537053169195529978173746203822571579045168431425636023387329603904829699262365254489, 8593323321367071596127566149576070662371171572344397967393635304366998673999421412500238970851383652767580086922628489269012778825537012534587972191473940, 5151319228911760512392667648862122914946098051025448274840978712735033921685683151290708092848084220693693945667661963824886566067359584245994260977145779, 4431721565113248096309181652197297999285672379997231189038420726950725958914359545906221329626422172082746086116553706948207776219886290560356450866296186, 8283945819895771153127517548199966981085819590932380242890229673629310760675696545495641158406612180407952578364508633931780615132396380069333252480352520, 6664676742123904847912017538052454935355704014681079177753560104203850792567613725447463363372469173784687155605825069079513586556104239341954608528806683, 3469272059526790781858400025301952183394164716300058993237635607279343956618109989949513951516820691286263325965345817394248897117058325093962854443988830, 315652025818206433598129541856734351784013080837958133624094708482139296307421017826637560785672755392079991840192713181841440912703833524827683621893118, 998348831018152897077691000305996728746786350099450688174131527105462739935507829002594840341167822720945006707928548814680888865698749114783420577536045, 7868458931356453794300732985402410861801188944206940162495308879678066867777675538318359914866968905951085031504914649814800712335992590202755883687039189, 4968755124529959926310850583533073814512155377168072328640254691266828021421072227650354744107969693033505483451715622306859544257964370357632468850489460, 6936751889765412502823550853740582710153218253873197618167337292655626676000076879516885909534909732855659140077141564807358926984525474977735212614685704, 5138157548009186008396880896909811477439387892252724545319945514538416085062555895305686261915899495347397855786037795439259410474712303556112866697705602, 5371427790539737420018893999658485370631614369396181669482135869120962293361860984043725770200708788869430536355008765221074491223971890758356511669007518, 1802246830848565049044699574764224974044676231159423313967174635156971293061722676906720501399723537377050171177100038916294764877026680680632442595771548, 3860673443658529111971857379620221327591100216482213967030291906390732931069997111620517012046384446362164096661241484897483031171832386047822716370537419, 3823887680667192262772451519024270391680876267815931408807879243875441671371594722235779739880601552127513254866817940786527717206567833398819522377671880, 4503782975095126731856133253780506683197629706267477030700537522041411250823844330169650853649820333164172291657372770794891653802451690555370840962630262, 259280938013981074604588376570128797947054073428118435482447930484791649859141786436065397618778442736719532071971470821666567979280039727655799328881264, 4122669320282208822326639738014798685997506376965975575219921974882201151099714512260158254201516285799097826616613459446515974474971575321723679575781550, 6254721140068713251275240727682836904779056604933668767414597143913119167982956473421761448366635020148234609018231024624264663719736957881445813544522550, 1167795491646216754677926669843632909626847901282869589853934358929726640834361028123137424849535518511790493766295529308701285552077332792897975852563151, 4267533071225401538114643311492438561674590914567182173786128044404206120279357711076804023105700147242509967467105962038027450096127895109503518824162247, 4697563580934955720118926701862405250456638350725565798015731809272930330849283870617627440281631671167906411441038016160169162419663393412608522875509549, 2744626774272780124272670286072900069298996715337288325651332342236579297184975490948670233939597692806286366492014953529675323706072786155467028648038448, 4467639461981824906121414173213058072209430851541998638677196722903013714231784584975226427832976022750562410276807154914483099521929152256473047655134032, 5106703610135680612711655338823764449470435722084228035858285808785696160764155805854306916821079795520876256372957824830461995444652001594182681739181940, 8190622416784486265919510053739568552480309629080948637443001515336723902380040915195515969596460926456282418532230188692921989168110645051660293414109660, 7724002728215068834570708243414780090142755222084291375125425895137177829655542976905513643530607192336676513304695386200258285044327751829475555984484076, 4458417134537503095217440676133073516998968577246726337354536017226731541012813948354411127783984238037083309242295008143594248552968061450694131502230692, 6885065249459087383808266297319481707863816880738801449566990650975171390142504031800086814878558109220020950914834546859477027770159484683799359966252521, 5459616378188607747702734121737138574408394016305261154743285968838792823243473098871620537463699205075619091822552314858850303761713699137585244997378297, 242945835876126131259037042586056138503842556112175489294398498988064762722018489910523894580027462723048788736265880217604746758138324129011052543443678, 3442619935156347309330595513779587102667211256967618095588933359447931828843510583530994688748668470284865286833370169292244441584305663623855504656007681, 4763163617256728783559513024052485954854973555030302164297912804264154311654643642917045901463400290906726038532184344691253887964236916841490147786852484, 6897891900515459190417026355417851836729420258413297630519406028570171031506612360798872474885642079534560951577588199538146471491881141692974424836979741, 229071887279809196205961945884206298216433596231276741261595177556669346515221780298089050313747524170786924163794150400337054901250339442075033354575662, 2676729554179183385333225025302399484444760460828863837347475956953915511733650110904692438234001729716748778063833149253914205674588316120188206296842204, 6209065113347253257046018359536088803592524157512189210220876690387844678618873730997519416408694560177057302760933292688092031638571241690084567485275851, 3077760167451211732792728163497386541593115434159721387830970313470728816250137380174132404948162121298664890500206630496687557180469051856411958996672255, 3681805491918052318285129842501692001153441393683407628739356733506580551289273215396725780559926349098060728596859858992806377895176995456457092560222865, 6417002225167276089494697253733140261260764381890156145278032672014412119579749161163073722161725852993877384279345655012535858201511435931542888552400868, 4818209687646954017159886198591364503746427655454344491458065603842572491183904412073774101688226196602576841978107377940181535015791096954164424470563894, 6835867654295227722195394369470032106926141707648276316918741473296259133834380099769204195098707486948241768304470998926461747424692449061709997397541391, 5237264022615540834381260964511530331138405584210961131484608189821506421886039107151008832535989427123749667001175955274927898644993015267914329612917866, 7436966667849706491132997410540515062806354935252318235303333565702480214485242948277343899897977734257383603601371834941168235134257184841363204549405673, 6679488173981490014426418435971989514812323019465921512632109715472998592259991909714600816388308644799370523287101591438417762840951175885286181191387902, 789359177110914174539413898731078830954757917655287940877339195174786293247284187424881657741237142503529185791461583821612654609624314195742220576529197, 7810151826055498676501169303052952057110789830379180229900182129477225603804152087011260875846535732848468796553760478220634705761935197516779673988414953, 4116669088560051158515100438313374743842571340096013261599162315164072870816799109461162331059683055026029528603955478035707898275960780566432702162752189, 6786085905982132092124834965813629961627845853227071078847523293870006539885976820466886313889930633613796023265553599846911875379632224367343653764451643, 1575133892214441236549211295526005683679049377480239663215936011105979330231387728605197842246087989296526385173860520267884336922455782069902046850223377, 7748031102451295808100046770949402254847252145829665372932237466480902010989157927669150192683656628777393065939112363295543737204505654187889668955901574, 5020858280792588453673639099338173804405277267546882252117485204550720500115748298173533053614738124184747764917069844509567892785930955481611259987009275, 4066085784893732657438480084253130477129577059784262992676156261386334495316025364289291718119522877531572290509218659496982541756002470559423917136057481, 3586960173880263140975028004091554473859853315476026208247426709413242972325528001452384989820937744925496299602644963664827505739179752332640816100463933, 2463378314444577495304590692912715022691185370341204450000393277115840134198298027283395160793176646708055253340805768013456611202956721560440419961749223, 6896579117825606447037333699236502574833668388326125003662673578577700401378089625017931664595682813070876773356741134804020873826872444104541732503110660, 6374928138747610098602830234366740365811210285476361754282308352653612863134270839581621865026665446911322523505112885895823609236585726596085023422683305, 8166787532812031692122122897927379305584125700438622962953209589896393338370576312702337847113256728371755812950346900982109180706637165151152544309944345, 5591323720773878290849710886059666850501358955656988379164652945304526348981783292382398230509970239296098578514369606803027044960583189591317826716475265, 2060945162315901168969771597249712873924201095775076744097038548538793757775595069929145074714885713952573430178267560070830117127680746696711029369258795, 2738836329670069977264452858025142339547483282276389844314164452325660379506008527213075737467970440851520569586813400241934272497007918388022997521226148, 4067959359111662688625402307545758065723409188886022396759178516064178875003774215897556536177770275805225170417983926755393349674819952085923356260305241, 3015520417576364395494640411751160389064630075926844068966109747453224882612234682171717765644837049023290463330594752332696726561234147743949832415488082, 8806851781928090966536709589319732981884887467882000828162728901861739120278033152945000065871006186168505153419459848487823768456694717916193641752878094, 2789180041258359216266673571680560298300537244067818640607606188499306070278098883886719293260295663808127209465532403248609977017202778848222848774746573, 7234453886353214579782337432424406111776640009022199583889739804661497092013372853709557926284302455444575009191542429134277179511373702073507558026137868, 620287684709070585777028890994774922272810195672939472268033909411776072204266930089794063398445373601067872706616322265796149939412265117889179509217350, 4358116613931891340838054904444447314225864588364501875095357971024592521886327862701155821834418487575376090327214978572671164142461360929749694663886567, 1654653577340118779561285739953819393844895770931893766429234624102681812491007962376340607716627200253699491936982377224041413351113218831255267386645212, 3066270578286030203531307282755952279892837451508030088490752668573597251891386623382337251182184241436623886226698378590266814976688807746996773870412133, 7209016924714075171458660139008331650984577923590716698270179093987161874971394087307032825288588014974347656172370087637286454503587663458240075608417923, 5911612356749353849008594018244778852755662210941605157607047064136173574608027963387985350692093215617041044865629403492910595111339390555042922350064439, 5608788392736790881588514226735435723831651580307049264809487057079960816018767292960271904012483595151379300795244865002884116498116421573654549667251713, 7952836023487995328129590976218623524033317491565058794495488308836163211192919058240891049333382457302826982540258269662842282212582643287553350517571705, 6041329922225568491631554636506209848098461102920735289049556766384777573227701823971278024016853567439375720051082308286148821313896275571158493336963360, 1564268393884953198416126370703954481058965793027366797599737791487308417385437545676189086643710896451376898085012286438257228378331962086595658018731614, 6460112145965267490376146612207097484188384470927144655710268787393740030266649898664384015744331401282565571887014512309532646343084146278466882505566096, 1017210140201825485782723105969282414028079965671720048149512772896551505835019441129999769007586355520622235744724875578058399141469448537426336940457235, 6063398398506766818479958922024742284230596620941583728377334187752917858185497363436183271037327274529532516371037457416454240130856726604015692584137488, 4991970726785662007202882764480851119233170487145686544155923526879565425973286092173627575092905010442539041248639071649788303324369760786025953310989739, 5354104452701393115498775199984803856824587724602455459116859862584497532373666718253491307238348521257307360818979137884824156355323607607336240748854437, 2585928413488771356978037698559445698517927169008636927747217215874816514692808215777981434758909354083758061602076340514982146604088716090006286274636140, 6869591120434621613621941874611644064840033029418417188663242568201883348642035774076908559161913456645151725097310720632365595944467212219119791528043599, 1596589606927729053375679482058122748008789874185402439237227417753829074111685741670980155174936393260010702531644377419214698925602901818635181845689519, 6028331492821938366901487517090437572694713101823511934859214171779630261444757626418601755587104539063153630765912154533259020008288351450059798657940125, 4711281147716976472196302248928855141198592139828998536666489038299819771163320032796949711629417892707899599472399845234961088296661120765490714506216688, 6180210988574014691501548259087748727684813604928084781355827122851424398145883429334491199185588087900128060776987864532579996281718306654772710843476493, 5795271906449500425993533942527583227565040388341696473633694841734477694144208068630378834421768344639023037158093745795372996823164586224272721089993814, 3102176852317505027519296382790706212005123907369689610831487109183633153379586452913396931439970740203954561337715940121850427438040075450950975732418076, 711171238458211355381040524124094210225493723647019658197245712179692804115093014986465106789781162018896428596294931877130595059333643170637564344527549, 4512385816079718952544848469489398362129529968664608563299582124489147338170975141855503110884863683256901912418225424410733499070189140653346454951697408, 787635116738496337897497441438354341178073237844491695200596504608215197947815305053735875652755217694664913308119870141215789440937435577062182773018081, 8188887809194483398289232520236268401852258921592355791120943477785376077803631941248454609324315524110013613584312844109126578033842983336953186997209569, 4089346567832560903834056023250079363359795006111174121106462061851486760157386506203185429250499998063852869921885076543378576838732145266539750003470197, 2785696008151109722999985580056934246843301364639501328338362653471601132896676862957420443437474163243911615578543863787844048773454776973532294353106939, 584660387247327905130005699937304482930210091017737904857755059707333240433927530467661764579421332870983105509522359480022895335334427398782527795781692, 2254238500169160417715947268926108636784773221299754034946765844724052996470173324351459490146962565901104853616647131197338557312906647246231412754289772, 7792415468523196100683262019022617716433016048944117882888325386138600591033815799979705173432697488641063624150811725528214856760262663040767115440506536, 327368488738197608683325314785870379716426701096531855421532658737652945272558474669993968482538477263532787786535872467104836166668786054227240674692356, 2597110130123407349900676158686323814100570368527666816475727243357702906631360089190780841317674705227034358921267054088560718988482843695443065563967241, 7588903304486716368284826565175068391462539213520072451653351557025749383495852346676785191524033707000019100433297806631857914929986183136551198964934905, 1750515092981917248848051348759377510818848953200650371069550324451158522991788650330292247633580089851976684907698417448623594073001409417266670239795546, 2528172488829596282367063002201643255922358920573944236181226158894689065526212807744481035359418204516648665716200258200145397570413705888065376198036497, 3650441838862357688015426439822080504301243425459857445304776673817743824644849050456506523852383119265875894736161713487070700150481387122901467730976432, 3705998567831113430269762843705142809421906226051007563157428187448909200509773029651128951162559011892919798735321728917061010870706468561307970633478082, 8299038493295613191827025572104540421303157736164943754546198037497502255238192933624779528286614640040483177915761720417943352135907786637759105005133029, 4790162078190325829580072284467928212611855051179214013802246800571002719178067184026839387320097553517782260551111728878382917735391993920894654698872128, 7035426611260336340256993635849562769604511908384083792522119437984406588621374698473658773503373242929618236080072347892705893472461017845478414813524456, 4874757172112582161907992612646199297340910090142899588420438952375399217362544303330910186805696139809706502963160020690339005671867488266872565388620875, 3493228347108522074050903135490386605820809556882063923293038525420765081753527560869143610062775522514297462569313168387694349808135199125458706310267806, 2541135151493535218266398526579021162344201655352716260043684807381409671024598885889446261403845005752553386713346941596471168656327712726867279318470935, 7558810861198608864135448721405759795640424488515832733261041962198681297380903916594250289396395258733009998153684285922889297432380609455461317604307521, 1084231354071498365291819710769264001451175713418511500113087109219780927257594608522488983735777656846393397490367697106362276862384731809181863803262154, 4849787296320128652752640339466626877205676545846225066873600594542673746084499578851317902989267700114182509158075713272971789406844416447022995399444447, 1915379468354064288982326942129899807830571972045300113934676995905958637486476778070940827885589088698463764146307411307116506049909600421928860286848130, 7613939426595090940499484143667308910798727197717011769761245614182890050259119725934119608366921272905266371947390466026889867304127729824538614295971188, 2433127282553891107840859929485519653871714705969444711434947477826168466450976262322795282132942729008961291905998058182617025631621796091314832955496051, 1813149641651537580729502031365727623662647900583168423162530409469489839993584885440058997277796860245234155312113547605374075190426714684345671669018380, 866274903155830661531757907062972119775899473492734989035451283687212575368381203468352061348714796372450936263522749132184696617246241154189907223517109, 8568792302264725252654960810090531740296322040485268294081093645354553519951252809190372455915495281107909611309989149055085942214373886687696497332232461, 4686745271277572110629345867078634602218458487230571101620048363750713070165460706308232291598070297484169465166462237705131554758276911169999348420179283, 8619130530282708069102976946191194081134433997405339342066385353997845277851084943569192429001492646302442068089011681343457230143291995681493860014335308, 8648162409861585873331829413092465295879073366452152551142481802371462751954353280759656050811808866355263664840216886342216972638457039189197120749547905, 6629853586348074493492096512062293756123063173700901340192916779376128778025552635223005446046097324047707074627220130336822652762032607888604749126564143, 4186980696463521328360054520562149076172157239956672682479339708262856102368952411252516676742490482981722099336898135955559627232516910182136937725514285, 5148818527538907001802578283739198896524078235612318333277389811987225741985148047676565246784097122858837591386015608300408215314300517261840749972156955, 7575161820049789767896924096007726130623481004691785737196526272099142018406031140644046219000386573061188925386822320135070461544958691963595251409432712, 4294608047211667691736234464121519518459171321869998291656558956389238468502850335229413330430216959024148431270842421016044955286516654351232497639091350, 4511337299411665226970311255940544047543739025964426721646377215054092841725101211049042240173266458436489762481933256545226589615405535651065366484829143, 7061790552488875174498563844353169946384051248105010949033836923622727833138236885479771757109695894608184440827286247827505514626199985767694478486965418, 961298781627252903338819154333933807069127299744747594188129771188646872382299020601000010149622276345274750768882251358867508990798478553629183078273250, 8638589901797822083154107888879358391989341900420358216649101467076699548667940292006604810891723605915063420082948302759638919103185564952049684585343944, 3849915865077442001019244573338766829783061443848873072660947710638739009875390236021931266829332396097705581064406143363396280417592874581307451283270987, 5316319864721530173109596884972930794916168213758769567387872969155860661971923089332989075111067377168763983449131922241749658581606898558968666547033365, 2049862874838634483270301519474977979136022422204939171768751627043953341124767322290149283479329742803626797648553623642060117601237897900628444158074909, 114182363412069522998785787272906210715336082542547706305293196268435343014973328132519459567295460701446046999428372074462203784149262792649847625433883, 8351452393896548874544061143553488252422293823119195089361184867435084593483878131246079384841203873084622042798735268504925677916369448616183445498709905, 8708269665843572910003995850939906270033338294982672868028972767160437576204601655110719841733052571900146805385747966964777546923924023048783839646833082, 5786504821236012567338593773073075037802939403593636876202953804575846843674285259535027456603322548059143768846981599586514690984352807298214768134435252, 3467200012591106493345574085600575900164200840096406437285404032831777645216697317777152946887169044361013553530791302131966283744211123883528868329729904, 5346116542498406601277067555198054926756059596226449760304732046236121666536777020174049467155207275960604839267632661632958650017993548114395668548149844, 966312991964286416183229764188843093304747658452712978314506254767420937616774374705919487121983165583556153526010846148789452531015086997980635639471269, 5844817151219123999415028402454801960874377620423160232764234369670538134758862139592956321946629644596175406379331946953477865063107144738529526107475157, 1085355348438578831678506765700967253061511403038006772684800794955559217177044752746561523247601953687387068298253937227329333369115947506129427385959375, 1648902157954706124807590855023000607091573066440230733749134528575808832278559885350368261915102646204899110622223030468451661733331065704980939141811288, 2051935608566732400476216378825707918468831818295189540570415175565813351356198520414893890468437957162512577935410493655395357323599041401817920210383359, 5506304706618824084165886518598698790256826403608034967076603087469321549452004081157000363722690643304148704021889672387732917731950315365955061426152345, 351302832048460905694731375288688655785725398516808632644435560328858858287958481800638819660017356379275800550396963646666823751398898291690036896725012, 696365817956634415759409779503858038945255803265038655823316323840206049661035298673651781289309067626716547637866975441115103126070050344080709817346491, 2824410401060258077733657270568603214636565245952155528341922726099459784460131385022117179895158605446768037957464955092036221480085519133659661045012078, 102933529475514474393864841631521570640402185469881745410846540371615717301695060967333553205636658112846012366027141549107146144253084225214041661623401, 2217064721521600668981248427709757141842454007599843306307175647212379920594613803001337948458043283845218095195848386599318747337524888620720457114129173, 2167894750186666527225708548405555310321510529918635550335593795193480560065956978745283061876349904183160839301700317197482451008108344289033579919075188, 3514195378002848886967988321547377806908572670979837314366250212815502892908995742683775138661712076852252123359497676700402513994440407638235011763833716, 7144367550111332112677260658775750186156477092817137265932436959755443016934472681440694003847513989776502423473913802844452300688213460074447872619388416, 7625435742356834233184489410032550382753464424557272957337846182938681984871758593383783920289343318105872735892770453361156535825368998005641383766875089, 7766301712615840746990709955179031573312875635361325106497422982223760517025534811781523232847626853028911773911372461340289079065774626535999152678718757, 6483456176546487535813771813501907080326899649901869165470300531443557653649517221931332351192615811721176563805577440438972343605202281469316803875599383, 5786835019288882947825210219210416381726034410802350815889037893458515123717468563402520832682334451595412446884962939228280942901086855451200685918913540, 2138926924447433931236584606975600571632710796893611340737805808125227505703318988403017068488185160625597918966249856713490605671563324615349739538147393, 3824226884452737919287001796757985663229013229729009809270117472510689351534178306119505823216583297664947636852975314023337142561877702343317049983433074, 6720414789212473611014045613818369034086022646296872870931633501669008620089297349615231410969346855316396077792647030723148417810156724349531800270587629, 953364325347512735557759187148841057109087274282087724400287841486121760425971662546290555901823833515386353724775527518452350231374908550250375182548480, 7262025182854205601730261082503974748728560380731431564704458616679667635599562171563926294593723732914533543099948204405716950938403332246170833367150494, 155746093533807898861748368279967240702146004419312483167506485396465982938909839693424135966401060610615963267365383833237149470503560375634601540746401, 6001950393977111707913326085703575783676939594062580799576144107429124675144786992419217982950464475979558515150111149718998175973981368592081295365013125, 2873494135831431968676541493729606688730633905643693331335425096576267408111557803287705466126471472878603865057821332978040187111363870102889834281807732, 6912292566424846628915250901606322069229541427436745451845225901817199922052141651280511262227716992968102510105556582747127921447263827307685373545190145, 4248261020509038003631905262154944870600888123283412889529852740985529119468706946775477662109112453903959854445987904136452088004276163017113327540571000, 2570792838711572005950745328480931857337207261800798718028118404173815990028065085304790596737108588631145546440262430350120091283586178258741604983920391, 4464104360579989204284592468092988615287421982501184353914429009805076807452399273830891882373867388067425547363183153335862694757698254718063416873004257, 3290788028619826061313832389597038120845885508688286591026339056773276039844674428149707987547930365255470242179079373829927181655729678970773324595893278, 2206265126782240373388925141579132214056517663035628859223645784969637110576602846698183442077370454943985679516537701395689590079807033264965818593958952, 2526971904986049797926065588630927582304037153712271922811886990887348706950928395141300623508517921127147292419855571795329997095443206428590275029492419, 7791989456523565757455219417446247503314437107122100874953867403533326505470164788231966734791120842452886495285472385461748956037397233278441579650384860, 4710463774394661171645027520484954009578665867428241171934869382439634032318400701822332497893031194747860787328238005642702642818731275429152914662703023, 8693795375137409038418204328656914488720112686873127363019627449724090948262266271918431159446474128061958299388529193051704620309720979141038654476299809, 7706053963703723650501256424534141522172372458314749326819867137225378973802629369568113753301201942348909496599147056472346425657255901865342973462235488, 7859515245397310553241090740062428590513175693663568109944407465095492258375227952996855551800087911812888656991845544450409970677081065365436303378557010, 2188347713292615336976154235806628591529511454066662882173552060067817553329877735713004065110022917385841524145395957473980465669916904121527965826707035, 5170817291382131065416180958719906146858467980043049222918406229520067343399343156750097158804711370497249239094136327725061388685387574234520370887102760, 5860419173112215851816254772882795118732080098590590517357418713938111559322367414134515201837654577825443737567508927339134663695356796635429150199140029, 5085832193855570409026107252454392626920130520479818844363411736667392694459495326392909164867653777005703950919635553390166442704386913474661751682968694, 4143205578886041800607286701307421576485996928725364587409729450071940908249850483049898975012569216379544366493918934621536688869121644142528862160119663, 996978536838236412517095478675914542018683845018750436256967098034830857009050668155233820816243941881944481103151311297304394601752174859898133860528883, 403584014274204890042113028104897873992904562419722809655575150357120438794663533404412114383677991853491821234161749276310201781916410418935856870531295, 6286853182298537639287934351754901075860321630634663537196471457663180050705910575199520261961781019410122224791639254976419721927404956156389791753130279, 2104784419868106995499707175995982225288784957834041837160548390060449891236501975095046443323005853511473674673020172912422443050610735368292809008469822, 8677425561250033718381109603273123226454509152240965156620861112052209009897467563623344172561069062815316330422864669820020973137659755159437953870422312, 50779670339803831337542900412432113832406194195957877357746381865748581094077037103795606014546521424181076500805204508803321252200713926714080739233631, 680806921617031655678218839519107885811343243749697212816374361019998985431399735713453479424280616400289510507047673494666206336517787004599958483700189, 7293282722256029057125829388355493014251756227684850789719114660839684440006145223691066582331411312222356100648264728387963203136606887525318694898236276, 3263796651021941273194259222460412145235951806380884403138761154048772984015513872556649805814723544870627620232482450739881006572538233416555115944727093, 390238212626914021724739586979177950473638412859808185282548734524895919585443582432492237496589472069313631021184974489965647800184370405882159752014958, 1714299724432920794062040119399741349158545128432552633675116458187261888853051569158802387359549545740564071628385334300460599464404245194852782878733276, 5251900566459939714614137393862798530284698222863432389916517256698541098232723546264167692111763541367193693400503385457026344911030268423981960779828139, 7715296586183947706831202516661710840749500906065822360453427662261008054978688366168036680695813990655037188323652906519855801480016348848022959050819124, 1244403022903915078041033958233620132583576910618822971896289363694407322790790287404965608762495052232213104019052778736518455075785882969316017993580571, 3462548515558221518826535398733582443255472820527544486747898532997835754145998003900564307610710318116602127866283661964259941815763097007470422163818729, 8069813468573753977745871734823893730347636001676826842189920965705890922512618905277843676197367170122538050147213858572356648750366919331006964849725661, 2023448446608709302308562917357983390782781730900543039127615075023417314941553921167091240990323466968124405085832002693406032390427880372204179396951241, 3563512556653325107384906185110094395478961992787385927940520801566512681718699986791262679739235017799388569979153006845036786530215044649218354439083900, 6049618982455290846529041225181792527137675442227612603795396673436955844258428940079328441092991379506819982173991633979323953098706321262995212449929646, 985327957184241701508146032221913309999968741897814420621634538457291793766206803940305647464507260813037397075226760667884055734447390583072186666035075, 502462200996877567441542625819349553112814632591052030339601107326326713866853402366733947159512681876497666599755143900513420778995696978182416583851456, 5033104981466179353380294584180114559995639304302984714396543922268501147743246825374167192506322957241302923395201236493765495938991288916446024988428965, 7287016514872251523099828880196999715001764475070156950756804937956456356940891322463473168894625840107028086195243728165922256292803737050246186697310926, 1727503082138836427347682259095471432707936756440723586331813108724082840682527869930026907486602445992924957591305708510719062732702171089872669906337727, 5695903781515157487079233663444161612643208715425877710882808380661195356773284677276397283105471097432895600539984407974536412607224392902948831191029751, 3465795376577958589949279315667594641247865355661016714310020825199344504756018605044985733458543411282206072328882133119999090832822042158000211877507600, 1353779084750817052086003507701013914601925813912090539695496141052384654804191881737425461103158842939534945335630303420436240048600887597751784432544074, 3298104480850476630521439794660744068084224973628414941447101925467249219370621253240879675858578510124648163652990770654338116130018070338200146538457740, 6597205167820181487982222698909078599098748534026363946967271826534424239678986036454080108242938157445165665161639130008699598864894355971420911320008358, 1779351641597979426037392992065929758337122850648564600636472686688248066433309581467191645803732212616711860037210396144548454393020151118426212098162762, 6174215983661751688270259007305253855341329772509674624825858041783849938891707821977936885959886802678306762629457966955255874492780931589168816153068166, 2336412776828951916905664735447796343086600855537800083460156663744862664979918191610331703557331274942520639067474831520755413411186791661222780011157658, 5187348172775390231148530665677679323690546402819409283328593290657696157013053649686312635358053157866203754133676009143599211371298247530408556545238468, 6228352471172684714214655664253793853145291342520481780781503923803768062338744010932481998067341445501007160079711815756426213043334398055261487335563443, 3147459440939203627833102872221074303265435522222749798595873300423065095269587818649926095558789975220438810182004860610533662033097663618415846620826749, 5298687710309282490510224678044466376338859872750031631074533118709333400739511937841069052022014090858701587086313064372095576574509913838435749151735064, 192308241902917073213111921102542473735178549548128400185116303060240668241547512187825045362619488116535039886558591639047148353171405568971781322727877, 695089700571147476989305668236579513236302635027114159574586915158014831886547402066718820220381998323665031591650550714932249287607985357580805098875629, 4547802252607613885915092018406254209648797210532081682979236045573877494822591587205571723322636441948179672710742205836003878210671920859025863137965731, 5945818886007106774741065081148713201370412707484824581476410683337054181755999037968034967335496218012327168072690872197794444364661804889671894821623272, 2313968307113507300251442155549350715655430710474577132842118730226502793389355519190205309968123761658511047372040337847611763731576054438098185757083196, 5007169588476758788117744486363196411158708563408695158854412340305990891425548410777675261194192943111571203729454028625821784625833067708467292144564848, 7670001705714185621354755058514485038351810175898938923604282061473610792755342647600329555954955033703740978798801228322934564859548744954360987358021716, 8528622228972181298582343849302667579455412962328695208809624302220713482244422553863450503291293665181060756889799856892100495033704855734202152574321201, 839833108020993663028760820940637900991084714808312073265745602524202574968951881175662759001980741129685069692363369851812050061059519139919340940572111, 6208990265070328595340593801010842325493131487293323211113585325457934424086930514698568478919449536230321045078541419311687359599111136970883064258489386, 1125727405004548036681658968067406529586023096040383606134068887029547145305235947920963056000759713395225254736523661839942541290607333393335191135919502, 1425498480219371404018795015818478066398308834792454675504499132264721246046510890737634079954325987548308110408123910101457481073463451444187505662207125, 1212370673996419642022485694059844603059830130617468907073599493849707362912703418344442431681765295519402376328392471612084408690587884798452922436358711, 2892082854843878041239116859512783142265853177609533529868028980530987034560622335563245413469757167793302998136947141560870952006175282330721879707993547, 983415198883984628466131070883381006969134071142336490458737959696493662289964347718914915551585447988651983545551400713625996419021260439852446147717837, 7868034659958078405329157041894866888818223733385578139399110490117635134601516150660883863546655295065450310617399681703601965703462205385335001676132397, 4722522152424037912878345944198976736875586326742828439576182035862195781422491797637810793675971450273435508550589930018791937183981196097700772242378186, 115757510813206469089917961656649550110237558234130999704832139822450600869973875972385847274770518524795465600607729758066540860373212324046153830870473, 5097420566952163657453831254239871892585299760110572481881724064227077684135050997599614764584998561803346642008023364051655647673361251051540594503880744, 5544937980821221194807504063970151617602327227797874236263920667101633315235367502566413382380627536525490092067451893391732462438343325376506818285950810, 4484158580215372070693402412485766558483685566848478874811298532730012634602900002281604787328295266948914160063067618291857099419384187964327339771281333, 2724062055769804096703493472692487986929275492083587509603215032207161755977668872038739513735453285154131939924815555032591098699199098174657962223664916, 3931116988406581722153844383792126249869639999704856923047915322898780166070424747317793239446724549328125775441426893891815647079738579776420584993413773, 6848676423787642359207380424189074481135122970314337353200881086952011311565344409575059826329293997646279852497353024615084727809437141839736254586422529, 435083539235802601799720344738909221713687279431808311162810685955482658704677036853284158102829727688988677786537553242265769312443142990142884091078353, 602975338328883404372857542879665698463583240016076639379460475397116897485594940031986755446422136309643406755685680871044093559004995156546764618846975, 6159466175964845689247684388133790243451534016382829868976800692017666733059685781309314855800941612840277119835460681520956358344880754763766536657040202, 2673168460887701052522395245335724966927195833674457543195513392914407147968474813937296811203062164978948611482530575192129016152436881807489232404135106, 1985068535175687441624764148913815441328804777708972681716852763786629073567180084182772483620666346401904901475098940999114681431038806211377330528481752, 2839380191201041584629969095236614187474107597746559928549954581786895520935094836253681323159724370490899309519959775814030446364678808846698155661769016, 78942990215840038607745157860244421762439562349048882013001054148982597843324081434915390654150161267036828972815667737200771676262099137728125814572465, 1458908723578633912383958695011966690307746749974500965464300116040798518651959939244097903026755271219251697923102443265187427068974732293122015051198673, 5276499322462987631291362436721435322909022528964557730194404007900732770896290550507590807934513548840946241388637072661310638145122437598500093019653946, 3290006453898457909039484381245079004236938033266003592745856769488116945084433529351993043864475729154692500094527113555512785935687741985503618738869218, 711229848715262911186099099569026020104580719576999043566698087432602580721423090393621763486684702002744142711205972905743668394672607048376340419987219, 5078351361311183076758951691466114222038400098888759508181540679141139310392232169850970479663887511638548283171590546244714795095234152429845359173548642, 4528575141046994575776366922436610565831811215865615417178295044078925542230442249470757277887775583106742817821549690874324574741213310895989710851396981, 5397531103005057128354278168208431989018725662452944517620626102705064711668051058517573876457155981614404830382906382850169845701225078714671986261141967, 4178041003195738620935275361705160545428995923140717286519154232839719907475810624959991861761968061772061535153726623733253321554086151965194736296910002, 7444076220599932814008035030266803662441831518659739110517089144858625253556120035519722147951805511496255246620953902580187501422931266797468924190972777, 5794494250065468408274212649662740891938345262374908458756528841016568073868667210385107040880351630467645207871925565138392216946419642118953011720439490, 3093289057159163482251940233696816062307562286314483044172518739707348733619380918325665251765134855542094021609603475668308286614188271815091433004678275, 3278470131673384120838677750591901928383092305780435259976947014416804186309514366542223474229477955420378046636245232784708420601268509120804364831096507, 167175984219477051277237606909593208154638287982541527518777527830473404609804618507232707006809268240880564899013352608432566903563642830651660095544680, 8274852797938065232242828532114514033325748208326531436634802645523514659590394695736885222381900047350900080719026900645469805899493922257196916311283104, 441740626998815195420683896429512727699545613902469290471088331142680355520596410002515020444474227510706007678940848265625154063993987144571581001129949, 1831528284737318213343284904854695630939532461942360954214400561892093590357225246557525779251255525762862389556034601234151386049822449450888742832697148, 8429922926002169936774895250101827418433004318461608204823917446039068088787317354342474998433639541522473742451123671188697314139315180166904605999196984, 665551897417419173925793872168390208468145667592582013230021081298575472552489157826380229180352947515701107092683985971386911144939347941016213140556880, 6362202923213857173343009975078457791111610525015905978514787277623595627490531043887900133366488339887732599685176957678823972578004040508083966920877445, 7734046361773860483078488886302835507533552622983537304906768871315954710699985526094604953076137510586335459640349045727140316255297219434930529642987149, 6906113384758913620643602800328154486906620867323050594280008796640167976257997217770798126849492608882043475598899401370808322569100925836223670269523308, 5719274550404213324278256260288062650612165634268302948218411535701421199163278869081161476613363315481821809533024891462710013154598412036115194695090398, 637270188183246359614418797179046186331103395592737463488568419330509518564048606135314840371361784212413181875544950636504252914897570804552688445481812, 3577240606121187856195870367858743848524011143048813001164169047733466888118035183460135802992987477735502786773492328884877363623918207909965134991768295, 7978594463709151145337430913982795879079311570930512548671750107966125394194483514021837047245235428363735622025839874113572230152789666231737518804118453, 6252379934106167619842404316830627961268594018181469016841712380852951754498476068135713247044748578818737732840694958384185298827312260999187778637220702, 7791395825902013326370862070474041768291855210812484157737147844364781104726651996214542074664402391870779645352690789958353823571267878304487402331402540, 4866094081451796655251917136638842690775780126010946910944272373426976092392238710036629657931768863081285142959752394082267326454429786282926985514807438, 320125437267047501270747302834483983690938130954446692409145983337948080438708228120178028015099859908024545722032907853580622432590518613550017066637600, 2266325059129313401480602143468705470515110279746691348417684804033770422264931609110036392511493816832928072847852569338217739815852769576119371376505838, 1322090270285998627655622648540994122693525783819034650108475169301479182612652318116815506643689887355255480014729562304408252235819619793551149167319748, 476489953247904894289446317269187418134198545115146977025146766318744468494749279869432316056413531922977403419680681490720359168223285416242902990740772, 8238026474813507921966439890441592391050393781670396426850896070809796277472781705087005994560612361435399781537323576461329328178910195861808352956418180, 2947145377377790321193688234258804490252221933425728980612044503691735872448297666238117242971674107714111513728414476452113120659589537413622329826755411, 2823109972898670243519275652797594193759957346327911740339535744029262319740746252438360532223553361666618051096103390199698882428754435742788924409398790, 8683601718263808577297445338047303379719647496422120164630027000918156991381543953476577134009697832092343311888608364577998441899539950817184234956942454, 7116786262606012086895365442702175345243508754023007979127303697536900585492011041187952578144081384112839966992510798430009575978508513858005948697094898, 4350879812699439160167240562983534339046503862458143321204190266309516839232135440746164420336227860509603364763101037685073653944487906112883154497056766, 6272819682609909838000055290700133363051577272970704398029905441586379780111570744846233889172858925153407021452937672257077041026222973066442291449860063, 2245651904204352817417982163086115612712861105524886000549210487097483752233781939282580378999003086595598245304068777300490796835897623614038791536489804, 8280458296128448822149809208165805078193878868977123060737640998201274356386386836036180195853446137346618212233280803126105767136352641389977757111603291, 5215421764985628018507686314246441448204747119795647859069501744569503629606435340555944486819275439174850269753178108710938390467543987935674779329708287, 607328470022463552086631258714360048329927991923928907454855518401143601397697519763012696662294491203660563969713683610896818742861568934135897054560623, 2357193466759462763640085840727215989256135518628571799432764593096073141907167636181173813662394725980699920509042324903450623530012208575926753335608143, 7418681710882691175534708990808705707298732288318493501563461114031924246942612300833642810921504832136196122197998534535595797589660993942484199717711512, 3551852467445182992836868047080765464170141159438663944760219410071134396694616986034367157170012205295837643681772634119340332343882942969635616310843561, 7776833920071180772289835747307401039215299482328280564441328406066232384912462741204513191652891338156160866912454168493191946200898687803395043800596946, 5959961992505780335423448022736257657731558817873559505498983430078196955545683347734644751691401946251746474154379335568771139141609871084293152583263290, 2509756190144016357441526238322184948527537140230485411396587667979563901978471465015300517716272668482538174193044809983214307063290501812754855781207517, 1965154346180409136381251621931779647255433024202719023474560807590819688710618202560870489100369208548567022483529200878177603129659468792119929565923141, 1526763019812420190228477058782061762990434947769479580719310857705953145569674135338870265507864725446187280949941026080676707463947769989221033587935535, 8838300588141745255505136821247752602724333806673816285544763319493800988501674289718949960634958357130026866578928588046569715899144415192183934760091519, 5857969076853447047884679783983143377357450595952033687299069598792052253713949144196472696334968513717553663293731636527987129700176280361459557002281043, 1168969580702634916846399310443839741683404071310654825910425811868074514218894374978747479558695508392303996276345518554922807346082885375545028302930652, 3744289383766912633987266683269349645504572036815841529223567874168655787916293548820416734120098718101854051092952625921877632913597294262794338641469144, 3073185715439256026102975685038166478808189117876483282640672082459677432932057655884619716183011311209008515907655164995861262568548360417141818055656051, 6405700683664653133279707283713019461669919811352038730669857516091898149058680528976674075791216452110641928521392803319774057907251892220228483785680078, 8644714625141658986862178217349142408709568026263850434710765895865123619883466411784096212547010071854291999634503764613066691539751195128464855153168760, 594603616612414515023815800128460269912180007943234122863234455013190064815279982023321678979141200856752996646673247238874696828245133184661218456400512, 7035776646072604873181949209442842082742604300825823133226216302097997415193237968658269109966855915996805782607902086093528167353766492593795344959773104, 7054911954403198472072512521708430555335195543183491935024240754448813802056127509745396870407409532006472718920971303081505641932202059252424872921375047, 5392939532234412104466472422661160001138133563029530919855206062440507764144160328081922459136019117754639334686743154877189135760084104383201275673935209, 2999974853848920284836920435469891694326810642101157084920388749246691600612478156912620461671609761416377984792440875224755012759668577954089826878618678, 8043042106079420248920164540732478642797484619533149920141965494627707151616452738280807874517041162373001389249195581889183329594324639280124145994096896, 8535593956779454871324908043295507583463677932220532850567487442123322256090604418614038579857149141776701875001297126077187991255620566574803467994783123, 7384713135951697462051227125792275913368824011165729138036365636849585673645655792306105197408648542387050109143881634173733324629393874718817637208983646, 7398797510785447050143622009846614622202750004232315864054524735883948248162768016020132963406208303463052584874192344085119287118039486356843640372950885, 3800746734319079281562788676070181875394740775630044528056697591683198015726753129193553809832013641508446011909512031154272144659286440197664172580682609, 3693288445337001434383797071653561422865796848488547272230681833683339402144360840085614050274932763314007927494833779487105623036705326022701729725816684, 1309517243224145611905686414810889664614266480743360272056496391158351117282857648980059572981164248275490700604899401364606655835662781322527297769062962, 2532221450664378061795568081242600474980480988975857810328414941066935304421503659720913603778590366953071551566900411685086130507858897387774369604979452, 5037093188701630351295854893145054777007132031558694317570933789457190497344641495787853561565186727882654525631628443338890796607300417643076925858596531, 1102884115859191559696343864118558870758926050577656377640416556276137993197524042512132663253039951215382690269057943507285180203688907643468138247286408, 8448972840875693848334030263255438633435203550647426194466954612769973508215934985270592688985820301693580443726801920817911229526827464060382740092320844, 5640309255493485632623597208941494037252609159210205421753595311796612665223868420151986198309206379783981774478526205793220024843754678212227598728850388, 5646146932893241548257701179848097860647049869522190749056453830283800959254139013062229223525309066466525717059113861749537544688647185391365124885638831, 2852529029811178404340736347230295551967372253715280348923320336552352927367770443243688570136308183940092081400968805005306504140876626018960654355669725, 1031780260660216079847189198362676753721244357106065564730964654266214198978611264910247662179019073742567484983649083101516327820268998395875469477226420, 3581312554567806960128721948180476769817664552753690298997863281913313865071270948889017719457818587186338844982181280141529898294050389217853443166717316, 3248235637922720650161781204941762063446869731632945601599471730345815247705328620740632212180681258855563604910868118099413761114839944426224227326512753, 790430335270731883783153975821143684727773727673210681028785573402374231505834911266724861925690280550195183363474140133819942563250216086984145069062185, 3447581531693481787504272334668119176686502429009421514826971745048074699189372117758063167922042306023233533944752544050220506328142876418579081457598223, 7146771750125488725579512351766788484909523152021708753779709476700168250205539890952552917700223963943187514073951358243568965048457082652811460922679509, 2491592130619758794824086270468171018234540989642567733936843168246594848881452495553691289831705666406115226445225811371764549690640412395656586623183710, 1528294653193623127831505374222297287702916884263201939209855512729062398795869570184854700987943960384241815855864110020761867431935749297902887691892853, 6156984631952196321978470008967778202178159728945608981594279143624421211837483951442261588590928853095921899564673978313108566138888492642265139240904549, 1723327812724585642965185328419860386959676113773120451941099785110069046147470230609536914096090897102657990472892598967508560387968246136425745028402976, 8844681879509446281938382017073776570398461516538847591461586798662147663164004138353567359698382592265220064595438593621990636636944260163464383885150981, 2122951148088791605148930430023216842523190110567498363338311762752490255912042428166481866441055904245331534626402650327233897769586622296017279602554132, 790570578670699118959942941373740112512015348373674336069875469554254461139328628067950758083756882283161864283716333053764484432736835240830556920478388, 3360572523129521431661849887916815755885357675881119312002012102324395515858294672561373664398339685427572195366955221638874035734917357645712141246438612, 1384151506599666321733191522137732119479460345684061540748693695002852283752472971373746924491030466664282785607437353144585828555044792888715910163810144, 6763152094151846470293849201487836332206680916382798321579000902623795787364546185021916669110692222334593792327652697423337297444905912794268904251160186, 2735735299713374601379772195559163776864229323984712373134176139487035961169291179407718334569609555492081993322957246465125141267221485741172208417052462, 3562692052375820068050589494891701078619507009885022463350465181453888588197973260195347229674978832801151071637929953061341711736705434325164755265355182, 7782342272739172018363014158520387989767451835550242186590207532201283405690535449409645329538180319462261693540694949388069136008610073679774232291279925, 8114898866922527340022710445629655579206708749621179210261834869751463051436271049391799862650635765759036568051369973228986438037047159037772400314188916, 8459293860893326101337441182742499230619676801449586143508718091506327321470603890583990337571248487839390509480780146977512416603970599602538151276300896, 1104166782904834061447211862425282773918225644199578678736068196102055828545570384457650020578147199275294924888484220592127133751596010453410609448124206, 6894094038581218286102946056667274941277036593408323420854289861370428612929693512985980017937793736948854965583981405827688430418636888369721679258425281, 8005922930081716193835826592863114556448410700053938365847647244943372244618523410623196637206096524815033960232278357591947138168737129508160847203009734, 4879661644761506394740423704341153987728045089002589514394836247060806945683750690358752663931652491618944972250069307631174497968893649203631763527418349, 6979824582954191105943099541709434337481306911081249149748642549054453730737002895925555314781400547608511065870978875676112615531676121517630075606858678, 5614448749811316036620209283229009217208936340966422996128606773116408395410780874314773590259485594892614608975460150660214560753527065850939008995606229, 4698722552965093060946394213213851305962576615396937121412851623292958314052115224171346728181032927885525057053259318735186918213050193431865331560408862, 7061479069718483687432172273487727526654795002621787876331744276596783400100296738442387908341553592577084524248459117914659822015090681622808466374766615, 1300835693458350828955495138009887974954625861978717719297583207378159109418662295829470724179395722441522323550234150090002077198474588245143837137667035, 3755847877033364031243835790021339729074220257690041707041521804820992225830052008983038812436641435810664120060153163548508831840881234780645172387182971, 5618165413979725100479740395170325856902317550354061073278063766981150356705596426915200469688549087585422157989759599287753475696700874637828790381801014, 2246111594704401578798695128697624328703499132059124876595383038967475009264807625267813165140693935273799683397837462678125271632175334498097612375632824, 1498540639901314109251009893100965033334036369979405439049914382932959321591152024474534222501305796310634374282155267986782351289154901654333847690570620, 1069633199340778768437090362308325708699957370309704452315634650796764835868667254984568547945860397650741688935864108783128965046207963816235196302989176, 4082909511206863209824264048181166580820212914928201104262127375976525444426968714232789749764365463126096316118317729902726960882510927746998027692693040, 3444488746892713694537827886643103540656965406917379627549112195616123600144872610291123865107935131806894700491965957972930639063156965046583254297065028, 6225247301534922332752407404024101750915007830967319479181700319234338550927163574630802663914699574128415594708988141791307937433257636599902337147994655, 303619759996835497941678935484569736066897491038323444243602953221997497937199008317611355782918197693174457440993211623440144823183409794067707346630389, 7490463203976079379357860737216494133634968909663318838236132221080956592300991927331157332026672066652084645914775896235126066748004224145358052522066149, 3447803143173964633892350057555229480695529130988981803465201933144273578917798658549299858079716752132503251241660655521426807997495886621743349609616666, 2885031350423983271306520894274094486298749949345942130100875058234456476600991658524667656987716469795680862375296626667049309284280346275567039537450494, 1720161123308452583750338177404661760367543553642269301358708148712092897856781884474629975354626526032230090187334743344434357966305626098443082855004305, 7073458806184811232138048762000376451492870243327534661995021264871978695215338532177158133491288485284665783167633505422001977317777232128964630538338743, 5650704276594080205566294799788779233111373422272560738708226403227083167130406002740914943134284093227019814457753700377597739852854408607922205368044167, 6459154031588188884632864950658024366456457942397984755821218666236332189699696251610498157245887442160874679944317322562984256098086164060500146252834625, 3509794234982613690977852811844491766166199707545795680971755648196288716532467719756568946720376889570672307124764229303959186876549037555308959916643486, 4576753884453005101036596520762644287909948003225924875329289021976562743654015891122301229397778236745589488600305505180179422509833639700183718761602154, 408739609761626613476610230081294315592044499634165579714533645397610382635555454551884289167581928552818259115859981446554877432298338263401554115239060, 3515930875108832675760141167405124693248706259487917781673948856879828612133674526963488408576408675667499650578026455250167194016250116757278721387769980, 2133528294311883199116441347487639968576531002539940721950952110340390867417108026466481076297924573522299358493088432075318230410917410759626706668983643, 6720489290170739789024742456706887817620276163091761791205663049309077298708113997290002182798565023451646247225383878565311254745026271364547150308784778, 1041735718484853291683634352079367167863503053096647061462836959289519150768445768532978691579721511105899676039257176115025898236385683874942429514566033, 8393475391892195070528549526116388715057312041500750668381713976557862388292663341113353586232687929012894915195246809640354509337931115048207077631772464, 2032848441289044159809710963081494413644297874381400877541235152818607919755188979824651095207579555961627196334016282020130618039532224012903941147649349, 7419050771328290957172307809353764976686756009214154422640110132740907627073307706285958142218243535392929238018687057666204557734915120706381201366383556, 2789724309246431050492991651835998635562119493920195693269541586300014758937663551987738671714139068998071785951026043250649796392776560182528658918849928, 3240947670575493280151610579350085753860282138453300426471834764559222048669251041585628618755368826202107605304116078337696078414432176669370391128068317, 2628560843427141790128457367076339940938645073799693450290629740543117152732863915347309222612214102941008944923716032407797049347678073636683405643823763, 6349071528813620325163334779119419965509364106237942498620350117743936169291584106050508686501613938219579340317871550134166460824606811517249378863291914, 7043323512767708227068106249739951491043976377615496048093685452067553084035542590438128813773092040851301586842511103973860806631773727871710157387465685, 771339027639138775420697729026092729332491824629125081130247592473510452064957637544447168376529691848901640004353779830694590079796428248881709585961613, 5107403663579189520817333498915383809397751101703446127305785681428015061372625496792288537806047733638948275022016916546271837103709480100425546700739924, 327625569051205783001634588919193968189999837217354226746484572746154000339962037951450426985668670993855854016093289902451644873913868601670655500480116, 3844386014301870281302481856989707789687373446050245288780153617187119070897888828748336648704843190766231287738013119323033296349182601534367731306782090, 1572886196768069505956934970621366637835528432742348132960444043064980088311451130089804664015119816433120990190803444046551246465086459013483503289931439, 5183342944040765200145387941659911442339319823106589753277893727424430775596493960008538338589975457662959659009720024679315632637522172046907240132350140, 8359873648984042009928346464358777678731611745070054281943398862675716531347103634736177553748613173279303312585989579612319266920778230864475251897670383, 3542440849515671764245444098065024121872877054188470320724200105581264890278223486811811807550355733881152361680678815274456054529170293443494753263026006, 4261560032688111531704793847799458814235484033734374922142230511378966550625674132727287602439647592510145362934545646947123374874304162572641831568881486, 1707697727434220595134773797359426162462622658098969049607495505366434398108543395575866332108187580829080804949524651134194019912682813152700821774897687, 3395853840689150295756287201139152843675662234182032587021968652206166867611006426170254846494155261214610677409815738266406821975394045295260889839361777, 8658526268131962586752958410696961915030576463742608914688955078602071158134323328708695344759929277645023728071322266529152092796689541498377659071409189, 8144322667589876601711320985735789433829456855964892238034006464939367262733195958873005994083554693818284983548765519346418205984769507823532243908208422, 7785561762114561866994108383868364775151662846998527967561563041676911284661487594612516665431339133656480150262125458060270686837542315752757418136111966, 6227309745810560543198525057161686158388230118345665579738531381516868651117164520134047404161656576591438017085034989866009881352138939397850680211150321, 7839516692429743565681997707058527738691454956113408586733307121111752316549141113264286651492969596292708972511570097549781342331349903296760729058531524, 4739982437276363971519428579425699840338308555077570772534554688155796024995305793273311400661532761046294860221604320927651615333611383861185442535716781, 5023316340491752126741235821839975404001778228704263598835524219295613328618889880638859698252638003971110778169219799169827154016250695398915137163461518, 7004350722421597402834833979543835943558529591356944997947808950667888256314229088405739590176682081085740219914031242094208559184344820867719031880944459, 7581229899370264076529387872782508642606665074066493115745166218505936651631422923172340308060768370860059918666422433668636634462102002811138189914307095, 6143414630268440619666035518117120336697807584321603105150320178196266927582882618290252226590973875639180087528088999784904417586905758948504628361881857, 3348578789693846839488242683933929108730015397853655782644321493736955447917491476346062039530170362778037824592847400176272646937909800067684830905333992, 6199808281177418988528398071607863897759981560904152975641760811082772421388618436514892017128009492018150868934753765541732786357520596122029192546495067, 2985233625598944757818530375335390760187890131662490091010559461341989503812245452629843069501618105307975720029631745581861164110375579962357774066504644, 4246237565619791590370006629971737793862431087036064552569995617988013184107419981128181505878061920653766518535204042505403083800724487661608572807939152, 8380645024042095112890710070421181154514214161906165377120515698056657322595571828915138757430747671689694275795632646610484305734392519361921886893062833, 7350944967943867097984410095546362328396133373233163791400964792119530630181106238060830995394047745006949528187884649554703298569712383896479722690989766, 4738267603155740107142268680149512322970321427128158702697002896431175180296687818106258763294825068763126765762309765758572436597141243652705232731431335, 7930252444584766351309332675268183069653894316494030041508321104248778249679074318058500554163493412514806160599801810621152596712138052540935761086321011, 2974017948811294692697911486779614866029622967719614194502434383935484010338139122483699041680185072056709259159476865804830077246112732254331833426374165, 756647626686619420177777231375627925528482170684690309768586402102435454954873251070655267625472012700941253166698783169047205013254691582758760398744700, 1601975740086103139330089304328216565180305167310534990991729204041046260080344583154195140600034646009894327025378354036115444720718199960597999315357818, 8353870129987376202655331339252907656587295755447817704764534268660795533210673987694728983150379548987945071699609476021258357467925524018908787969143458, 2493263386315865665148248027073759861488839875821105781915340280816393339281378662533535732494013046391954388745230217002721209011499600978595608851419687, 4388464158002932704841191883629105858829407681357691203651996053193043883241936358829927958345840299970381633729316511076465889862824130623876668626216714, 5877540829064126214493567812360753229451325659241512569746561124317215290349040268561580377671280022790358374317135862046151891668215577008586213054572044, 5685977902595316635087198667084796063956787102521833643100961522266386749796547354579985137003128328723397415600174921039080670838311190932888801559723078, 3367617961952324158371702082158564467668156948272257381872749769849530193645721870660839707487620187227495835522233612414849305269536853263786929645478894, 3628523137158330903375949456562299935575151028665176105789690055344359991138094488921333143279772432143530602329800978279477076602941142834436217245697193, 2250963329400427427938672169148899524736332216116763709098632466918382985287923410568742544844101080880133496012827197701602294447771343104263506236855002, 8590983425597464006144993783937663661380201632166572002675516300929220859030826779826476681062448374609580993918444303700239760497291475783137496609926033, 4103239359377892979059990269367047865683540677428736810988222228378263813097020737887160921870201393495564214699822865381055385999826459121797150461582564, 235563734754835975863193735520104108185690533341027616684260978526082415741268765316031985031962148556238542191320772127767081125010569536226095975160773, 7130077431153489139494792114315322200051281063866424698783273214119412523382070423291540408534432889150932533431160693314986965183350344139688423805300725, 1236074319217562629622618499574203965020102269470559699708485744492249312114386633063827022157338763939282766947228478884521428070545887693331694379623084, 1505253614226160553420560801060095474639332898114013231849144785855067796388194759347713536482743287303287102663082365748627486461862967238683359830193213, 4861283617064058342162063088940402217279287517126234878965011803878524355828013654710727964593363536741589380891263504888869933623586795026653694036948739, 1086841376358065173855060973234190626741686184278393868413272365377194708614823630786347322865510096601936998277497089080212545337190838040826750818109022, 8675621600124474515814825814073020547094198271106905556339488155563005582732574658880009151447909101030504025842067371298354787750935518049982966278798075, 6451021818935003140938246115617847885707775810625831133231469622435509581171515118905840107771515804345012782137589782291404935097640555963866786636587779, 2249197209960506301770179222836377244258865188935488217005538297405642563994600679178570702625506567164260942928098572549185569989355815360339453976391061, 4260893291752065404595331092029237781404066642452203691342767029061023890901187104807201519212824569372149789868924286113215033823773531713272237979220462, 4670552441666333354166724458533238169886149290591916512066930327326025037793876278447836390011482571828594024646477931713583518452899608041933528693851340]]

解题思路

解法一
这里先观察generate_poly函数，它给出了一个模n的多项式的生成。这里的res相当于
$res = \sum_{i=1}^{num+1}{poly_iX^{i+1}} \pmod {modlus}$
方便看点：

r = \sum_{i=1}^{n+1}{P_iX^{i+1} \pmod p}

也就是说poly是这个多项式的系数，res是满足 $X=root$ 时的求和。然后函数返回一列表，第一项是一个常数项（模数减去res），后面就是作为系数的poly。
理论上如果解出root，那么代回[modulus-res] + poly生成的多项式去，可以得到modulus的倍数，之后做gcd就行。
给出的gift里有 $a \rightarrow k*a$ 这样的关系，可以考虑用related attack。
对关于a的两个多项式做多项式gcd，可以得到一个多项式的公因数 $(x-a)$ 。
为了得到a，直接令得到的公因数式子 $-(x-a) \Leftrightarrow -x + a$ ，此时得到的新式子的常数项就是a。(注意，这里的运算都是在模n的情况下)。
知道了根a，就代回原来生成的多项式去，得到p。

exp.py

from Crypto.Util.number import bytes_to_long

poly = lambda coe,x: sum(coe[i-1]*x^i for i in range(1,len(coe)+1))

k = bytes_to_long(b'flag{a5537b232c1ab750e0db61ec352504a301b7b212}')
# print(k)
P.<a> = PolynomialRing(Zmod(n))
f1 = poly(gift[0][1:],a)+gift[0][0]
f2 = poly(gift[1][1:],k*a)+gift[1][0]

def gcdf(g1, g2):
    try:
        while g2:
            g1, g2 = g2, g1 % g2
    except:
        pass
    return g1.monic()

a = -gcdf(f1,f2)[0]
# print(a)
p = int(gcd(int(f1(a)),n))
print(p)
q = n // p
d = pow(0x10001,-1,(p-1)*(q-1))
m = pow(c,d,n)
print(bytes.fromhex(hex(m)[2:]))

解法二
看了别人的wp，有一种groebner basis的解法。其实多项式gcd跟groebner basis 其实是可以相互转换的，先留个坑。下面是exp：

exp2.py

from Crypto.Util.number import bytes_to_long

poly = lambda coe,x: sum(coe[i-1]*x^i for i in range(1,len(coe)+1))

k = bytes_to_long(b'flag{a5537b232c1ab750e0db61ec352504a301b7b212}')
# print(k)
P.<a,ka> = PolynomialRing(Zmod(n))
f1 = poly(gift[0][1:],a)+gift[0][0]
f2 = poly(gift[1][1:],ka)+gift[1][0]

res = Ideal([f1,f2,ka-k*a]).groebner_basis()
print(res)
p = res[2]
# print(p)
# print(is_prime(p))

q = n // int(p)
d = pow(0x10001,-1,(p-1)*(q-1))
m = pow(c,d,n)
print(bytes.fromhex(hex(m)[2:]))

# b'flag{e6d7511d75bd537e1bd0cd08abea415f5f27d6cf}'

用groebner basis 就有个好处，这个算法它能直接把p给求得。

strange_rsa3

题目描述

strange_rsa3.py

from Crypto.Util.number import *
from secret import flag3


qBits = 2048
pBits = 512
num = 2
q = getPrime(qBits)
p = [getPrime(pBits) for _ in range(num)]
r = [getRandomRange(1, 2**(pBits * 2))]

a = getRandomRange(1, 2**pBits)
gift = (p[0] * a - p[1]) * inverse(getRandomRange(1, 2**pBits), p[0] * p[1]**2) % (p[0] * p[1]**2)
r.append(a * r[0] % p[1]**2)

n = [p[i] * q + r[i] for i in range(num)]
e = 0x10001
c = pow(bytes_to_long(flag3), e, q)

output = open('output.txt', 'w')
output.write('n = ' + str(n) + '\n')
output.write('c = ' + str(c) + '\n')
output.write('gift = ' + str(gift) + '\n')

output.txt

1
2
3

n = [334024028297795358428409534536782438908850190596668304865805437854374647984162763213581202801755428896203566172506219587266859416880045688129543855047675462354257676254231028533265496444966553195988075269677126779791155950793986187076641998741755872346979307739639779735262978907659727511419480461209503641512912873117056664008629779726881137366723127568036608925132936367006658464077463797854166622020483102972486974655232026096153672010479488999300909745157075526157596970246521452157940857495163175605553461432715056788388724755538433445976849818771932805940067427962262593386608298455471107791678224956504101174392785507134071131842103995133811964997751791768061100121699973057595724142612170517768245173187399850847945628945800042668385798893530527806229363060713249, 270672332309468804376393577492871858269490099887383011988714622534037610808764741901954257217313289938393835900354736668003700671505047142365053976908516056996483106174902631762442253779775073373220342445779447626486345253598470015470094856727845150372622299396840670432953284676150980428391739322739397783248924710490946083987879121564403742528241040454099534823772379455574658130173290640751198753015984316400694738114541263533626932367096040344071742474883684682734122111076840572805111010694147825191233741720325878397443178835435703420465683485344417909319591496135706730327376897531024858122747777315158814568580929655522627811650949169204543250919027738723235091257934106114809110289433115714333069841583284243937630033653684708127947780848521445941847102881070046]
c = 24426016715355498456650532748209528249200902516644306644652290745346403378221744208791754411669322694597831272399935610924080672864361088045894354412944203199767471898920740773322967470374385635042086816010876203117884874681450622109443867183037282062248951073356702181165103759051513426785435705002047708435055880616309144483691648077981524802908185706596363674820857151388761087408514551645305031742705266691826719380663571699663832536944531865183586885154128228789310222929701360939023228059118720311899056620389378996862413971733056546988166759451010742768802840638380019172710929867945108511664271273569394689619
gift = 173299379625576798749821685155193435290573235640007530711924098468561852299646118206367598564087551037396665586630782838190274697684611102346492601699992667822233634078800006099513099432664305226448819277556828816420517850404262393535832488384876680039695417291460237594174659357055221582914415278609167623124281569332881993050546046852564902573985929794261636296569394448935231131668411811662581097119330330246497311885207256858435515769776396794250803110128999

解题思路

也是先看加密部分，n给了两个元素，生成的形式跟AGCD一样。需要求得q来解密。
对于给的gift，a 和 inverse(getRandomRange(1, 2**pBits) 都比较小（模了等于没模xD，然后可以考虑把 b = inverse(getRandomRange(1, 2**pBits) 移到式子左边。

b \cdot gift \equiv a \cdot p_0 - p_1 \pmod {p_0*p_1^2} \tag 1

对列表n有这样的式子

n_0 = p_0 \cdot q + r_0

n_1 = p_1 \cdot q + r_1

符合AGCD的形式，然后构造格子

B = Matrix(ZZ,[
    [2**1024,n[1]],
    [0,-n[0]]
])

L = B.LLL()
print(L)

p0,p1 = map(abs,B.solve_left(L[0]))
print(p0,p1)

对于gift ，大部分参数都已经知道，只需要求未知小量a，b

C = Matrix(ZZ,[
    [p0*p1*p1,0,0],
    [p0*inverse_mod(gift,p0*(p1^2)),1,0],
    [p1*inverse_mod(gift,p0*(p1^2)),0,2^512]
])

LC = C.LLL()
print(LC[0][2] == 2**512)

b,a = map(abs,LC[0][:2])
print(a,b)

知道a，b，p0，p1后，就能求得r，然后反推出q

r0 = (-L[0][1])*pow(b*gift,-1,p0*(p1^2)) % (p0*p1^2)
print(-L[0][1])
print(p0*p1^2)
print(r0)

q = int((n[0] - r0) // p0)
print(q)

# print(is_prime(q))

d = pow(0x10001,-1,q-1)

m = pow(c,d,q)
print(m)
print(bytes.fromhex(hex(m)[2:]))

分析留个坑先（
完整代码

exp.py

B = Matrix(ZZ,[
    [2**1024,n[1]],
    [0,-n[0]]
])

L = B.LLL()
# print(L)

p0,p1 = map(abs,B.solve_left(L[0]))
# print(p0,p1)

C = Matrix(ZZ,[
    [p0*p1*p1,0,0],
    [p0*inverse_mod(gift,p0*(p1^2)),1,0],
    [p1*inverse_mod(gift,p0*(p1^2)),0,2^512]
])

LC = C.LLL()
# print(LC[0][2] == 2**512)

b,a = map(abs,LC[0][:2])
# print(a,b)

r0 = (-L[0][1])*pow(b*gift,-1,p0*(p1^2)) % (p0*p1^2)
# print(-L[0][1])
# print(p0*p1^2)
# print(r0)

q = int((n[0] - r0) // p0)
# print(q)

# print(is_prime(q))

d = pow(0x10001,-1,q-1)
m = pow(c,d,q)
# print(m)
print(bytes.fromhex(hex(m)[2:]))

# b'flag{bbfd3b8cc77896de867998bab7659e2fbce6378f}'

总结

真的还好吧，质量可以了。搜的wp都没有完整解释，还有这样那样的问题。也学了新东西，有理数域，多项式GCD，groebner，AGCD这些。