Jump to content
BinaryBrother

_GetPrime() returns larger primes, 300 digits+

Recommended Posts

BinaryBrother

This function returns 300+ digit primes, by pulling them from http://primes.utm.edu. The site that I'm using gets pretty sporadic with the content, but this is what I came up with.

I couldn't find much assistance for generating primes this large. I'm working on getting a complete mirror of the database, so I can implement a local function that doesn't require internet access. I somewhat like the idea of a cached approach, rather than actually finding a prime this large, as it would be very fast.

#include-once
#include <Array.au3>

Func _GetPrime($pStart, $pStop = 1000)
    Local $lPrime_Index, $lPrime_Pointers[1], $lPrime_Source, $lPrime_Dirty[1], $lPrime_Clean
    Local $lPrimes_Array[1]
    $lPrime_Index = BinaryToString(InetRead("http://primes.utm.edu/curios/index.php?start=" & $pStart & "&stop=" & $pStop, 1))
    $lPrime_Pointers = StringRegExp($lPrime_Index, '(page\.php\?number_id=\d{1,10})\" title\=\"prime\"\>', 3)
    If IsArray($lPrime_Pointers) Then
        For $N = 0 To UBound($lPrime_Pointers) - 1
            $lPrime_Source = BinaryToString(InetRead("http://primes.utm.edu/curios/" & $lPrime_Pointers[$N] & "&showall=Show+all+digits%3F", 1))
            $lPrime_Dirty = StringRegExp($lPrime_Source, "\<code\>(?s)(.+)\<\/code>", 1)
            If IsArray($lPrime_Dirty) Then
                $lPrime_Clean = StringRegExpReplace($lPrime_Dirty[0], "(\&nbsp\;|\<br\>|\s)", "")
                _ArrayAdd($lPrimes_Array, $lPrime_Clean)
                $lPrimes_Array[0] = UBound($lPrimes_Array) - 1
            EndIf
        Next
        Return $lPrimes_Array[Random(1, $lPrimes_Array[0], 1)]
    EndIf
EndFunc   ;==>_GetPrime

Use:

$RandomPrime = _GetPrime(350,500); Random prime, between 350 and 500 digits.

 

Here is the 'cached' prototype that I'm working on...

Func _GetPrimeLocal($pMin, $pMax = 1000)
    Local $lUsable_Primes[1], $lPrimes_Cache
    $lCache = "2357111317192329313741434753596167717379838997101103107109113127131137139149151157163167173179181191193197199211223227229233239241251257263269271277281283293307311313317331337347349353359367373379383389397401409419421431433439443449457461463467479487491499503509521523541547557563569571577587593599601607613617619631641643647653659661673677683691701709719,7891234567891234567891234567891234567891234567891234567891234567891234567891234567891234567891234567891234567891234567891234567891234567891234567891234567891234567891234567891234567891234567891234567891234567891234567891234567891234567891234567891234567891234567891234567891234567891234567891234567891234567891234567891234567891234567891234567891234567891,718281828459045235360287471352662497757247093699959574966967627724076630353547594571382178525166427427466391932003059921817413596629043572900334295260595630738132328627943490763233829880753195251019011573834187930702154089149934884167509244761460668082264800168477411853742345442437107539077744992069551702761838606261331384583000752044933826560297606737113,23232323232323232323232323232323232323232323231919191919191919191919191919191919191917171717171717171717171717171717171313131313131313131313131311111111111111111111117777777555553335555577777771111111111111111111111131313131313131313131313131717171717171717171717171717171717191919191919191919191919191919191919192323232323232323232323232323232323232323232323,1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567,3357919051293446684817338475525336738410860683671992917156014373893439459981205349461903840857391256114552436727030705242812636090289386090253261128312388690032525006703900566545832881453504420702454161952515801782756924440723510485553617697701860843302292487377415029400870876382968571950877132931544109243793366659520676094343242287408182490885436245732490266782865577,147905612304049314530022347858051795393169843567686496119778103525328675398119462130526918624189025093221823879535477996560410449665190880468513606241420472470681055332721887591747863405964601930591007609161946038677991696595604464433826327996801243951556854274701334312260550305897135170116383049658549024443746904511563699126930309386309517504941636470564772320067276393,11243941652563674986498110100111211214413169141961522516256172891832419361204002144122484235292457625625266762772928784298413090031961321024331089341156351225361296371369381444391521401600411681421764431849441936452025462116472209482304492401502500512601522704532809542916553025563136573249583364593481603600613721623844633969644096654225664356674489684624694761704900715041725184735329,315791951375393537137595555337555955191395351995195751755791151795317131135377351919777977373317997317733397199751739199735799971153399111973979977771537137371797357935195531355957399953977139577337393111951779135151171355371173379337573915193973715113971779315731713793579595533511197399993313719939759551175175337795317333957313779755351991151933337157555517575773115995775199513553337335137111,24467476921682913438488192789239875454052536352549377837017690003767392142115603881393841041310716327816213613354449520915894649236940295705032203772143700063945600771074430370325781739206543222519232991385636612822084739163686757649627381681950058593932837672011365718824444153413729381893208613692665940794284282462079335312142411834200416495641677380129898882762716949168399500016681107627423520001,19999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999" & _
            "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999,30369914685909658652106967844955538168079478716975369303623809731000205970022875045834819836097482525947050603139387707707707707707707707707707707707707707707707707707707707707707707707707707707707707707707707707707707707707707707707707707707707707707707707707707707707707707707707707707677337793021798049055600739862752169539628228990732338404083897976707501737684832661872887871610225181760657104568319,23111347539713119724140943160767373975198399111031433148915311553170917212371239324472633278928332897304131093217337133733527354735933671369140574153421142974363440944514517451947294903496950595081553160296481656968336911704372197297745975377559758376037691772780118101816785398573896989719013913793119377951196199643972197439851994110247102711036910391104571045910501105671065710691108311090911087111971127311779,108540871852024137837529457366425345163408989164877909166491842616641991981135011689476695849803941790591401795168969498249897355324768178088518513156026831828793854471326717801604260274446021846541136205357444802749291495386649979610567642710417177711042509688835903368099465519253326878312637499376794203125671816898434564095999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999,1247658889972860411147035925998317265009144137351310869434160680300829996526696305806135205829395145563881475481128308055393359258093618892415479514586715923854428061641685352042395341528722373249432456770472489676158608005616151666468795670611887371658561987387950574168107860744010500989329661046967451575035815400474716679716898697053520240386503959948292135398276882924396308379934119693310960583565643442779048841835736641,333333333323333333333333333333323333333333333333333323333333333333333333323333333333333333333323333333333333333333323333333333333333333323333333333333333333323333333333333333333323333333333333333333323333333333222222222222222222222333333333323333333333333333333323333333333333333333323333333333333333333323333333333333333333323333333333333333333323333333333333333333323333333333333333333323333333333333333333323333333333333333333323333333333,10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000451,19869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869869861,76666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666667,9734471572819574918623369660869466987125523927747490023587668111496196939792351125148996897038754440454452803638299813520465182998315590857195316599148406551634095445602090321059306383740503893283630788427372259194749483919228961342613468942155223319295602778842794797030462426842918697703604268261127857790178424744625937769080399899366133345348959370145333815420464679055893736124926501" & _
            "6513184863293742099074092675297451334222515563705769519100012093174349,10090000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001013000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000101900000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010210000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001031,48888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888881,1223330000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000333221,158315471626780934086237387536684831978123267410552693833973111248384519653786919050180309437564690815940063185306426545663780897012126239351462572681789897003108212315417518618618618618618618618618618618618618618618618618618618618618618618618618618618618618618618618618618619628616567704415883173152839513414964899507293140595864807679928585958582897670745849503119169479744931229473623106925831137646258552288549227637075815833085499446074897559439953073164073165170557701,33229159612484779776592692453015937833742587231313549322471188388859860608230489118172504368174532575496744353711363918947598515643519074887501723383342696157701656044621841473480812153639625878742168095538916210443704099436882726076735942533610577481148320247327057038277038149923158464559950389918932947962976752229383037388830600189989790244599021019248528828241308479745300458276100912908398768483185285741973849115226596045243779731503091210662840160861494626156693622624507047899,2357111317192329313741434753596167717379838997101103107109113127131137139149151157163167173179181191193197199211223227229233239241251257263269271277281283293307311313317331337347349353359367373379383389397401409419421431433439443449457461463467479487491499503509521523541547557563569571577587593599601607613617619631641643647653659661673677683691701709719727733739743751757761769773787797809811821823827829839853857859863877881883887907911919929937941947953967971977983991997100910131019102110311033,10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000174295123051,168132340078966991479234843040214163814008879131005050199982686052275192862579281812200842498176844243480333541539804441269656855795790246718536005661390200961918084704920716014351507531406253948235628729161481417569772046047249313751887076455262444135248318465774602119797030821262907700716028329774917209760128807430324977084247794037397579051560003510237512296214214982383281629297197445267713301690633987314268086933159403403240453840213576426105549310423978241810065948770795631639703034173006193345651,76365326439828205119501781410601211048154995395541151761934" & _
            "5534683446798214401532151525415530941440800539252620761045131556784082309435674124952532098768790347657301075728630489953153053698915918184279961736931458633176899220705352982796605582699123037792296334286436389915443822916890735794189661745441875558670046732937263678647320341622510029341996692008473793812037794115485328690841738796710968017578124999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999,1111111111111111111111111111111111111111111111115555555555555555555555555555555555555555555551155111155511115551111155155555555555155111115511551555155155515555155551155555555511551555555115515551551555155551555515155555551515511155551155111155511115555515555155155555155155155555511551555555155155555155551555155515551551555555115515555551555155551555515555151555515515555551155155555515551551111155155555155555155111115511555555555555555555555555555555555555555555555111111111111111111111111111111111111111111111111,995865598681084955071398338040330206911346258525245463691116582002007718603506959845369510301631683733886098830894818404647480129705482845136159532281053407272929387855550327271381011499489059845661884239345604351886727494252497426228673080502659460769377681225800781745878691664520425311046982229541310916818702900666031093689413988686004455214673197308021346521837339851069178809384641929724275861231114737882928237519964598335251789138246628330684547230179473963454820331455303852119095261585415619291037838364422981,1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111118888888888888111111111188888888888881111111111888888888888811111111118888888888888111111111188888888888881111111111888888888888811111111118888888888888111111111188888888888881111111111888888888888811111111118888888888888111111111188888888888881111111111888888888888811111111118888888888888111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111,40254158729574674675380496515460635716718179931464917469531979849600647989842597784967077617230860958351283100476063654884317342919984483528863644958223132062537790724232408408659779640008076663589284180306086600272781178316422394046751212546244439245994872833051601724913519810094273178281976501412145269089669792061662706245133139078143212730507878096361621391776713871877524915091729969565749727693367626370715643670170603423002549532126514568224267916950054996279889572076004793672222123544627814089545396962467645516102286318326190437,15850287302405806989978944349385941354707030790876164780905675677643030247259589275366361051578825078176240141310254667849680779101315548683724799285897026979906806773410231607398526949479356399250883782954407239898818480058626343922829621691163004604665060668501224758888620152958447270466551869196967288475211371692168859786228896584510580924825331727538884275467860448532339877581732712750235889233707226418967968690708871280311846962390644994683635128901553212959925784734789271836344997303909184934778008187556102505805885211020613386241,1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461284756482337867831652712019091456485669234603486104543266482133936072602491412737245870066063155881748815209209628292540917153643678925903600113305305488204665213841469519415116094330572703657595919530921861173819326117931051185480744623799627495673518857527248912279381830119491298336733624406566430860213949463952247371907021,1357924680135792468013579246801357924680135792468013579246801357924680135792468013579246801357924680135792468013579246801357924680135792468013579246801357924680135792468013579246801357924680135792468013579246801357924680135792468013579246801357924680135792468013579246801357924680135792468013579246801357924680135792468013579246801357924680135792" & _
            "4680135792468013579246801357924680135792468013579246801357924680135792468013579246801357924680135792468013579246801357924680135792468013579246801357924680135792468013579246801357924680135792468013579246801,200311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111112003,311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111,123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901,123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567,12944444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444129,76666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666667,1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000" & _
            "000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000543,555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555555551,703000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000307,4531237355389378252167998204069912329623238122031742525328375168700640071230382841176538537641410229241210453089727044117359137139455328859431837448826486544033819286028482023523368963132036246337749117510181791772392419630160691233539397666404977367459896404859268755714147264101378375452001615625546366367347635604604983153448409986447938745141330803902556457519623807485807874059361289422468644305915480952509665275858944824184377172418429729023520527815721212827456904706203130970930562002244147732153879979550528775145262679261139839149750738281823331233898450596958081662801176207041676910592588281955660174518029203,2468101214161820222426283032343638404244464850525456586062646668707274767880828486889092949698100102104106108110112114116118120122124126128130132134136138140142144146148150152154156158160162164166168170172174176178180182184186188190192194196198200202204206208210212214216218220222224226228230232234236238240242244246248250252254256258260262264266268270272274276278280282284286288290292294296298300302304306308310312314316318320322324326328330332334336338340342344346348350352354356358360362364366368370372374376378380382384386388390392394396398400402404406408410412414416418420422424426428430432434436438440442444446448450451,121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121212121,702079226394599267735191841413128874795247805490517054276340557155948943570099062636753289411154623672004867308640920603807694718006489892779925062138618515629872757368947667539951593306987479811638187121088483515360221935971126625400671012753343761397211280160501540278806457364464956441544244610516403573071554299443696418311471338159713528505050660205171647730521360774909493612839872795981479630114537859390310673838221447860778239988727101763027517463616482160397971523167080327549594766566010372471784045891758833973532140862388344166251701537850595095780193783149508070051871170910983223951139145060424748526226517327333826692719,1732050807568877293527446341505872366942805253810380628055806979" & _
            "4519330169088000370811461867572485756756261414154067030299699450949989524788116555120943736485280932319023055820679748201010846749232650153123432669033228866506722546689218379712270471316603678615880190499865373798593894676503475065760507566183481296061009476021871903250831458295239598329977898245082887144638329173472241639845878553976679580638183536661108431737808943783161020883055249016700235207111442886959909563657970871684980728994932964842830207864086039887386975375823173178313959929830078387028770539133695633121037072640192491067682311992883756411414220167427521023,66666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666663333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333334000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000033333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333336666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666666667,100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000123,100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000166657,100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000260487,100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000005259048033991,1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111" & _
            "11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111,111511111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111,333333333333333333333333333333333333333333333333333333333333333333333331333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333,999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999994999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999,999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999998843,1702227532314572632785843152634373310716567344098231328811349327252477474483503052590091452549833798337201702845064536591370723167163891857998691097553196285898495415302621430192358311580472852748596925513388124888373155732732674034723556586612896717526849516945074388633879724438660938048352211779096818726209619523749353156577429355252891177613173228339694594066541369977956232359689440821410065561326888052810472860207952236699308117466368308941132678939686610505565590472191012690904022278481431747501898431160635781208448932655728785292678947417227745152129899816757524258104088355582903319658232496430473711278503008631715363842540131864967823631956365613714869620277889,5555861076960184508403211776496369033897918723969441195461219781764269875834" & _
            "5854432054120170830714766464188007124699226386623422387769456601176448956639325334537116275182973025840249128269412580280436561380140570587351647498514970765269750764472034037444958854210834276380918003970357231651598262223096012857397343437198448323531581388309338876444647380924682260339504523027125448155104599046828313551545739370286071676941209229143837472675844264230173707541208165228259972996459002751062573298411402344252697111948207941349668125541583535558456937012199450299952011671765759602629849268239727951048247103741366554054627352274368579415801299207137433624252756056310758472298250621,6660000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000007,488206692078974757239578751106501798481193064305790060593268437941627128786518531687782038367395832494215303395275266261062870163042743713567477092591560354372022298711585313960166069663510866751747594454428370134263085036017021235153166806087444438422225508307090473714775930968942163305842969968960054562144882959808916790127856236878924126832766246591681391552185769201675241103805718565160271127279144286915245849425395672583677793953258530912351358504190352840627804277371662423874093878957332436516983050363505381795724757049138580227182965779234414020354586369950286426688735805438813033123751256021943190348046084856883806613660223368049593031293490849051397554356373996859058494329846897,26012189435657951002049032270810436111915218750169457857275418378508356311569473822406785779581304570826199205758922472595366415651620520158737919845877408325291052446903888118841237643411919510455053466586162432719401971139098455367272785370993456298555867193697740700037004307837589974206767840169672078462806292290321071616698672605489884455142571939854994489395944960640451323621402659861930732493697704776060676806701764916694030348199618814556251955925669188308255149429475965372748456246288242345265977897377408964665539924359287862125159674832209760295056966999272846705637471375330192483135870761254126834158601294475660114554207495899525635430682886346310849656506827715529962567908452357025521,1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111709,700000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000007670000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000" & _
            "0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000007,13000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000006660000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000031,162682049806175057753884851265330486328063919520755558292790805460031029454643346312271117690914484504894844599049076244329848696273213558195548539272627523837153825097961378488188779184431865046448473874606934473056822559308822160857085968868655553841035686341276698823661412396513266491118997706075183256507481578278688857068967270286738721667063497626807848418636676499873726375316499519571764658910990177486523922469808513131799441816805195234129227862329385123878613676085406492561665353908330849804756218502245500557960620845531352399179303254558466512999685026775985792923990792201336571037334333443149429381091104563438543832563401680689989126004779208220421880731832533985489677884766515838571522508297557358491478403959999999999999999999999999999999,314159000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000951413,377777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777,79778777376976175775174373973372771970970169168367767366165965364764364163161961761360760159959358757757156956355754754152352150950349949148747946746346145744944343943343142141940940139738938337937336735935334934733733131731331130729328328127727126926325725124123923322922722321119919719319118117917316716315715114913913713112711310910710310197898379737167615953474341373129231917131175322357111317192329313741434753596167717379838997101103107109113127131137139149151157163167173179181191193197199211223227229233239241251257263269271277281283293307311313317331337347349353359367373379383389397401409419421431433439443449457461463467479487491499503509521523541547557563569571577587593599601607613617619631641643647653659661673677683691701709719727733739743751757761769773787797,10000000000000000000" & _
            "0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001777,12346811131618262836384748535762697277828797991021061141261311381451481551751771801821891972062092192212362382412432532582602732823093163193243393413563583633703823904004024094124144294314344414514564834854975025225245445465665685856026056076126246276466686736856886906957207227327347397517817837988008208478498618648668918939059279499839869911018102010231025103010321035103710521079108111011103112511551157116411671169118611911208123012521257129613081311131313351338134013551360137713871389140414061428143114331462146514701472148914921509151415161531153615381550155315941602160416161641164316461648166016821707170917211724174817651770179017921812181418341836185318561858190019021919194119441946196619681985201020122032203420542056209020932095211221152117213421562178224722492252225422882327,5444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444443,2204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608802204406608809,2244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244442244449,23158298834967953" & _
            "01383382804603744820179489984338956584969728297097203344559501549797662853927814168579973331645551905688822529808042732543304747028003221007625742691494727455821218639638651699682292802220170616629519071769161210904553553690676633551397477721451660528361887347565234018369333137499437710829407347371582615660227727307345508599735199984149427690377444700272476480847341703153978952472467092030042730494489512166097742529279067450669005265469379026352244807268239696526807378394020418341619413193808133276619790512991018749634886746411102521482772263689241012979559749865915102584005335959009797719023288886831297081617492271894450156894535182140736993138742911291801835481351584345905920276899976463338044802157665975863487827899941464374672315100140360072256500639806806717991586108902921739369139601,12345432123454321234543212345432123454321234543212345432123454321234543212345432123454321234543212345432123454321234543212345432123454321234543212345432123454321234543212345432123454321234543212345432123454321234543212345432123454321234543212345432123454321234543212345432123454321234543212345432123454321234543212345432123454321234543212345432123454321234543212345432123454321234543212345432123454321234543212345432123454321234543212345432123454321234543212345432123454321234543212345432123454321234543212345432123454321234543212345432123454321234543212345432123454321234543212345432123454321234543212345432123454321234543212345432123454321234543212345432123454321234543212345432123454321234543212345432123454321234543212345432123454321234543212345432123454321234543212345432123454321234543212345432123454321234543212345432123454321,17481745174417421733172717251724171717061697167916701666166316361607159915871582158115781575157415721557154715331528152715211518151215111487148414811478147514741472145714481447144414271418141113931390137313661353133913371335133313321330132313091303130012991290128812851281127712751274125812571251124712331222122112181215121212111209118811851184118211771158115211511148114111281125112211211115111411121093109210901088107610671039103310301029100910031000998989973970964946940937932931923921913912910907904901899888881874863860847836833820818806802793790784763761748739736716709700694683680673671665656655653649644638637635632623622617608566565563556536496490487478469464446440409404397392391386383379376368367365362356338331329326320319313310302301293291280263262239236230226219208203193192190188176167139133130129109103100979491868279706849443231282319131071,1124394165256367498649811010011121121441316914196152251625617289183241936120400214412248423529245762562526676277292878429841309003196132102433108934115635122536129637136938144439152140160041168142176443184944193645202546211647220948230449240150250051260152270453280954291655302556313657324958336459348160360061372162384463396964409665422566435667448968462469476170490071504172518473532974547675562576577677592978608479624180640081656182672483688984705685722586739687756988774489792190810091828192846493864994883695902596921697940998960499980110010000101102011021040410310609104108161051102510611236107114491081166410911881110121001111232111212544113127691141299611513225116134561171368911813924119141611201440012114641122148841231512912415376125156251261587612716129128163841291664113016900131171611321742413317689134179561351822513618496137187691381904413919321,40898219980579159776996317324898872026206132596748896017473279237518991353929463677591024072048450010528459772640149671692340908279693157095084879444206707543375421501800104093293396206327913172767083124373255134233429862782043334814006490625572442648203763894111035311575723357020097580891226344587271299971045219246901106481117933148034425902652444750180410250998723697379171162706552734412404674280441238292336977881260682908135520972114485319952173417748041535765966931238390420427790155703462917319601701463757346434291483411237900023585316357618620939711668086537259663194008474099373185233153917232179984927697346098159174126808639436090" & _
            "3553768936939187789113455022149939659910659453049038060214055742897470204709358474094423874469888000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001,1662295743651887468382899391713301043911099397389372738935506949203005239545819581206343769533358416361933461156980268632332144529435091525117278737248903911648763665664736134954791855328307393503485289264795900112740427393197845588597121927325467349170243136505228793256580860799335469210857412886478978168296421582390113660592741354112764866826441621720878206513474565234503591002803141103244967294524825349006195983486684005805606025840816100477682419836734146909602451654088826027842594169659725127881404965716477834249114173562663024501825242357394577182362981542251396473296485403547581269781642650910830035238836354448665068184166301928173932739548084478240036641398059850824589822200538086451624321102389114964825973542279270698123998373785260313866942512142243569170917682855520022962234345102373733016175075970899608017246947651945356618131650573860100480001,188888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888881,94547005113906444550092967769278693366458905022289787149508678380500658547107877688963133200816447475865903181500398223069421701682469846895352775062933280780994198564105265333454625084314006874655140951020428525441264820432986082000678669222872721350789756752010560690079446509850383148101390483994796016226100635363838422432461041613899207128518722088721656364479923851594876231365263866013098356062871257185310658090233647322143645842184223625364270095557239142116551241120398837682243428924234930126174181612463034415778283980959764368524689078864161430654527689567152459477708733464401446958719318157608776778257334149941882650860668841859967237978937666780682566994676099876979345083447022603175841330492614467613282199729121409933559694574074990111540914866135536618210560358040014112275153295692243935821889493881197110565594118529824787238592254052577207341235576372341117844388725202230195764060843081469,91100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000119,99999999999999999998888888888888888899877777777777777778998766666666666666678998763333333333333367899876355555555555553678998763511111111111153678998763514444444444415367899876351422222222" & _
            "22415367899876351422222222222415367899876351422444444442241536789987635142241111111422415367899876351422415555551422415367899876351422415333335142241536789987635142241536666351422415367899876351422415367776351422415367899876351422415367887635142241536789987635142241536781876351422415367899876351422415367887635142241536789987635142241536777635142241536789987635142241536666351422415367899876351422415333335142241536789987635142241555555142241536789987635142241111111422415367899876351422444444442241536789987635142222222222241536789987635142222222222415367899876351444444444441536789987635111111111111536789987635555555555555367899876333333333333336789987666666666666666789987777777777777777899888888888888888889999999999999999999,99009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009900990099009899,161803398874989484820458683436563811772030917980576286213544862270526046281890244970720720418939113748475408807538689175212663386222353693179318006076672635443338908659593958290563832266131992829026788067520876689250171169620703222104321626954862629631361443814975870122034080588795445474924618569536486444924104432077134494704956584678850987433944221254487706647809158846074998871240076521705751797883416625624940758906970400028121042762177111777805315317141010141713513508777111771267240121820004079609857049426526614388797157507125670042178899470648851908746607784452122449334789058876485659407494431770234401429444684635965816429474544597885080430221078579418344163136926268459626123401222307026961171052986678025760887620928299131662238365092859395956809833344536276670600813971396353222683366212571986835708804574847311939814027027079442098182640625072268445312682675089719030277118365634386854028484989478893308161,314159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196442881097566593344612847564823378678316527120190914564856692346034861045432664821339360726024914127372458700660631558817488152092096282925409171536436789259036001133053054882046652138414695194151160943305727036575959195309218611738193261179310511854807446237999732644708458115013971162391837116812903591959575630727503349061151491596414831256640288450350331100630952987634635171904529282690290251884718855136066007854273721419420627063933128466234540168430643296658465419091021725613876873328465748216443395665790188244691830394598492264469555011258391072014820547111848218049535271322850559064483907466032823156808412897607112435284308268998026826046187032954494790285015739939617914882059723833462648323979853562951413,97531000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000" & _
            "00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000013579,26239101565328447060123918373674208978057113438861141989421758423970142484856220671211540783481267429700502343921103065290527668576657458958751181596548043025978840356671379135035526791133596366969844506685702866779993614546634613735995117394967537659699529026318625947139301893733861951377177974947095636208281670411870225501930002039280164519618614673235015546735016608008486293006836388909056210080472677487844068176925946035205300259046187578968594213985258227747133005834004196532235834671954181477995365808482009389179411950537560608738910820545229319169642928070213324077932286053936103139431356939273283938800097532097593853875437260843652397331443383642274309393825122604552063024326652838634628304287106582401531785185099376401667669709198058340072348516352979897739267739309713198877460868256238769502465913139118724473655294382189475345342990425513867676000465717303803725163749093217046901269628895344388748833127,899999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999,2468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824682468246824681,1767641807025330119470850260411829130901448469376337871650915905863507856934515382801387942881085279937402376159112547633824833855741508843239602735830083248005025706354615217811575304279174894248088876448755409909675053984597246788325337400677386950286609023001699541498211138902891222397083099844523920039925390780300751562228477268001255246674544034239636404356819234492700414605077707513802067302563245703614181970727260412043912184208105881414114585649673145129539127844678637487889006427993393021617584528966465118467431324225454626113385285374754429177776355749284729587283653719759233840248367999018079517531390290200028903546898258861349424339147923118479206014510166806840448285548705520722596272930904107466459918149711841548434230326474750215508787461254" & _
            "15095293617377659928799085817944203573665671847458973219762174704549317792600078092813221320480219344767070054921514953156615109720228687984582173564348216778507099318258208317632199185942671379,7777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777772777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777,3281118110819871787138717771957135717471147133713271127190719961796139619661766136617561736172611261916131619061706110617951385197511751765195513551945134511351325111519941394198417841384118411741954135411541744193413341924172413241904199311831373176311631723112319131703130311031792119219821382197217721952194217321132192213221712131211021391178111811171136113511151192113211711190113011790139011901780196013601160115019401930133011301120191013101900179919938977917976935974914973992993794194795396797197798399199710091013101910211031103310391049105110611063106910871091109310971103110911171123112911511153116311711181118711931201121312171223122912311237124912591277127912831289129112971301130313071319132113271361136713731381139914091423142714291433143914471451145314591471148114831487148914931499151115231531154315491553155915671571157915831597160116071609161316191621162716371657166316671669169316971699170917211723173317411747175317591777178317871789180118111823,259117086013202627776246767922441530941818887553125427303974923161874019266586362086201209516800483406550695241733194177441689509238807017410377709597512042313066624082916353517952311186154862265604547691127595848775610568757931191017711408826252153849035830401185072116424747461823031471398340229288074545677907941037288235820705892351068433882986888616658650280927692080339605869308790500409503709875902119018371991620994002568935113136548829739112656797303241986517250116412703509705427773477972349821676443446668383119322540099648994051790241624056519054483690809616061625743042361721863339415852426431208737266591962061753535748892894599629195183082621860853400937932839420261866586142503251450773096274235376822938649407127700846077124211823080804139298087057504713825264571448379371125032081826126566649084251699453951887789613650248405739378594599444335231188280123660406262468609212150349937584782292237144339628858485938215738821232393687046160677362909315071,98888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888" & _
            "88888888888888888888888888888888888888888888888888888888888888888888888888888889,2850380883607027865606900730232209445429324581370553769881085623971362843343908341258933403790254408588473244662658415050905000326427946463672934034690013524563020829588490937617778310221130932639810256961418222279236076716143350581708022932381590599454412600075913327392849804210070837509778849709700680944565917798061674919826504950473304644390813548822301823398910176091271093151149094756283362131241037036140576211943620845804631805064242400070924270211378383157989922728839312906536621613614048464835438359706820978099174927773256141269983223146411906599115722605107895031444405379620074155938498202183092071853435364342302231804517668821825466382603344031666470804568398935790931717615232903011535287994446531578403326430642896782180090496036030255809214366925181689552585217270779031144158406724202195224580295523196665715362057213063027677310754582684342457188418915092254231697561722887241993957358497590330458835385625649594351716318328607817341144763818145596268917877435067458273,9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999997639,100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000041,11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111" & _
            "1111111111111111111111111111111111111111111111111111111111011010101111,111111111111111111111111111111111111111111111111111111111111111111111161111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111,777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777252253,777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777777773735353,88888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888" & _
            "8888888888888888888888888888888888888888888888888888888888888888111101,999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999997464799999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999,999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999599999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999,999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999993899,99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999" & _
            "9999999999999999999999999999999999999999999999999999999999999999974711,999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999948461,999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999494999,999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999648899,99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999" & _
            "9999999999999999999999999999999999999999999999999999999999999999809009,999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999579731,1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000005537073003,1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000167111761,100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000" & _
            "0000000000000000000000000000000000000000000000000000000000000000000526663,1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000018919,1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000073203,1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000473083,10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000" & _
            "00000000000000000000000000000000000000000000000000000000000000000100010000011,1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001975081,1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000019411,1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001880101,1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000" & _
            "000000000000000000000000000000000000000000000000000000000000000000000001598241813,1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000004114571944591,1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000007,1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000005352807,100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000" & _
            "0000000000000000000000000000000000000000000000000000000000000000000000000000041466567,1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000128594673,1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000004975694077,1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111511111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111,11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111211111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111" & _
            "11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111,1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111112887,1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111151191,1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111114144411,1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111114111111111" & _
            "111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111,1313879718456104225921995528497555855625152414017051819746489965175418594035237238181967239932841927943368022817082758088019245450978689926961358127631787144754373062120106902504163460853000843067796699510293924385333858122456855065858902248896798237625003273316840048212276610565777594650220087971045508055611314300070786176626378923084556948528977153135635206046615173944871186308702998089733796437598174864856900497873863589167218546523213052953471290292740839713119247294213720517263787354623928731924441813068650485005632246166869508621489664962699281739398162579362377493635567561343072827446535980932480283909225368443393486477711655376434350643031227524710815041165924570415486219444700695031601993251625411314037854648482400238147123249264167061961509379444920959953800364778020888142773659393688842351560111550969115614788364312559110854239694359378947557812483113318119934088060561737965196192041096299817733313038159648080136912212919336690293080257579650807503654066749005924284436981469,1332061140839377881275519727319087664563488856868363921090395424176003152616860694181381143398958886259607293657001126184200768318416415606007833158939494315794328961487646727235838064540020547096394715096987075662967270767111833128464892735927736680676281574819109293384227032660487105717000617743694091166592360430209859676725860069486092083162245353787489347996458344474036872405942603186910010107030249504890805053796812313931063356431538211577486558808551432480653655410786671149204990680160299130601476673122202346746073152960215724110679148813387815550919294278374132793382003237507202781781016933560748035199284389762236567868983336572644092830076478031437341713748965371275907861617842781207938340308618406806132341761652317375596844412105643666482330760029638578300024864280034704974456560072577302079710967422894034833870079056341042313954950303306609775366758875654233649026454012791177182484068909800375740635567792618409877923903328804607686747508551182788215187315706825259409787659457,1717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171717171738858369,222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222" & _
            "2222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222252273,2222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222224489,2372745398987024026246661730569400071940852598530913706750961313093613019661136660043304214953229588549115824235879381842077106653008440157763482515826755896463281987961979543338530673344287018463219016115004917088496306089189981437869746067778819705086659226608214905773265406521005821190696164966769062789270607392466810411611364927251425724094853199855468930458472451779485739850642137721909433918071274371636467786383202340657583081021199102890278550492075053970663402100153191893555813143629199328494500822016926378226575514315855644658990142857007620141512167568953260848559217323755974661494616621625481469726141488042628605904007828553835113010863602272246388549781675554738720289081288962182158908888074895912630253490848795442738869861959492164311090600752598942985608896520433889214529842303378943565378331077082821046504392936708043242708752032968977683539225351550077540671477173072122185514120758317186048432316935013230715793661245186916334985219768354365429487437645709510479749390883,3000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000066833,32222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222222" & _
            "22222222222222222222222222222222222222222222222222222222222222222222222222222222222222222233333255227,3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333323333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333,3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333335775533,3333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333533753553373,4000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000" & _
            "000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000609469,4444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444446969649,6000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000869899,9444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444444448484498999,999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999" & _
            "9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999499999,"
    $lCache_Array = StringSplit($lCache, ",")
    For $N = 1 To $lCache_Array[0]
        If StringLen($lCache_Array[$N]) >= $pMin And StringLen($lCache_Array[$N] <= $pMax) Then
            _ArrayAdd($lUsable_Primes, $lCache_Array[$N])
            $lUsable_Primes[0] = Ubound($lUsable_Primes)-1
        EndIf
    Next
    Return $lUsable_Primes[Random(1,$lUsable_Primes[0],1)]
EndFunc   ;==>_GetPrimeLocal

 

Edited by BinaryBrother

Share this post


Link to post
Share on other sites
jchd

This function returns 300+ digit primes, by pulling them from http://primes.utm.edu. The site that I'm using gets pretty sporadic with the content, but this is what I came up with.

I couldn't find much assistance for generating primes this large. I'm working on getting a complete mirror of the database, so I can implement a local function that doesn't require internet access. I somewhat like the idea of a cached approach, rather than actually finding a prime this large, as it would be very fast.

I just can't resist replying with a very old (watch the date!), definitely hilarious, answer posted in a newsgroup about the number of large primes in a given range (at the time it was cutting-edge). Please realize that this was talking about 512-bit primes, while you're talking about 300+ digits.To place the explanation in an understandable context, let's say that a publicized composite, RSA-2048(*) (previously part of the RSA challenge) is a 2048-bit number, product of two equally (up to something) large primes, each in the range of 1024-bit, that is, each about 308 digits. So adjust the figures below accordingly!

 

Date: Thu, 20 Jul 1995 13:05:02 -0400
From: bostic@CS.Berkeley.EDU (Keith Bostic)
Subject: Using the advanced storage technology available to the NSA ...
To: /dev/null@python.bostic.com

Forwarded-by: matthew green <Matthew.Green@fulcrum.com.au>

From: hansm@wsinti05.win.tue.nl (Hans Mulder)
   
>> But cracking RSA is easier than running a sieve until you have all primes
>> until those used in RSA.  Besides that, you would not have enough storage
>> for all those primes.

> Good point :) Forgot about that little space problem (oops).  Of course,
> who can really say other than the NSA?

Astronomers should know about it.  RSA is typically performed using 512
bit prime numbers.  There are approximately 3.778e151 such prime numbers.
Using the advanced storage technology available to the NSA, it should be
possible to store a 512 bit number in a single hydrogen atom.  A typical
universe (e.g. ours) contains approximately 1e90 hydrogen atoms.  If the
NSA has hidden 3.778e61 universes in an inconspicious little building in
Maryland, astronomers should notice some deviations in the gravity field
in the area.

-- 
Hope this helps,

HansM

(*) For the record, RSA-2048 = 25195908475657893494027183240048398571429282126204032027777137836043662020707595556264018525880784406918290641249515082189298559149176184502808489120072844992687392807287776735971418347270261896375014971824691165077613379859095700097330459748808428401797429100642458691817195118746121515172654632282216869987549182422433637259085141865462043576798423387184774447920739934236584823824281198163815010674810451660377306056201619676256133844143603833904414952634432190114657544454178424020924616515723350778707749817125772467962926386356373289912154831438167899885040445364023527381951378636564391212010397122822120720357

Seriously, pick any randomized (whatever method you whish) integer in the 300+-digit range, call it n, then ask Wolfram website about NextPrime[n]. You'll get a 300+-digit prime in no time.

Here's a Mathematica v9.01 sample run (I typed 300 digits like mad on the keypad):

In[1]:= n=1654486103240894053403206870530135065304612049816540984530749803013049804150490864068468743049435046830646806468048630468049804304860469848902465048904165401984065044681435135406801685046468048601534086041530468045315487972021596172958763290756783095027617429617290489708016504860165878941336048134841;
Log[10,n] //N
p=NextPrime[n]
Out[2]= 300.219
Out[3]= 1654486103240894053403206870530135065304612049816540984530749803013049804150490864068468743049435046830646806468048630468049804304860469848902465048904165401984065044681435135406801685046468048601534086041530468045315487972021596172958763290756783095027617429617290489708016504860165878941336048134883

Then p is your pet prime, rinse and repeat ad nauseam.

Edited by jchd

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

Share this post


Link to post
Share on other sites
jchd

I'm a proud owner of a Mathematica licence, which is indeed a payware product, but you can still use Wolfram Alpha, for free, from desktop or mobile devices:

https://www.wolframalpha.com/input/?i=NextPrime[1647816546168546816416846816898646813546864135068068406801680468578160460436]


This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

Share this post


Link to post
Share on other sites
BinaryBrother

Someone needs a Math UDF based on Wolfram! lol

However, upon testing, it looks like the input is fairly limited. Wolfram refuses to compute an input of 200 digits or more. [Could be less, I only started with a 200 digit prime.]

I'm thinking about generating all primes between 300-500 digits, "packing" them into an AutoIt variable and working from that. I would say that's not the most effeciant method, but with AutoIt... It just might be. ^.^

Share this post


Link to post
Share on other sites
jchd

First I'm surprise when you say that Wofram Alpha barks at large numbers: to wit https://www.wolframalpha.com/input/?i=NextPrime[10^300]

Now, please carefully reread the newsgroup answer I cited above. Digest it and then realize that you'll going to need a fabulous number of Universes just to store each 512-bit (155-digit) prime in a single hydrogen atom!

A circa 300-digit prime is a circa 995-bit number.

A simple calculation gives:
 

In[1]:= n=10.0^300;
appPi=n/(Log[n]-1)

Out[1]= 1.44975*10^297

In[2]:= n=10.0^500;
appPi=n/(Log[n]-1)

Out[2]= 8.69344066468389*10^496

Given that our whole Universe contain approximately 1E90 hydrogen atoms, you're going to need roughly 1.45 10^207 Universes just to store all 300-digit primes.
Then a little more to store 301-digit primes, then even more to store 302-digit primes, and so on.

The real question is: how many Universes is AutoIt capable to manage?

Do you now realize?

Edited by jchd

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

Share this post


Link to post
Share on other sites
BinaryBrother

On Wolfram, I forgot to use exponents and just threw a 300 digit integer at it! My fault. ^.^

Ahhh, I didn't understand that until now. So, too many 300 digit primes exist to 'cache' them in any possible way...

I am having such a hard time finding a local method to simply generate ~300 digit random primes, within a reasonable amount of time, for the DH key-exchange! Who would have thought that after I was virtually done with the implementation in 2 languages, they would be like, "Oh... by the way... The input primes need to be more than 300 digits. All of the examples using 2 digit primes, in every example in 10 different languages, are irrelevant." lol

Share this post


Link to post
Share on other sites
jchd

Welcome to the wonderful world of crypto-size arithmetic and number theory!

Kid sister secrecy and strong crypto are indeed different worlds, needing different tools and once in strong crypto realm, you lose common sense due to the incredible size of numbers you need to manipulate, even it seems so easy to talk about 500-digit (or more) numbers.

Unfortunately with have at our disposal notations which hide the groundplay we are on: writing 10^50000 is easily understandable (even AutoIt deals with it with BigNum) but actually getting some grasp of what we're talking about is a completely different beast. Say, how many primes betwwen 10^50000 and 10.1^50000 seems a reasonable question at first. At first only, because you just can't give an exact answer to it and the best approximation you come up with is itself something ous brain can't fully realize!

Whatever common sense tells you about small samples often becomes a solid concrete block once in the vicinity of 1024-bit values, or beyond. Things as simple as enumerating integers seem overly simple for values you can count instictively (up to 5 in general), still you can manage more with a computer and typical For loops, but with crypto-size numbers you lose control of the consequences of what intuition had told you over years.

That was the whole point of the funny quote and the reason why it went thru to us today. Not only the number of hydrogen atoms in our own universe is way beyond common sense, but it itsself reveals sooo ridiculously negligible in face of crypto-size quantities and number-theoretic properties.

All of this tells you something: only theory built on solid grounds allows you to assert things about numbers when you let them reach really large values.

  • Like 1

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Similar Content

    • czardas
      By czardas
      Some time ago a question came up in General Help and Support about primes. I've always had a fascination with this apparently chaotic number sequence and thought this is a worthwhile challenge. Without reading up on the subject, I set about trying to figure out how I might approach the problem of testing for primality using AutoIt.
       
      I started by writing a function which eliminated even numbers, and multiples of 3 and 5. Everything seemed fine at this point; but when I tried to scale up my idea, I took an interesting wrong turn. The approach I had adopted involved testing the primes in the range 7 to 31, and then incrementing them by steps of 30. I had calculated that this would produce a set of numbers guaranteed to include all higher primes. Testing for division using this smaller set of numbers would be faster than testing all the odd numbers ending 1, 3, 7 and 9.
      At this stage the only thing that seemed obvious to me was - the more prime multiples I skip, the faster my function would run. Here's what I was thinking at the time: to scale this up I need to eliminate a few more prime multiples from a larger sequence and increment by much larger steps. All the numbers in the larger sequences will be made up exclusively of all the higher primes. BUT NOT WITH MY METHOD! This was a fatal oversight on my part.

      For a while I was distracted away from coding and this bug went undetected. After a slightly embarrassing moment in the Chat forum I discovered that some prime factors were missing from my sequence ==> 3673. My error was very basic - I had made an assumption without any proof.
       
      1 * 3 * 5 * 7 * 9 ** 11 ** 13 ** 15 ** 17 ** 19 ** 21 ** 23 ** 25 ** 27 ** 29 ** 31 Odd numbers 1 2 * 4 5 * 7 8 * 10 11 ** 13 14 ** 16 17 ** 19 20 ** 22 23 ** 25 26 ** 28 29 ** ** Factors of 3 1 2 3 4 * 6 7 8 9 ** 11 12 13 14 ** 16 17 18 19 ** 21 22 23 24 ** 26 27 28 29 ** 31 Factors of 5 1 _________ 7 ______ 11 __ 13 ________ 17 __ 19 ________ 23 ______________ 29 __ 31 Sequence ;
      The sequence created above consists exclusively of prime numbers but the larger sequence generated below contains five extra numbers which are not prime - 121, 143, 169, 187 and 209.;
      1 * 3 * 5 * 7 * 9 ** 11 ** 13 ** 15 ** 17 ** 19 ** 21 ** 23 ** 25 ** 27 ** 29 ** 31 ** 33 ** 35 ** 37 ** 39 ** 41 ** 43 ** 45 ** 47 ** 49 ** 51 ** 53 ** 55 ** 57 ** 59 ** 61 ** 63 ** 65 ** 67 ** 69 ** 71 ** 73 ** 75 ** 77 ** 79 ** 81 ** 83 ** 85 ** 87 ** 89 ** 91 ** 93 ** 95 ** 97 ** 99 *** 101 *** 103 *** 105 *** 107 *** 109 *** 111 *** 113 *** 115 *** 117 *** 119 *** 121 *** 123 *** 125 *** 127 *** 129 *** 131 *** 133 *** 135 *** 137 *** 139 *** 141 *** 143 *** 145 *** 147 *** 149 *** 151 *** 153 *** 155 *** 157 *** 159 *** 161 *** 163 *** 165 *** 167 *** 169 *** 171 *** 173 *** 175 *** 177 *** 179 *** 181 *** 183 *** 185 *** 187 *** 189 *** 191 *** 193 *** 195 *** 197 *** 199 *** 201 *** 203 *** 205 *** 207 *** 209 *** 1 2 * 4 5 * 7 8 * 10 11 ** 13 14 ** 16 17 ** 19 20 ** 22 23 ** 25 26 ** 28 29 ** 31 32 ** 34 35 ** 37 38 ** 40 41 ** 43 44 ** 46 47 ** 49 50 ** 52 53 ** 55 56 ** 58 59 ** 61 62 ** 64 65 ** 67 68 ** 70 71 ** 73 74 ** 76 77 ** 79 80 ** 82 83 ** 85 86 ** 88 89 ** 91 92 ** 94 95 ** 97 98 ** 100 101 *** 103 104 *** 106 107 *** 109 110 *** 112 113 *** 115 116 *** 118 119 *** 121 122 *** 124 125 *** 127 128 *** 130 131 *** 133 134 *** 136 137 *** 139 140 *** 142 143 *** 145 146 *** 148 149 *** 151 152 *** 154 155 *** 157 158 *** 160 161 *** 163 164 *** 166 167 *** 169 170 *** 172 173 *** 175 176 *** 178 179 *** 181 182 *** 184 185 *** 187 188 *** 190 191 *** 193 194 *** 196 197 *** 199 200 *** 202 203 *** 205 206 *** 208 209 *** 1 2 3 4 * 6 7 8 9 ** 11 12 13 14 ** 16 17 18 19 ** 21 22 23 24 ** 26 27 28 29 ** 31 32 33 34 ** 36 37 38 39 ** 41 42 43 44 ** 46 47 48 49 ** 51 52 53 54 ** 56 57 58 59 ** 61 62 63 64 ** 66 67 68 69 ** 71 72 73 74 ** 76 77 78 79 ** 81 82 83 84 ** 86 87 88 89 ** 91 92 93 94 ** 96 97 98 99 *** 101 102 103 104 *** 106 107 108 109 *** 111 112 113 114 *** 116 117 118 119 *** 121 122 123 124 *** 126 127 128 129 *** 131 132 133 134 *** 136 137 138 139 *** 141 142 143 144 *** 146 147 148 149 *** 151 152 153 154 *** 156 157 158 159 *** 161 162 163 164 *** 166 167 168 169 *** 171 172 173 174 *** 176 177 178 179 *** 181 182 183 184 *** 186 187 188 189 *** 191 192 193 194 *** 196 197 198 199 *** 201 202 203 204 *** 206 207 208 209 *** 1 2 3 4 5 6 * 8 9 10 11 12 13 ** 15 16 17 18 19 20 ** 22 23 24 25 26 27 ** 29 30 31 32 33 34 ** 36 37 38 39 40 41 ** 43 44 45 46 47 48 ** 50 51 52 53 54 55 ** 57 58 59 60 61 62 ** 64 65 66 67 68 69 ** 71 72 73 74 75 76 ** 78 79 80 81 82 83 ** 85 86 87 88 89 90 ** 92 93 94 95 96 97 ** 99 100 101 102 103 104 *** 106 107 108 109 110 111 *** 113 114 115 116 117 118 *** 120 121 122 123 124 125 *** 127 128 129 130 131 132 *** 134 135 136 137 138 139 *** 141 142 143 144 145 146 *** 148 149 150 151 152 153 *** 155 156 157 158 159 160 *** 162 163 164 165 166 167 *** 169 170 171 172 173 174 *** 176 177 178 179 180 181 *** 183 184 185 186 187 188 *** 190 191 192 193 194 195 *** 197 198 199 200 201 202 *** 204 205 206 207 208 209 *** 1 __________________ 11 __ 13 ________ 17 __ 19 ________ 23 ______________ 29 __ 31 ______________ 37 ________ 41 __ 43 ________ 47 ______________ 53 ______________ 59 __ 61 ______________ 67 ________ 71 __ 73 ______________ 79 ________ 83 ______________ 89 ____________________ 97 _________ 101 ___ 103 ____________107 ___ 109 ___________ 113 ___________________________ 121 ___________________ 127 ___________ 131 ___________________ 137 ___ 139 ___________ 143 ___________________ 149 ___ 151 ___________________ 157 ___________________ 163 ___________ 167 ___ 169 ___________ 173 ___________________ 179 ___ 181 ___________________ 187 ___________ 191 ___ 193 ___________ 197 ___ 199 ___________________________________ 209 ___ ;
      So there was a big flaw in my reasoning. My earlier assumption that the sequence in my function had to be comprised only of prime numbers was totally wrong. I imagine this may be the cause of amusement to some, but it also goes to show how easy it can be to overlook something fundamental like this. Always check your assumptions are correct and save yourself any future embarrassment!
       
      Currently untested on an infinite series.
      ConsoleWrite(_IsPrime(999999937) & @LF & _IsPrime(999999961) & @LF) Func _IsPrime($iNumber) If Not IsInt($iNumber) Then Return SetError(1, 0, False) ; Only integers are allowed $iNumber = Abs($iNumber) If $iNumber = 2 Or $iNumber = 3 Or $iNumber = 5 Or $iNumber = 7 Then Return True If $iNumber < 2 Or Not (Mod($iNumber, 2) And Mod($iNumber, 3) And Mod($iNumber, 5) And Mod($iNumber, 7)) Then Return False Local $nRoot = Sqrt($iNumber) If IsInt($nRoot) Then Return False $nRoot = Floor($nRoot) Static $aFactors[48] = [11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,121,127,131,137,139,143,149,151,157,163,167,169,173,179,181,187,191,193,197,199,209,211] Local $bPrime = True For $i = 0 To 47 For $j = $aFactors[$i] To $nRoot Step 210 ; = 2 *3 *5 *7 If Mod($iNumber, $j) Then ContinueLoop ; $j is not a factor $bPrime = False ExitLoop 2 Next Next Return $bPrime EndFunc ; _IsPrime
×

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.