An easy tool to generate big prime numbers
Requirment : libgmp (https://gmplib.org/)
To install libgmp on a Debian based system :
sudo apt install libgmp-dev
Just call the following function : mpz_class getPrime(size_t size, bool checksize=false)
Two parameters can be passed :
- size in bits of output prime numbers [integer]
- (optional) size checking before return, not activated by default [boolean]
Build the example :
g++ -Wall -pipe -Ofast main.cpp -o bigprime -lgmpxx -lgmp
128 bits (instantaneous)
== BIG PRIME ==
202647461242278449663528477191329121253
273777903417965956501274703753930964457
175537847388692513920249973584975673279
181001438786494905644613255277216990919
270758340624584477251567049512676804717
178055327331710582128624995834683558609
337920887054586037205083114757231043589
207963660780961922231699304286956442511
254566418744723791436120302884635961991
324329606982817892038867261120013108611
2048 bits (few seconds)
== BIG PRIME ==
20939077772174489977490747359248260987961332300018626077532698713038216442270854911067233487925371507550258064340563785964277556426234021310909172871125825763452075988402386973565133062264469924375680152055365147724192827072625371000628324712340601583161901831791165760676200315199594136197319716837015295467550235722880161553286416381219858248144810984651549201978078859627056918828949748918594792403967360755785925475269344872124816539160990794124328767527942538698293504390753441117352087226045124405219649269676791032383911116622411875664865245761518810734640039946930740704465570210505520479163928570805546579403
31744284057824293509860183784664734532105976593210350750269681808664596851297157950537499436050047891201073664769602901921541859785475811304424221371615637297231197755046600755745678392690432244556148578617349156010143576647539208898319033499329265512808857153734936032990655714666664978869688578343805310229581675025218515527552021928847824863311474218810353081287782233012472513402357165959405834256176768463710684223400564979576228031112631443595771672731252935717089341613431691164805521920864090597328594168866698312360650872009821607142356770707151380220595857948351856406042224031093173658564059352880669330643
22320037778250599195852013544052157210543016465684545141843049311766548941509072181772293838164250403564723220300636070629051437945660516091661105539134991533615386389092595890559341604294350964521598903519794294141960994309600815161987184651074722261247536342583882587914030391438398578217124703508507287654500291833392968009066933312237323993707623254231184722804164902502689647328668677905085220489195265328027069672055079887718512601390370606330477329383152401030656486630386579146808253931881864296940646916815221182662999903540191472745953810915754578336020734787472260505695376430761496032220801436273373098409
20714548655058151694804617179133232401862091523203985067057288651864369001748705216609956686104568869296189459267804992526696552344833179707440654986113151220153711779339359311713441850924331891812828001386837320360321299274336646908983582521817431819930964838092079067986220325155756214539911771772386413275395564738650255272642336672256724179029712697391397893150562275248884466043388882906817054400733807434771864771055584082122613380938730994324369854927285011835832356638403401819282344956648032167053701143903433565611546456556904394650971728868022185715706698155569946705082202944080616962355337254195924703547
27005926287373863541199163087330005764960427062121778458660353266517301761326513647133155150462226182205574713579376634891206886197307970547766407900674909999156878698213491783705417743285345689307788930602818833199947042427712978174823625696274270051111151912659017095151853398865401941586792661741582916841215309516946067439896782578312175808550483987342734447055114527785278846490661471821057477897279425960308255339106933512786203212961109589165628357524791617099329424989963812827207232024372010795296982423181959006099163932477552691727687284470483044803608796763363044608576740237677699845770507702807562776431
20428916627323004186440319031843210861586431000303292857148945359315137623734805481046088162693378664806983059776728938474038197071017941626177351673442923321284094581270672709209999793681193601852814780170330242769192130667446093004243152669391574551724175858290099564765307265583477203298874395100704614044498986772541267699827653072965455736616450479355488728164657745998667544378899064462395329756424328654011422559819292908970056135147068104692588554392821707290832227096077234517761172433777770755076131879332646037318621626807204628202222336431250047064930412212310303451582609354946597206380066091654710507841
16554009563043810996253108125085796870649079672001545012645450902703494238501429478373215500571851235833033177960780966784821236453551923635312084826759656851202250672378202124727699377601254848295226498839202368536841804786978621190743198597941211960862819006505876934952571144002369524880213363286533076545740587875199445408760621314043205678323301877319677248194158582318815924303990356729458305517177146044184991977432759440822375408997493686822685312574998287806776790019118302140985030804594624403267543642724585153200984184685468544375814329417356559643948527027406296217912760186097702048363969391275166358461
28821826864733703596501143702260926539855421183418836548118975474398654219220048140860944553489924579645500165773013869555215972465687651833559121804433891086304262304156219509229855108287242523718904269472648137994685588198788830517400903957460001579130960121912521414270922380078091674295998417364634194973200142002004268536080676834792896527334743068914158342470972327477220855032350571686544172282091241064595137119996512991551177239434429390881184143555687406056385175132723459087159415174560660769395247325762123824742167293581692709164833609166777893252149555207130190580876073058174006910285513769557678247631
16411341284950818162416133081808261097759066866146540892201596433574440175321941754356047428510045040873754613843013595175039515519307013950684465189700035235472060455286788574531969582795596264470527059391258917069050459494318375243824936261744824122986357277853408289775502220384278772271126801319876585826311232091168702398476767343599260643319062678568798170836088629315026073691305830226763407389203384503447317648195421959869537382168741847962495191734071430795162486503312651699220284393869839213559404519693905144176636405784379738866435487796146003635476892003508008269126349013704514249139010983497528304541
29593103568911578197998759299282073665967690883584059699983046201170120320433078673358145525807113421812177632801130346872187259033516498331142554060352328135937699021620811962318378398043738094842529221111479517021345545738550589899638125578171324200558350375204094773702107148646655979793472728684389457623040372281693625814884469301346168996474798258785923390807332339986520587435822657846362486777598621456152249088964642102185265709095197993092854394991872914368019747804808490851260942644972148061743582065223604291421511248117577311669545421786179430918789211212354035410827690619541689953595775444723517671741
65536 bits (after a day)
== BIG PRIME ==
1040683561524438137109027684674751200427051280672175279242388835233236512303651380073674379072345512213098637577267327070563663218431717292082151150536385396172655282795248783964817256178662026447373030392382642166399887267426042817544675105688359307359579712394853563213473572787384792703482834501136085756351331601009031513804650318830646593414086820827326892169646614052261165539213268518328499665054389368629824639899175283206147492531766462336509448013879557874440123320440709012406379957449970340157252354554921743797289883804353043819409173454105460238245924342684026388875373637742494777339007942287102822690759242442824623179818537661400532757045430703414376971183709192775470646624984720054815478155294745872834300832408758204751701564965808827146842369614362744618697193270010901820367368441085231039489123049616692309752273064545509360518986973046735243313854141561102710843144954570637766940090897336199133145081290883252537952216549397460710057692045777860492738394583997026965198074068090656049496625382099662198514066655375833263413517049074759924183732569372804157529058858191500308990117559967285167878161124983070466346214423462126491978953906205365943537583489595440961531051228634812674095046640154989700481056515109931072512261112598994935241109791059231234223372979218296179458847378655929165779974961364545494074369048602569468592030588191503982688762328536924705421493003716174426805441807676658014955608616078735971278542594087343437747599874258727131394105614846430767164536750063483284671195137371422033347674398619389340390843791244514092422625860596942158505043506369036444843471727036305665331801151634563210259971275680289567397834806907579551530314542974061225408097589058513018534964048222980670346672177215521017704244332423644957571028785035303567664437221361034078170805936574255050683324562842840532150502420470534594317009528392059173781842630311816030154033807921125303033912427922415829328445155999089739636253878553423046464164513138926007116405821290536445454760337727268603283908083390619712668553378197837468206192119638362366076329579347365773758910728800685678481112289967503987774584917019006493187577788650969359515595941100380754161871072934817637644519246744970175753955061188859907707887387678352655814157723573054047536324389653039891630925143193993067259921161211541642146577518902926658827839334002547000438711778596817477286217368883586856857339857480827064741905925399704104049401030988179952287232202747364763925004919482129890310420173485015166039049782295572532170247263844722689144132855713896418287628543447710467685274428254559015040024778244234833409026432639379274921337999438027401864195603185746201957301771298904042395404509305814391082353643576298011603604077615089086651455905212122552003745994155913986380923918274098996546821515966693011633993143844206627469629921606730097095893008759080582118701085027715143714019116151582769806121862432733217712820970897049640942286029455955084846019380111385958504994614635090303318872524754878999549729565116763126747568150582778570398216219225542915820859773705155346564857873710237993786518478537414966699253230981460954076853380009864708842485853647337559221321283183936486671414449902357648379288486498935992074518460641230212453960775690660301861933793328510206289339428818934372572600962626326373350137859984249118522024436473758090262222142067328289661032263736751520966733162789524256722621266670613334365392770451998443713362175118933169735277983700708884961513468704150293850717159853849735279168368443855350929847836405303883644576975245858678900903997171877868961090949647251807901015452002375493738691036403210320169243977219325498578049074743570541990203381224819150719162901586648112225519520987681679404578514292873154394400620149376790665315234722612578101243127860346255717072526653216310106157179186447993105089839704337255166769616869941676771829145444817859493803599991376684777684031936142991932410038959873028271949963183563951092039351325824504947563774827777742586535344583566942307512444136515287623073692589064868622102863665494142387689355731683090000670917550151920668795553998273126866742841490776301203688321724751788953379552025162572848097977434455172303384922550035294840136631516601391285326223401285706492507036047117847165728541109337218525867278239673303574616744265013512533053110292457548348766654765829506463680729247506686840004727562536524353435198979166460818746596635344661947109827890636083299429572430969134179881354859437912867933720969254396496119678510921250005764245871950399790166617420654934619327536019663204611724885172575617436559632804501816989158952176706484636904286167691257573271678035112850620121771740454184563610672363848581306012469808940198453771201985102896854479871120232284772411968416261865044709240044699600446630513251536520618363856114633697411351715894056017773559636840932145582443764497173304367622258219882720681883536086992569705809268173592172262582179542402618426004797492154823151790541171912962458005679907680512485182471649843219989787220281501155215580377228453996644429605394161163450055826184422241943426050408233912251590412300229624923325462104451308336038868781165082138572373299107413330652103393042661401001922166458246330204837090649491036606108020116972359492123026703643411486308103776152131942446233726866731998552911317409954755858532434740621584036444917922009020464792708883521467537882287238101269721070450907976719006639027234004181532333576471110677281590861182400652235318359238894807156277360176215266618452442749662118951331213575196829959279707473327330697907941447417716629647899697357011971157296084342240875814978966162265913209645385323951791934490646662002489990001885672137115135827081215548013080902939347792030271370039601536320514996393761667064426146590050985381049447965103600096111184348378798010749671374070132543640558437546886540805140909915062134632107454382628541252448573021514256366030806047688691160614786887710272258045660381209229475157006067780228009183033801228808520347152144721097234952389106135301340593610998883578052230601061971762662984385690689123268785909355958841512769541078579499871846004759531746150044027864231323205484827842072976902003617794226555739665944846356237274098539862528294399681374002514324812969028703063290462984924398163821754224929662524714305094426811582247964790202165140776629117484568418159112313370322202759583327082676099073943474431847307303791092320750254762748981144376605510816487994202193533657469584965147576375790990579012231390390019460445281926996784596200867997177808589193896640930640893598713662467285045040225418814945647557531202340765424232830118218522379804709541734806840737254538371671543274667564623724841563935280411285045102876576308885961268315519607941282433471912250423657981640143405856642587359323823686589004801335995684012576844671302426536792933177103090075362761639015063125981281867568613674525127558698481203942598283621084696033918639733798061248104930960045524744106541415118684698672916964870915448773516399696928716409160153859717814967902570895522470908094087359951342735638623815270559028721912441520619733814617765073303909524526802381206943152981162778426740494504465331525829440135440810302514157967152556968385436047133257161726535458116266261501105436269224705159220287548710018655537145621952624340717887853922079538581028858168829914118340902984213213100342273735314737971389368272404251824330582237680079491758668396450026588474255450223161012429627431594770301589063829135268966330371881708624828322554470423701257973470367272786664257468464020015457172758971756761476980866578962112364371718449161682722323813356328892835280997640329759846100829356115669132786490211284111817828419024835616563172079963225070046443751566778370382695564960559903373878226930688696979094990913759317750355542403354690590466659427083486785989233758447131219380256049039860633156541159817282523289665400912237927689523996363919561778394543578488119677559519449011441470330192263866078175482976742843949831364835566186092173616503686349659911530419560661031925032271373435468299730491914723141635195195957144512223523429390314338613544772235250790653784497137444093654482805149832433006165177562452502781016806539020614524064595940823608610568455991862311644361867306176006615287181957839727265174048379195119597735996468229069114503481024623925841360994870477030285905710741284597917519239933494245629473780828067940815752477483985143593313207014518232232799648268909958638231092411622664574243499922889956154898579852520414763728397190449770652510253655822106328313824059398173674459419405939959170118367855793907890916561531564312768894336157547659984860947277495897947899569294804671689884757337638942767032824449055774484754023843011666918758373864559521450067035046809143234793463428013596386691277165219509316328972532859745082926732900624741777304445890832322021894111492814109634228194455982809573878359939935488776110115150128912166778853947608030901992408468061888731438343544580853823999029425796134589839893065518860604776458408323168673592163917647258190325157535407420421071072426572463511050961963203817462586896321640080334677971427443999253204738389304354679186419479941751508348685155034991021869490307728119070472791591953137116287979154671086502469741632920030090707560458087871245054482313807389356059894148941982624555579206714733938480677527502058316932327618850450052094543970866334653871311026497006069860367249321250010535420520934497505927904012653834519419476600900262000690689203446057070864705447667163889219109228971757882412519640086731370710332696680421540515822620722072301470017727001299378222413754127866630662631108763879135369876853625362748053023345753447752252691461859851501206568332762692527408783586542324306363557697291121863086858293488844726955974011242206416834213279928493552832046795750025216313478533774309396611194053380416548802631636241043014992172934300054858771757649915525675775109238989303178506788051289714121865242646186736602373460699091213890942065415269678154657751523586445328094698618504823436727764877903865112632917528621710994930751106264084626139604220713951514753665895899477091114586641277494473555380019723363030205400309967807477540316361685365589364618004904439871100539967503638335979402094158681335255376935983572454048010498879515132854326792579924280350389035769689091926601085510836258361058608416071600293231162406471091338022649531624170578070060392954870783674807785000220096606280207038910852971624831704888521325715778838543290853430233053202836736650926979049678499523823496499543295686993411024703170712036191784867489467162758984422258976214107052283353268649413237073378919213818952482346827932013645369423348568724829742991883187164630900120171078464542042005127311116557969042873872785164334687211170877826841464674815691875734448723802338501828425511423149898152673553506587130089558982645267217203383467142814120467917441695659306326480426813036987389690468953009618715022656672565934241893877850321610916065546251104254392107570231358712862205789960434135380545056753043009848589742287978443947487545878757633420736857291658716451931881635046226071544060599257684912094548926869712825766341118498225051972120162990796177276144643568319144192062927363585899262778315919211866202878009729050421270004881209296149610522834306153320965237309206228325397544104890655326348887464869724241226301354140344106682020567626349344647976644074304261467508505857497210435922103560762131706016807207454196193588248532764734926357876093116256369651991332114811324799379046510439712629417757418015017366039854702074626109888367534605543673145691796876102467032594638969374697382428339403410443283477796114832617466809906944828987828498180540499738849519004630263520921150003728142399728584714597971812169382386517516317779965080091552483029759048030420708580116164288155702832086962269541196013537490375384434000306279151262746932648952904255988650051743897948823685085142864412881969022097913760486615523729765133364937986362907067743160781943730288490773282451291790235262940990973678137872099651530317631804227951072047292853265548463858685493228038773566563390223036867082763923153613881049320019021304818080261140020827407951873002540995620972162530237231932003874996097174228116770874817499467127818229899838621494029692606413533652153015244408352591141298089247740792646546223666799315768284776120052627352180936927776730380827941015581362109187640742700208990583376514036069315049416670288156047336451533019040912997169691831573932134975055548087911296432639497124153056859913306195327061582442223917122034630557403724022983043534482361198343185525414614730543050510886257425559943148928068785918169689006525859800584865158080205361122654113036233698510773379010408044317944309248264738724483122570480513764405056955031065057507304342078827659025374108158233583523968273644827487961630122766652464755758393849331660897376016197006740469481786589089078626403635551561712164073108875982361365873389324860885826455995603693278448320480765246570599179848165347873560231683886107985601047147824727169107164427407172328847483596410496167715367375849710894057400040514488061723811814403539201492332102720987027805595041939406409753329021279553203215692604253416265922458098353529155945888849874771999733947128463004324321837172668813540278056003398238768387927015033645087062957853572624062933293547943490225134820168469634613760310614404428984437454333684130294453366246104730107581997173754779663235801847700418068955383787159839728649755643873804222073021124849928315815335427496792606949100616424932767788391475069852239220858708852214582620659933329388934309542271419619454847278724237649156749836235253605237776879324117905346899008386205239334507103484328442192421325802263203658300160000801643602678596068762441401569121739107157052558583768448419404790519418712539743591069416491592819888815484866602448154881716577915782081173686730525268187427518577590078344140659796955321133367650650734230505260844531478087567186804296152998194711887184338281169244813466526326525164562990369760804166157575119683508669618151877666398030392334549614841137512373332617123237923724576199949153276274041274597283455131443195315520051563740899875123025206522799090797746213561469834714400153768773730288208793007832116400464839197616113450564414479276232009201524856736683897096260660347170295506317600997282138070584530178827325715816780263503102158790689217301878771013793855131880270421586979448554234440449096100806691724309470740547939311847202110552825492365111940763515517164820648241100682628034062437793369606257225705916068952732641147529248479078601281059107696415280798512502738720149818166158590708440670946516294206826051677876946020001279880837420497830383800199714208782618589989685963430255761160365875914509809926864286426858524095549874373050930287208982731187643241854388479789295885439827222840517460699799551767042797879004000153307429854445177038611745503005262128713600352030733909078833821755224323085432227203815418314942983048673672877537103548424866394609713626552553726823457254353086977689496132385999864353542285844782823162775338054081134311166174552760893844424537094695317272610792544715091835954221860138620563358214388036705456681478040600818150642572352170372637950280439362619148835833161612742786786996247244117252197692572496786605234633038079211674987379106965389854854996948191632007652411586871842926442692261484075454783010074629542793834508556044932314506902866640348531384744914053709894123796401273422966656988064857417733382578437466460638227385436992101320618627528431036157561839944675934226394221877023433186892962570573297280821386553498991515362093255504340595814364408939377814228544707187499854658149929286994269144152528194528422637687736953145733070446208859585243039177485795086741657336944304845906929534210862974373041960726198910091145404541053925044658372876255809559713074280310386415768493034402069413490361104811313659955148630867413895679364736917970209507704954914847108827887775159601510131233085591078589231004776135325910460062018514068583631520046251757575791488426104517981531298104020153098941921592737701677583202221681604872357965200828813859464445660756500004396214751012837565975206340071722120533362351814896254137579750860514402776727925605352986348088617337574841528466777039981833288351699210758184723781458238931695263346195848721810660592890589341088118138461307023938510789431874332405817444161990526589626902225000736187117224527250474407215905713106587372777186318319165734667594272171620488328661582936290900093556599946476732843659043880501206573409113361091557924155512795910989790320096202846731398733089246474857060366715326024808910003787219772815504734656173921922934130103476828969765530057051666782481288788799401526771212166939135395255042666694471078658292854258869017023404668717181653877519726405740034515935015880995609376640372767144634765295746294591521652980981043978654660530598724125531160590041609213599711440105399880440762493750108105409542963618707530887784343602350445632108495339407179724714324564903717793889794601588363377972561487023196320586520125625008019852423116612188721867134441297211435427211295710051700881506958859528927221345888603730050216938877703312085948497671284832627444506295618562339715786429451901720297124255820071902855937669359515897797804064879291451500047872064718613344236076085888629367580224558305053278415605220973440704514205093891729726013663794862345797267960341207699027357076453283242532884848541580126825153725565338332936569813269724379650980707753951485261735543880320282148306356067079772375568422685106758969032283414571812763167166258452630050843160915846255733832232779691870239286525880625280975105605260420965334281341435511263077568796564655558214335140276495670009929953857831121874723933572600496409956031222796657103934746850952024504697475151620847049422374564529670642974057042097544947036113129604846275811393318970818755475054766591917001888041428905728975628440330184539068407223092432295954143568621919554882056022230154659844171590950463238842686128933396713089873833236495837106339875540485035778064421770598157200176959955185064412337248107852267264299643092242200433934555195854032937173382937124685560390741749361525710557452170638636723026624526344863025950772896429043609130034586168124416604569341692096649097736450434910137053451597127281975124361122256299916613262252821898609923850823394939248685912831017895080605671630677273406509964097590358470451657808711192030164375355978075253898613237647306680369290872439059747241847927577617915324365546727484370234495151925474487453573365969014614226771279771743528862340115947819529381680322172490533351537063379484211979277093049061455963734609205062763407026263097563211146949673683338742325442356428409286594080025748814571922749351832332449966013540791621034589431604387455087360079768711067472902410244992810211523718667594794457583509453614686840747872330736583401482791932669542662070080908671648952708392568444997303323927558641578461508007840619119084738444742761469355193702753348453808230647867639216471952768114381885127033769053873215872420728759778505068531481645210347946279487133436840581824230500007718564236046901268748473430912725458212693285695279537305681165755121962112380072233909398944880875384442535863281747897237876942375728099405866870872306430250394913088920512841661940276667206599261164158387309481693588263589313195275797090628417843734427063869577766023966327229879033076526644838642585245439072363315616291941825994964432487693066923561161667852635620647182883697332870335586798918169040618797971943838109004748936461718558876451767618397207798057997025617994686427046815838410794688834728339397593297
1065733546761361965615543936014278632601305373094543912140903957734130170150777968217662389467705026824175532069286089731197738886326116828805754745000279085309758781614221452670617781259465123335137482609522342814052401815217187714557117625984743776025826352659313478533145181938372023916861476015180625750050906647998190871004247270912080227054916936013732877595190369733929476732815334904093304774953941558465744375326486458559006537893963488035341854384484168718981094846102999309561102491956581021930279102819148751429677701987731964204016787995999540179144890163874629546547403762168885519998921048591544472024790966307692349285984165278865303056789767654612615797584639399776658264459072030702616510340605469618533833618206246107592489935003936802597523653731404513246158171739852577967544150629858025734251368479566700023127451744141979947995993614760693983830408474895403284992162040092800208890558849472109128746284791045505576060100134986209781487441439746988784127112947053018801317967845019617595113988832113151303033837690891902963963230326367191074197662146214967424647406409786462132450754520667250033929180056316393940701688867250128819649347669160018001253312697859919836836534179028393277511349288213040725936657201388988952508928726169788457984432825704735421288000531269220764906937507031949719012749439845878311446893540232384613344479806994764343938797492765572458448714091867307228320803233955156206517681036336583608533928736928047497041133254578816509016907324528274835934315166433295004982208978773963135396260797242685084241213185364550445624426757449336973707766471901853200162899484190425995986008352457507126145141139238776112880908629955566172901070603714104378211537653895696117870224487871162234791350691471239090794761110548864917039653828043529652668866374763970457347015361978117808737594369219466674915560332967576801710295435182051464712708685823103607404074895081201942365582757345921355819627204080260034497860202680594884055659105285423984244583131374706912426695208211820207512818530534790900261087384631844267976234977235440067543005819488856237170655552185761952949633719921282390036441358162627837932882445693999188259542521425665430513576815517931507641512948677905980161362867250442697471938416550663689567515522228861319771397756210340081306449875575030634584157823482203480263582108469610181045698327398036836582797584554178493299773929081486316749052653173130488129291821985698232289480738431758745398546344770321498206705253033744944674705180340063675443773332658315345805526352653819082963401114103521171787188082822291103733756059036822222145873346364099261423983635706943742649942620807459082197424037063448637881973064887626347124413113942254444307873529955788458245721807591954867312027388994138984460543944534857246681766873386987259356790847785936364964788272104087236973845286307605464029162590246289587988850890917328486325307178358624043867922717702615861577592865976943750908317483858789681030023483945394193252777641412777986006966446098914334329877365718502362101716058537808600553714452335234000977232707736804015584038154552716523409157062337511627422003781984236992048274867936638553057044861609196379476947607917930394280184800934069877516568949638914425960689351872931025387425550495430924246857978559740442716845815578406711592770847115121193771494139597737847151728620013730978034957957698956990281317277898880257376083735345707246349571481611893038316777161375577018732779656921683179266883819203081795290117178804535416726835464286719464132929972402880466231805791397807217431208503319159284645826321503450349280823185840879293813534953213098122709684818582758176838719459280995518724121225846495001582931528003984888209629685795328820117791670320335706820093946674750789373099981882886993133001194831714872435183774129576803612743134751456252297043229691593726155082918819361466842688550470808165145998217363882981213260550470788671583681811577349363675171637019643059924144102395229343630463244078709324520370947551958176685966795447184041160791246772148131153747654012320734768278947813103817286348372765932096292170554009360146963201648115721971592759923412329073926726072839333720735000728725195957589588683607023982011933317673344932650818162695482714898375291521416938381256564038112213561266100695790412877211606067461547679903012609331258599789983184306428848689867900579650241895566580486397949723421477600502404224488740191426789772405950681751294111622639024704909217442930960687080143457853732496625788008392865423722852605849119751298791834047442775745727196423149387814596200018502240394116497272575453801922887598594438869555755339969075459713013356549326270148260451324607838559146355276594704153549906860805573540107253941849945143518176069441414182336124425048689136857525685798386925947405647505488404794358195109317845870495057753458247532937277214177656985099698718305508945622698323732439056115331251869757346532900455100920192630010282997993956137098760239528637061905988069377763642365500315994624776478943118362682918374430307748642245176141722948543955059743505041283277609904790071210038253573115214285992369939388759030290574328312749608923093513117187564275066347326273961238937657292865670166690825528811836452683447070083447448522497210897925932764466506947681767397529258978981052830365313548492947856236759075525424942139828105104523332407202469836754404218611557650453135009055256456254640963031879535335569843382953518851796762695259980882118513431954129649065714663935735430711663970979968050313084405675146629773735620011643017654917242884603907231509830795700680553760462106844630328092301264515711182222426528799038295292198459900778182321400593392955912042691170294281677275703166732251477683804142504269830668537614561515682837698622965947016590981277812086781305298448819010902352975210762473739774773158401515688229925247052169813446921065435627641121078519147798024630244167021312660398776534701694088518738115421437515669160188918273936945238056746167743721210759484878376012807508690913632633370903995175492884876424904087565009789260424265919975087319081983499718710991577239695300507245287468781582453510875659195940150734434979732599491231347341870058898222509258725704180685763319796683696386206618426332349925132349159919988588400783751971493588737168545533810117705189255578786807046076393619398910931209109898251544551155032585836637234444621405518213082245713388652900284363705707018776093086515944689204544963805068219319052596748185879730180774943607134158091874419815747128694554428141429233586129674591919010518667172751896100098438259368704232178341498806213255156657898706830775852573321059874436283416962081144730484272900646011854996548755066655947672301481019742551962277099193411991153011562495815959321569958422699949056415397538536922335788739148892129939324442245377835623004284049954144998224727142141812744653036303955805665851082582921546995187560707008917366412517869483545669894960033817427044505813636597847807739767482979608286758798828232885247315011367022973949831438963471315409251623870214371021047255368777981680764741433691802971477445262757287527377103573375797773450838583831344305125377850688424767831148655713769362725775880492220650339608953937799135394009269118946470114511854631584668449533189129587216058793389259014649647446604525448102349962609261031781395157517431218204778846626215472248159010003684529634244179030427012738548513002027507131524283291558997743024777199392395932584664539689750636232313323648264935755806245435899055071259797973365950894677249382288417529446943507922413418725366980914833310915834574565530339471875774399823830140036550692013344213029603059685556679182139146837546938267586213209697154816670934264619991425889097984564296789026151972484293208376105942236830304314092745810570782723861659628783006551339291744652789317462608269573176381278435496672199212346576138002416526846855837381629776602566346338270586786677316927841696034687237106160754401682984266974479077276347190332393091686431161242239781023703128860109448670217472022641515426755226706902768366875137507732987523483793579795381657484083845270697416903518292309319589254456727332122150394966777206376176092266525246941882272900616738129857351587687127793622655070704620600069968961823753457222339968421656535608960837725723023412233455758479966473787040562904841945632884994876848684800186044158459255413137441920127904044685203600113336044400251276596607967479555603483680038820991524668837791252998887298721916832490334035996600636016636086891329079515293403661285764802004123582197135768481273289455451347098619026720977341788249224472948173748366097330255704174229306870907994625871666474742392391605187894911134426363680328574519136150340610336644134054230135716971399843017190100025928641903828347495100346874077542791958051857327643398843972471158114151017196409522903762712240751436492299596519392425933447614659053494338395001271294145247355181491170187135753912481305908493094330280718267325066680005546865077463609562509663300941112147254468292517915520671784135249431267333267172985621315899557919830540545272623755823375262089332932758676178539193232849836830134522292712556193792781065369212027824013315283250921265066720238643882654559029455146218109720506094253124907557692514580258462359343669544128208196164600669131041808999085935055126314986982764821909879988588104440117939301667630900374245928850092689981254361980268269034254492960180559456738695137554994752338298903393539910838550691381161881460883164013709394525973839543735939251411796578620636468360056531649104542510388189935786383426669550938700008150823130318378846360099745424746057186210519241602200071864579631450420947953300818591110280973235404195210912539696948591201532114323207617876043610433089420344524331450287905848345191342900220962749042011568981017668379165358885081912132229600280171719562522288556766372313520028142372752547986623206269407226227887003479268912550684221789047296105698307374742040532489651790996379052004349322672351484925984058371077507012403302311317324487321052250689353460177856798414663551305411034003971025092768598971212394096640495072980552420161177205719740334035936455570591088098010280224063229661202885546349726238133692583208007944779940355293750978641267272387149260265156830920060493250798439814396249830252349247230544552387972293998266817546026756465909043086787442323317564841479554929112305961712750058712625865431643906724613087109030842250909836195759694402239392670982908269386133981357135935747653212509141542632983305287302096227544712516054684186902780403188706884605298445466583024202868917222161508814215380597217404938242805029759240029541604306033944397249247791618564601974123835376521503614460176718916498190836472599078656860575746707653342441950128235759014172536404863695844016540332711440488182355183295575111704489392927853457269489647665886372715054001589523319241966052489880297909415036531739836973304520534744132362092331626211051619641552550851997408503814088177606989352216021886607697441073409001688372748523605880259543823600727712650420737311889624535825755800893630492137496114748445339751549332772761251343944492001855110568402091646476405847565805660866284439679045575027215695977179826563101838448137091663647845717178810710164245659606181779654052847232676296394283051017855127938722687370888465110150639236394351258261800315407475808072043495148452654107106503635790955134330740378743674062324796815302516273029190937744232438422729463037261250809485284324004415929897571089419399691994928821795464777441276465141782002865301423834429906952478587256053901842401352709334666380813809792232699299633727072709105781832726746743429528942424343873554367527842551467808312210898785010123847046024449690820693912199085953873335326507460668368661226489795668765460220613406833625191664156257297117292729169959583620555495015702030436639497580684275387397100487000186746666330183278809606779514082356906033328252718970506248738557564806242382806965302444237310520437788388587361239058221569157720530679615968869218282589746818326399593267152978370845509579402083944037286677968381072901819930614274073568071469694985411676293918767610083171830084277172165229979538364265127187690616887869305558327679993825511968904560272032103058640781609447226063574916428019307296000778251428121945322550334547451607931020933325643751712125210837339852633908577326653556524070854148726378373151587639644732750329768632369833307889792839679051786644637101925492765251711003654152485231270377512922437609265341616114644364287794670788279113985356906073921285287130666912674718856841449980079381328954272911132653568904127875310227675747492689927126247654954277065788131110984622995937091265216511361606984989372466728672900329808210408730763687743569385224668572880412091183464627574809863018348309103387009066210341998947892672106526049197488682234046004800508252359594924555157177786523456402113595582085174738321760246179815070102387144792652177702084838811511267847596280835138942820796944846223051645284398095186437991104822364064305681753163160866155753815478580445857220454408733266995118294322993216516877930839766733517015179868086254543707589111181237791990563427781205107880738091890919540658099921820059748800466195020040786977395830154506652370542812603462055757555404105791899755566230622830883628134436856610736533264192829509386313813827220410026060212975446180025552176043132696655332509009166653816609495807516969479682005564159314005821990400270979955177944062460017797901251603657432378626097766640322922087244623271512941878253548290736095891716321591298190783947083745089726253032639076181112167660251963967993975606153688646527151742466358107548063696062119963504354935393191186389681196799440164833526055097740084415743923041987894828914882297643617834833640093143696755029289970150929656112780123462034804865450943651263513659248153513450235729620193901988373016041999830681873043864016545098439477072390992874416976119340835302303148535340728122129723426951642462291188486260607873425655903991804066661406200417378196542848632766067662249804619225846285739859291705876727574188818141742073813336847404452976278859199387782478632960884958565875013879632779547438503350293474675230077614874194809363288386067517445940232134480059977174619423129308536838729713697481255538108609100754666550816096954868943339091872376909587016289755937222447377415393011570893353309605961225990216649569064869775297138915224685886110909354774165742402660603946829608446852710751942183062057474277695787994232922912262214820984902641249146072321241945950491189138361553619566330517826620509147278615008533497205814385652714003756478886558367948636447167445691691712556979238938060320436806471297322638728187747030087086831961219070007982393429144463645802276811428670914436670131559183944173556763638066416732367028103987973454752285810192575963357629008859681432632793178009406908704566235110683060703329996318444453343354784885027380789284034626484864590528165783229722028378545692248889617124349892936812338136229162827008922692076496793572806050845772880811848588866380000232261516249222894679327021297035924287480119864858139934531233491303756291516422768165978053393467275314675484628000530769028658998933881864727936724086931921856826997252046458749940014852962342823623058385226741514292546402607278700325499644603107524010402351693670127124137674925932207504247706594127734819249327141076236197030898738588658330511942679994926587724527867914119971829710552170131181646589923548894315083635167260592056002825773820479134309479682174851626658317460174481736905280319150003114422207161717602167376770857968418304887123413783905047815318626526940065569841944367716477623690771082308544302791779345914890889737191402093106985833591853123900138489390946751232451693844887842240296673130135788261007473100230570263024036525616003288267492201579449893992228811638876565052651218959329856521923504737433477775215304202908473125437163694746498594902619810608401677584117961076219207954284986979807232655828599673457884641840152357814267030826645597179970425098834741460159508032392440272278424655899194363881977204237340424356687851857079210279982491515248362256077761638823913792781081383181153579244614112690589900139024822771560819167603126173079777251310412713936071826027603913261794723825299806924619596286497063451937869582990253897451202657231314403491431848435569974372090155731932924696676846684606878081928659468016338974265745160741393134934641832012139190703071384081747887915096994462607155810947127898797434277313399817825344458818512422246902001172627189705992409709485621092437147663474917805165652754046444805383949651934145670107903636144890212580678159071408565969607809855351243963222410018708893084977709898093951589021064207914630249408534598331997606475864883723836269860069931769174493221424513211615985921053371301163744188090700946396351724139876196968950191853163057560302462155574344046770816211376039299531081220351756104282631632418464748669150389159488870666489959375750816431894447077569952421950247361851938326998046115991219432806838518537821931034544316392672339279265457851663472107526948759714592798271754457800884296360050887576270632259576740100550641653609289295564001567045483193888038735100234450292831789007382783703070339551661033655862148929943785219365753843886400682039437190002189532019211590492509860133931597314360938985332086096347969435705173872729474182863372083923291271879948050661047351333521591367600405576492401702942006272698271418807555273095646022880272273540807913347584368316726147902369470662930492771100130931498473844856992120884774180123540578240755728683798915693306515845790362496153144896215835658326694191103210224674345350380781778222786636134083550087364771002754870017569637793693906791036343861664323881640033122961309962471154853288767076595181598288883833339424400647945883325791334569982097293258599800802745247011472878746856666883268870623166082566169660725674591345196952868368269320822914342525939027671594470683957163640176353039469756301289745784132553885671553159668371367338863719860789951164317066037076379139203264102823573018888712606212212960096341438645322260374282967428538106276732844522025166118652333667559305014016000387802732955885410562603952275272832044202195327039720861903178286284941192886567065528691398878651826852858340355879178140333107408144976050478067021824193249289691365759561017955301991983611513908657934638384224485340381993989692809467691997901240668603155780750449975199294905318430225265747756637054075180279035625039767819592965012826859078103406435706800510116823897786399872681070651267549539776582298671239828657086168727711982290090230562408294544590083775342250232015940593176009792355786754328095345087377365762288226643725315785230594929486808669395725403224179182345300472654577283484882093190427314420364321154143410994608677337466766107790505228514002303627944080776733162048126747852685859161123720284001593931879482999481045925950206543310150474171794864625612496980560102884339668536587565581459489648425073196674301324241584968955166473030826367162384453805569187121487531553743951538465424928675747177347159054096613177672648097446554711597795902177246601092838392660466155402337574443606330692057305508508043244171311592800924414143388699950779543347954688161993066969100658842154299437616913137183411126582781883825071461508113733162736251763728851353639088771946294296670841356009808051796637198372815567783529468424246138340305221287426747880012049464164984450605711502673514697071282966047731609978606776335814494105521416214927279857301992051734400350269738561292240081728193819960395905493181461222196337346624384119912475857831283701533317160409660183022201469449039281061185628943