[](ctf=internetwasche-ctf-2016)
[](type=reverse)
[](tags=prime,fraction,fractran,math)
[](tools=hopper,gdb)
[](techniques=)

# Alewife reverse-5

We are given

```bash
$ file 05223a3cae8b71d81592d5977fb1c3622bcbf793
05223a3cae8b71d81592d5977fb1c3622bcbf793: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 2.6.32, BuildID[sha1]=a4d814d0167c1c0732e8fdf0e25c368c61d6b27d, not stripped
```

I throw it at hopper. Since it is not stripped it gets easily decompiled with all its variable names to [this](05223a3cae8b71d81592d5977fb1c3622bcbf793.c).

```c
int primes[0xAB] = {2, 3, 5, 7, 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, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019}; // Primes < 1024 prolly, sorry just till 1019 len(primes)=0xAB
char *program[846] =
{
"1009", "1994", "1009", "437683", "1009", "2991", "1009", "441671", "1009", "4985", "1009", "447653", "1009", "6979", "1009", "455629", "1009", "10967", "1009", "459617", "1009", "12961", "1009", "461611", "1009", "16949", "1009", "465599", "1009", "18943", "1009", "477563", "1009", "22931", "1009", "485539", "1009", "28913", "1009", "489527", "1009", "30907", "1009", "497503", "1009", "36889", "1009", "501491", "1009", "40877", "1009", "507473", "1009", "42871", "1009", "519437", "1009", "46859", "1009", "521431", "1009", "52841", "1009", "539377", "1009", "58823", "1009", "545359", "1009", "60817", "1009", "555329", "1009", "66799", "1009", "561311", "1009", "70787", "1009", "567293", "1009", "72781", "1009", "569287", "1009", "78763", "1009", "575269", "1009", "82751", "1009", "585239", "1009", "88733", "1009", "591221", "1009", "96709", "1009", "597203", "1009", "100697", "1009", "599197", "1009", "102691", "1009", "605179", "1009", "106679", "1009", "611161", "1009", "108673", "1009", "615149", "1009", "112661", "1009", "617143", "1009", "126619", "1009", "629107", "1009", "130607", "1009", "639077", "1009", "136589", "1009", "641071", "1009", "138583", "1009", "645059", "1009", "148553", "1009", "651041", "1009", "150547", "1009", "657023", "1009", "156529", "1009", "659017", "1009", "162511", "1009", "670981", "1009", "166499", "1009", "674969", "1009", "172481", "1009", "680951", "1009", "178463", "1009", "688927", "1009", "180457", "1009", "698897", "1009", "190427", "1009", "706873", "1009", "192421", "1009", "716843", "1009", "196409", "1009", "724819", "1009", "198403", "1009", "730801", "1009", "210367", "1009", "736783", "1009", "222331", "1009", "740771", "1009", "226319", "1009", "748747", "1009", "228313", "1009", "754729", "1009", "232301", "1009", "758717", "1009", "238283", "1009", "766693", "1009", "240277", "1009", "770681", "1009", "250247", "1009", "784639", "1009", "256229", "1009", "794609", "1009", "262211", "1009", "806573", "1009", "268193", "1009", "808567", "1009", "270187", "1009", "818537", "1009", "276169", "1009", "820531", "1009", "280157", "1009", "824519", "1009", "282151", "1009", "826513", "1009", "292121", "1009", "836483", "1009", "306079", "1009", "850441", "1009", "310067", "1009", "854429", "1009", "312061", "1009", "856423", "1009", "316049", "1009", "860411", "1009", "330007", "1009", "874369", "1009", "335989", "1009", "878357", "1009", "345959", "1009", "880351", "1009", "347953", "1009", "884339", "1009", "351941", "1009", "904279", "1009", "357923", "1009", "908267", "1009", "365899", "1009", "916243", "1009", "371881", "1009", "926213", "1009", "377863", "1009", "934189", "1009", "381851", "1009", "938177", "1009", "387833", "1009", "944159", "1009", "395809", "1009", "950141", "1009", "399797", "1009", "964099", "1009", "407773", "1009", "968087", "1009", "417743", "1009", "974069", "1009", "419737", "1009", "980051", "1009", "429707", "1009", "988027", "1009", "431701", "997", "1009", "628342186020279030208477196652234251466546172127229920271442149116418270266805114129323801879492482137898525457610034761318243685701612999753301446499402184019047334363868952491996606714667813682795710496729144356627735845123676166105603998123636223487640503561426022924983170637012661801780667366986496506030776535567526896671098662632123365168743664803047333533266651378724651134747558720373671125128918192606546275484822315302537833017347515852873969123863196991591128905797797953641849823901200591253758989661116185809449387114754110693862270878790685521494032855174559448217678703819332109924602615048084195117590112536399286371826740412069584415578436175604905487388386875110557418165843986191168930994241095051887359640391104091658653518621901534663248053930033780121015835031607604047633957687509170016778799461147891167654749638057549827992932889122995155539900942798016011513799665913318026811781018347609393399492693089473128154346668249800406988857586278307546023464942900979079319193897231953014331315745983540688409217523781284767071786748835334904114251151768066947066974655638700742353772603987770915012114230380632982060506677995390598274839813186589487880327769882355406369328704667144104785532210079866539787033200765829359931127219031553817186725838729517291842565585345287913859037622248318083084610913049915914358110409209100852502593148685289707303219729372851454213282755549475037954209582986949880668930047153621586488494270546617243702586105425080170041634818438278320529852112847863734593944644022898353545446882029646417103689943919192691294079623058308937404741503543204905870498980563398747865075941095954326295793595346961572874520213826034401809759600671385592618044358788220764179037648551723688883462655964529249402109637617708231973919514209153002131026182417912198411370401495384651131774509722038523496382808921942374492604612687129063485332311030348703446367201242825533393540915424705051574412572120162877997562692412185247999611773833311632900771473429755915441182540269617877214830627528032509574263455045777758312790203647404347503161728097958892560903112974915627570659454527665768438056409725068410760146580760573561825743041360562327507023011036093343294488329397226160195885463366678787014633928020875226483619664858890687676379225725094561398719056931046049652997474332655225198880371911150572119222293804816869964938939569929273415161422698066449231388944785154171990521448471715053090799940542872248125377623217571815993265916187470537162268436325773823823025764997980088398890569841898462161853267169228882950197460075182837289919940982931539635781819167833327053366074466169096663110752528063831392419664656628996209161385538062512860770349218644155662924022242464260618852724359227862586009757511987837154780681347585339557128064674324666633148721900366457274096873746373036267539915146015258255209166409983804123119669569892997296082665906047894529706757974988307364081640652759420620606279591460036311764255114156837496511088449627305129870293650489346534475746640218520980739890581556540008279019229663760636485837245208764597357678419738833265275277731038701789683747837440024384633103957164283508891650623445519394459252271959449686279179444136374415706603701561041515600084286014592770962766546924881353153028839585503598573550964862568899783340905087121767189848319028823764126564635152182745746588976064614585513882178320384662630419491983556919743035918979272357120571425297548004511661675273618557126654548778343459193970691487722304790664607581194061709590959173879314951330697843870052828316024354166567082187518547658698577696795531130565515421083180252264454883596870044949725930149179966847413679961101162747165984569728196830920577134702664306366364197595517421138209600525104047202300339400088872288316077221656240102231143786257343020802118922926269205047219736723123445530507690137692235730009368553776231094320766355040830168009092017813288396850664476916182018546812944453888512931302160127019704913501725813307841245312731953948196722380163601568492780144962109057602369074555334991621987390374358769710617552391326453785020526405147640026146312997938788804138998232289707025657098750218408744926601492274136339769211112547916354899730071425547372588105403900685731200370521951579349841013973635462586811702994385448941952099615457769200940648360138128946530932948358590141678294540263461985603817191898095061752838756758169435695558894946752558724707225186802024978616855725317670898178008742128975014258782925817349723286317727283132139495271815132726481668557882676887050885378442098538933512778731774361164801103687075162670233525972446022073437141634190995911089958638936702125877258733854190658955211486896795807799247056213685696237168010636560453178295430632262922179196184338010387026042081248735157060332183087380384908870579342268028791502144475517809808520966859616554102946100611417937595977703395161367239525150406899496101767146677522362467244175944639777276553647414851795784699778438111349113652477278343467027323819397269455041625832813112347020033822455376729028165116279358528229084987521170918228041096904599804373545811652965962629163714889427307592378384787948608392935161760512373031943294253135653945376467534645062128214176859177671917924470733170543663095164294078188577644263829357684653992808048115290898706559292435665031983147770618047696164278180114571883909560849919923071788171847093498306550580036114960340160679659003480666374351890273587413582104233093778316851445659944947034432138454639433320133679779403332875832288448336528056715331939264128997610951123085318980941191657450923186786281447594211168439296167068599875424211947381124503574287428653464197183586766917064698969607222676938892700337244499023740021533322407975632591913985176741704511237708175586215484912007730703539347900914569981861379239832893109915816827892646998809604355655684309972455745534857625387871413240766757912260561276872396077870424036155192914575494839379065148798577492895218102356645374808828351190560242930341412752377938339484272418298446253783645567893675139638014454360329933950740656010948440208956227962611495754650589391649847173952559561706238119700416870351183225680846641395695009002342404433610812356666485300887852999615689594544734258696785715335953720841080346734273745462225722854716944440612200907986986761974645226700321349237318729650027840661849263165071729001132412715683532938282372956492101123225224688540919293418074389951077117059370386174729181602053802620109858124680047124580359410149534093848987322604588465223269320290130009628419324527856018953957600035078765304742008540572117322791116024555796432461153651126300748828389259598990206877366444955852954604969428779178082528034059004222296475937635225715400197410351141529356047922229074568209997829979346838932511651507196184691420815697818582222639999405831514378102612043068259534775279462337493896484375000000000000000000000000000000000000000000000000000000000000000000000000000000", "997", "5020973558043690795472466436617612912981186347488363636494918897580345094619354831599150783154458643768824774086684855736649234567349871237720799314877192413924062850078649636850002055053944829186672671708163716322615209049354719596052941417213532076312584086034682854165737646092676148538845676199745010081171006469722614059402250242308785689918241284131648855341488804135227553569275395839797208481228297968911162075439845594462320763237357071166784713446778736264921216635219120279353441051381445681864657026276821922514536569544725327622938331970575312038054498527495497627987060787647164378259819498672242544076388147523885345280342831806880870923391335094231290063505894883622740743763068210341558532266730092057471805710970239830698232092553019009302257534520260356188869212033343552453220921330349478151838282759011653076078016714211215874482198987741235273840751410610227050746299055028652883630584960936757395646616847713407087225242767250411952408673845861387774237778205037416623206011306490376976238654472840823151891585075016585390922891098308045393593571415253634799881795632166478595261694471140226795538975637348108530604584641278570409344858021708185167591243455235623668321570654443319286878417340676933354064642723586253821998813504508098460362918587904912942418728303547539706696690550986778207008561820335924406226344605013700816659534219628975931010285852931303562594784807047348570737396800467230532753148948447635460563997386651374238754668022458990241654392066026389403056595070158613582087349737094737658808886315648062674551872063472621765109045797432205715733767132011793304312274933554077784748964538523889920306652843830639205498914392896052991230020283366189067754757119427529149351327101078032307908260603623126125800088927147739506163527183895257938715531016954102699245294031066253590763425350011991169491433278653398617395440744762010472263802586218941241055055743015914720823242262689467262506542601425806024500357983702028225857710867057862345336237222517523041907324188469202303664776657176177623265573649232807583121306909916426816016755317491385615404780845499430052098612881460431944822161954276179349694442740819075713633944412726802575579188952121635648787756123395044724581329422707259129800369169535652642639801159987649031332406466937818074557103914266685904770137348134689897321542175254693720185576746443281607586987415388428553993232704096407666570219410589863873312494539460705640975599199448114612634267109102407317730904132567388335904394477797328315856196208327128937370947369504646584356343462801435206697336876183024095674551448335131879630403438713907124638478413853269148185567784954639444384365569717712309310955147830166043443238005822635747057545664360288684594697328877448799025973804079099439380682972847878899045536018223183365782765974974091131423937943531681735723827404656800066615668567805386492162335823765656414065284523264752292185725090814264699334921326855584899083371098784162003309739906310772506255393733874274017314112532904577039191591007997878380622798755534627692925758417448816637818373973221551606967096451086316437822279771077272376148121571163290736638931514234910318028624294165025145259063674698090046911948075952284431571943853982442651363186672689212765267770285908709835564485153350230618682629074091170797310328555429502555362409867954701387470139759267436167728204441560324447484705204937156843869157813675957725786241495777896024839838398414785265343398641920748711625568412042688914128968190201059965530908706732754193849067931364670270274047648481440681370096814642988815043774848838838626624938922121096710544680023288597319646570406408354982897201465676769575294628096694930977248824011077321485418818924406431852258175057513393216350344049082542468361410424350720060469598506634455467477484979788747749796354609315723688211379376475460277770530264522516753753687913348610617627180044792600195906279194933087464933773782907713330404447333076666728339988449815215434318007623282986066831788891581783579614726180929544276009541965962239461776447541627074351182275490323828208628197483439346482508248446963369489796326385731064053724062808612872776418445167164620078205714184802118485145759294486622205254314132962840493288591203480571662819511051274785273705020148845879775227997407048971388002158100936213131756838746879763532259763345808459116288029766085022119913164248480557500068314593231088987160279569530688677315004982622289441794353406429725797216878712063025668632142903490923190360349140006080712281827399665057312208935502000825739775748382409547767113303970336836210669133926895235962501629552040586816345650814016614025782130788916609032745001899785992601494105680942665185307812466814213377653431289952318114685582720572586088812989364579521550555538171289271181678410758350157911033362222192696775165760690677062098520936755788225598782659548261103482659701827359313630846363889110910616705120073617014817614569968408898086698115057255739332773912661929818195363021921324903304920137570439912113419361155599656792846430129297557180197243737754764342250277820536833873850512952381832218723730563316514909646802035262898179819524477957536959221311168489498330910004725990255589480473575235173541252809932701389183846177964235287033830925857819001160586184156930429524672516539501165080375924833291345560537459192125694725922302068041992414208055805065909773572571976130403681164189313519334650691350894602614796418772828939871059035015115580766571764509536576557130464695399374994550899074089674240089589432866719236464202233403294885582612550745275632442296172192623564576641486142828317213702576891904379598321939228709403256536312047969623685194330246456663079749586499084220375579316652507872292946875012466482824470432774707250524489619450216896375750616444251664515756466570884810083576309586519141251515118124071845062312157097256288192961806792066900270500521144047770243562264487965415262662776051613168034656779642758114200039168472440692230333077279334828068865916779206390832407497613723856853959754467657674563538356200113237531415811715639082774172579453150559544048837197565500009080784265163136751719074454322189938394735894637025740187989314178929192969601790353384766140549815636197188798439691133630864251539048445431466504628211935886080852752935630094058548912025946009818396075472885206608300233436748206662616807944144796532094594620433469104447555629020079624892194386879122958004893129494842096402682811580537753137281234266545777016470955138841847355634423380012680312487848379430425081882125872830213363022475922799999654579438370854572957242484172090786677950121432476319475502042779427036319762004097420400844853692174042251171285933661004386621015926998839941599937383368984020896260270592470934269224540700618758089646022331731630333468362387499863220719689333769720594951447656934220607389756444636956576624383813057790571838503297531863499031792359610404317936111291681774481991887238261842808901836334223213707711107364485905291532705821130807123125454420222217016446133202332841807820589616482431348754917145101606467632094604680353363557871712551081392926909985237301152861238448196740016300218475973366025567832749173016062387042861194087419952458165039784986962997512974528829545248332349853718708838814455644705761832485931700173130071897488979237327246760914209146081519385108482784142154660288373455889906583829801152124158506717738674619195960806284400917112864093439783694796630478012378864676928266821333294750308467294460965175361532830951966724506606586746876954737693583126883851147396217944080036427834332965580301642572700340135310646747719129141401437460780643498914539005330191345728255970110381137385266964222518724087095866095862614718716057244839384375250846048030470719467935727917893539564429681478585454577297831321858756129328359401791440618517519405327157366260531819490852031046823010869408062657846696435219976461406268554894567770971764444584971135801033696477178443244408796389792415991584094216896934420766505635365939320304110028135204359699782309572808211604994257856468898963160670508388545426450891965355149110111299200922903858711721574257678665591805489566917051248264400361657973441314647767689458266932904273127096255063678875054002411113587425151644025362144946685722667666911552246977486100064975984657109331523076430943145383842843621837003905509584456012817099690437316894531250000000000000000000000000000000000000000000000000000000000000000000", "36245651685809845304492628113575794772175397649419099113249877307900325591212664159525112257976186262177576925165788428184727502868295212091525088936946409650133956767734324927766246011976989507374907377126249628035718622112298251507273187", "997", "1013", "1019", "1021", "997", "76993463136706695564099584", "448219", "38496731568353347782049792", "997", "2038", "997", "2550715459588113191740567853821480131", "452303", "850238486529371063913522617940493377", "997", "3057", "997", "823141644718296094427700641815714988069885293953120708465576171875", "458429", "164628328943659218885540128363142997613977058790624141693115234375", "997", "5095", "997", "631438627444550736415080642521598404068584545931170399811149426440245178848956151040482280551968904085414619", "466597", "90205518206364390916440091788799772009797792275881485687307060920035025549850878720068897221709843440773517", "997", "7133", "997", "5073109956636842437922137917951595815016016809", "470681", "461191814239712948902012537995599619546910619", "997", "11209", "997", "438913347985031337591501224029935452069274872286254190655683643165087965696023", "472723", "33762565229617795199346248002302727082251913252788783896591049474237535822771", "997", "13247", "997", "1327219005770146547008686156809262336252304098712358296185474497662899493331386682893480798625505521976657389795886656059621285172228153327439765792208091", "476807", "78071706221773326294628597459368372720723770512491664481498499862523499607728628405498870507382677763332787635052156238801252068954597254555280340718123", "997", "17323", "997", "1610805172267842357617095639683797092166770721", "489059", "84779219593044334611426086299147215377198459", "997", "19361", "997", "2139592160996833904444519196048266285572585258708462244562014613878578784718122611950631792346783335492062143279594557904625677746393365345309654855942839875030957", "497227", "93025746130297126280196486784707229807503706900367923676609331038199077596440113563070947493338405890959223620851937300201116423756233275883028471997514777175259", "997", "23437", "997", "3630479287668869549750268730991097182488777024603224804293163934532866119354925487660843942045312796152147554107969601026775451735159578840647282686001322831", "501311", "125188940954098949991388576930727489051337138779421544975626342570098831701893982333132549725700441246625777727861020725061222473626192373815423540896597339", "997", "29551", "997", "133988324106187784280288196620247367470528903233752384280195808358192193530364030141478616319286544825474620032432885193545948964662015331837905297972451259", "509479", "4322204003425412396138328923233786047436416233346851105812768011554586888076259036821890849009243381466923226852673715920837063376194042962513074128143589", "997", "31589", "997", "5738931991401785278290295421593851207075494906229631943", "513563", "155106270037886088602440416799833816407445808276476539", "997", "37703", "997", "34852745127404453271355467204505037583904157560232023595243138842012775445916534653451148210482054873983793399474308536689963560530019612055489851743503416053101848051770672331302987621294126588219", "519689", "850066954326937884667206517183049697168394086834927404762027776634457937705281333011003614889806216438629107304251427724145452695854136879402191505939107708612240196384650544665926527348637233859", "997", "41779", "997", "12248497864385846776394397892390056468417217564487186546243452016977586379266627254227299054926635541031409485825456387995220131626108414165879951336719480556031331", "531941", "284848787543856901776613904474187359730632966615981082470777953883199683238758773354123233835503152117009522926173404371981863526188567771299533752016732105954217", "997", "43817", "997", "1009515176242195759436333727151660084423170233448167305610109739888867033605693921607825857499212362037761794631882229647666556510526199774621660504072978457006363045937600675597892161507028576725666537473371", "533983", "21479046303025441690134760152162980519641919860599304374683185955082277310759445140592039521259837490165144566635792120163118223628217016481311925618574009723539639275268099480806216202277203760120564627093", "997", "47893", "997", "398646830977963183322447766593140434683576908048526864634254825288673604304004967", "552361", "7521638320338927987215995596096989333652394491481638955363298590352332156679339", "997", "54007", "997", "27944128401974460395330123754686275388009856688602196578125401", "558487", "473629294948719667717459724655699582847624689637325365730939", "997", "60121", "997", "77940803786893016647539322934964966025718379100488200464157090690974981385586170948362089960785846708669816939830504157041168608009049605052660003972843137251140280478249968574051330621847204291870411456652836799", "568697", "1277718094867098633566218408769917475831448837712921319084542470343852153862068376202657212471899126371636343275909904213789649311623764017256721376603985856576070171774589648754939846259790234292957564863161259", "997", "62159", "997", "557222273128694516674162426702913777225589943389658106186243857297684547349274454742677626685673955962922402597754341425208664507439159276967833017800342899319139904259010271667792380324047918033", "574823", "8316750345204395771256155622431548913814775274472509047555878467129620109690663503622054129636924715864513471608273752615054694140882974283101985340303625362972237377000153308474513139164894299", "997", "68273", "997", "17440508702575850052896911458212242773207097595049949521684725971965638090857668453673550447629042635774807276483992681915852975891558766105215085808976020372544754224990747638780047860989301211703499", "580949", "245640967641913381026717062791721729200099966127464077770207408055854057617713640192585217572240037123588834880056234956561309519599419240918522335337690427782320482042123206180000674098440862136669", "997", "72349", "997", "1424380298289275705894559600755711170503199000303179135694877603277659422923208851946781214320169642370322910276576643316546509039955592318643318520069355214503644382280559886430362113741588407066504267684585657137741659", "582991", "19512058880675009669788487681585084527441082195933960762943528812022731820865874684202482387947529347538670003788721141322554918355556059159497513973552811157584169620281642279867974160843676809130195447734050097777283", "997", "74387", "997", "426450076438797242652822176973974841347834224968515749390409652341", "589117", "5398102233402496742440787050303479004402964873019186701144425979", "997", "80501", "997", "824106655669782210425565987496491762126702214637601168400484229048639977197249286980373617053059742599416312068799210836902298656937345312575927639796580262327402995651567079800656463080089983019", "599327", "9928995851443159161753807078270985085863882104067483956632340109019758761412642011811730325940478826498991711672279648637377092252257172440673826985500967015992807176524904575911523651567349193", "997", "84577", "997", "4944528468545255770865574380114221190998471661157926844550406264799390854466449317327746143102114005846689827694830766828943828956818930311295208977848091145573604349436839941159175394504050467760661318694531", "605453", "55556499646575907537815442473193496528072715293909290388206811964038099488387070981210630821372067481423481210054278278976896954570999216980845044694922372422175329768953257765833431398921915368097318187579", "997", "90691", "997", "514996339419582002586289324658434030355366668863920078962167376692296652132613308797333141596921224150313108804994586497792307478786701439693069492499380684727657941859765639397142855552266467039291", "611579", "5309240612573010335941127058334371446962542977978557515073890481363883011676425863890032387597126022168176379432933881420539252358625788038072881365972996749769669503708924117496318098476973887003", "997", "98843", "997", "301442113655254712905909901926689012451481130124254792162323448571207614502495384196126869113454266413263841134002419787734946904753889329810749588333759276172364193230338694508431109559638625045463746364341506749635448119", "613621", "2984575382725294187187226751749396162885951783408463288735875728427798163391043407882444248648062043695681595386162572155791553512414745839710391963700586892795685081488501925826050589699392327182809369943975314352826219", "997", "102919", "997", "2555239879563593045696761114418609456507282255603548227099728781334221193057686271515208071736549649604470137028762071704870151737556338573583097780176553033728339957624547890696818131074248336445137980275782255127376514077", "619747", "24808154170520320832007389460374849092303711219451924534948823119749720320948410403060272541131549996159904242997690016552137395510255714306632017283267505181828543277908231948512797389070372198496485245395944224537636059", "997", "104957", "997", "1012323941142663752943575066252780797696120427731616910828998531998548452296595951381134724249072458579321607158097952811936582645824027310322752213386853835911703333296464759502534737503217216491270980521356531", "625873", "9460971412548259373304439871521315866318882502164644026439238616808864040155102349356399292047406154946930908019607035625575538746018946825446282368101437718800965731742661303762006892553431929824962434779033", "997", "109033", "997", "14538361229487745257682170457856734814405959216469425962052011400576054111276050364279603615018009986387137829571146551766463482651444282213513369961768211142997430772394358145784688162016585046608655019700504896800057220809286471", "629957", "133379460820988488602588719796850778113816139600636935431669829363083065241064682241097280871724862260432457152028867447398747547260956717555168531759341386633003952040315212346648515247858578409253715777068852264220708447791619", "997", "111071", "997", "3375454873554339821014112396646130304474852067498624799546619899489477269929546975713496262833655453356344306236948923050310411808869829632508321207505306583328796000277316597491734113305075324587336522411370280436859", "631999", "29871282066852564787735507934921507119246478473439157518111680526455551061323424563836250113572172153595967311831406398675313378839556014446976293871728376843617663719268288473378177993850224111392358605410356464043", "997", "115147", "997", "39459694765875470141576638079098465499479668623064100064810566131731733407973558410719836295273087266359541647498772639126368333953423358659625851571582603515211711056260787965851889797806599055825412860621841289331451", "644251", "310706257999019449933674315583452484247871406480819685549689497100249869354122507171022333033646356428027886988179312119105262472074199674485242925760492941064659142175281795006707793683516527998625298115132608577413", "997", "129413", "997", "7553129670700810117236177443049339501407393353024497112491720588260921329", "654461", "57657478402296260436917385061445339705399949259728985591539851818785659", "997", "133489", "997", "25980185209260680155983489091150957266592864263389645865369284413013694711280605231725376148215553402565525344770150494341675231231995828510711703056761109302213135579423282202157355856501247492062574715366490096512678476350758824550709012111849700772341340219", "656503", "189636388388764088729806489716430345011626746448099604856710105204479523440004417749820263855587981040624272589563142294464782709722597288399355496764679629943161573572432716804068290923366770015055289893186059098632689608399699449275248263590143801257965987", "997", "139603", "997", "1061284478093134120490574326138962643383576170348591120451178777693851339358901234566104134284107020944540308065951031722956299232212106738300915810230160757429918716369835743989417390909386076858457295662168989239554402068894161149423576941499", "660587", "7635140130166432521514923209632824772543713455745259859360998400675189491790656363784921829382064898881584950114755623906160426131022350635258387123957991060646897240070760748125304970571122855096815076706251721147873396179094684528227172241", "997", "141641", "997", "27806982057853581864459841488908693336336627810182075117867298413541027939991858305143598359129694257228778010677915055505909918139828064754213739020059405463623859463575550295673176217514418739572901818140347404036512846794190316979114076091957059089918247219", "666713", "186624040656735448754764036838313378096218978591826007502465090023765288187864820839889921873353652733079047051529631245006106833153208488283313684698385271567945365527352686548142122265197441205187260524431861772057133199961008838786000510684275564361867431", "997", "151831", "997", "3285953693565530256115800482073279437127404312775462128879985648281136509133852277946366476820598526610405012654942447679756925982034824013822476121812295179872880312347210182423656346523480923472854342890714431110955178199116118028229426669", "672839", "21761282738844571232554970079955492961108637832950080323708514227027394100224187271167989912719195540466258361953261242912297523059833271614718384912664206489224372929451723062408320175652191546177843330402082325238113762908053761776353819", "997", "153869", "997", "622356281582461391123389336535578068400307622361011899125957703826390742157096885215871433085702703260992789059584333983894288210865658524955265536811354609574720641602347188123108545087591929076283949532906136151478757549983", "674881", "3964052748932875102696747366468650117199411607394980249209921680422870969153483345324021866787915307394858529041938433018434956757106105254492137177142386048246628290460810115433812389092942223415821334604497682493495271019", "997", "159983", "997", "10241536787881076649864784083320725924155487294468200096074282642623762885457", "687133", "62831514036080224845796221370065803215677836162381595681437316825912655739", "997", "166097", "997", "11405250480124509891101363855667497861474483259204554342932963047962397866264996748378991721576010916172344867162584304709430613352445633564921189986187763396984414357275984363672100783488186693142363961454827603244723320557", "691217", "68294913054637783779050082968068849469907085384458409239119539209355675845898184122029890548359346803427214773428648531194195289535602596197132874168789002377152181780095714752527549601725668821211760248232500618231876171", "997", "170173", "997", "1944807869360994770207438536559919056634540443061560281988106382931336667032429874652507850233703229371452968943082618826443877218595974482072630868786603739049970890829171640243310329078072773142632259951108763745080055495578703651", "697343", "11241663984745634509869586916531324026789251115962776196463042675903680156256820084696577168980943522378340860942674097262681371205757077931055669761772275948265727692654171330886186873283657648223307860989067998526474309222998287", "997", "176287", "997", "225073418047842319520715088364130442319988885603897716155330438594055372663041", "705511", "1257393396915320220786117812090114202904965841362557073493466137396957389179", "997", "182401", "997", "225329171368509161580472750897026209271177545132054535919092795048175517709558661017404496471571909222764775628194943731479366517164081876622381021735832173151443162628171041881190685097728786249713457178472422049206541511338483211278808636889900059219", "715721", "1244912548997288185527473761862023255641864890232345502315429806895997335411926303963560753986585133827429699603286981941874953133503214787968955921192442945588083771426359347409893287832755725136538437450123878724898019399660128239109439982817127399", "997", "184439", "997", "147948824613896094021559256468208240621247063714817440181805623939619560948705390107983487027464637347879398154756846108483531621445912903031841905046959331289859397842582645928423887704550435180423126450785960262310310693874091438507922975428859476159809606172410845400699", "723889", "774601175988984785453189824440880840948937506360300733936155099160311837427776911560122968730181347371096325417575110515620584405475983785507025680874132624554237685039699716902742867563091283667136787700450053729373354418188960411036245944653714534868113121321522750789", "997", "194629", "997", "3663574983339472396374498535089718440151822588170139197923643104403964824873940016494197681580897911686389150772108064161475879219326417780345224634357375369523896053565948898451794062203069501481019903036711514600073580767056801019", "734099", "18982253799686385473442997591138437513740013410207975118775352872559403237688808375617604567776673117546057776021285306536144451913608382281581474789416452691833658308631859577470435555456318660523419186718712510881210263041745083", "997", "196667", "997", "8455278772776224374271023592698437808269362247194077422320886658621746174281418149174663922086515928205781678321990770649841595335371231946470738240060062353185284927152119985585357359688807996283753901135009827258161244214785267280127016797383", "742267", "42920196816122966366857987780195115778017067244639986915334450043765209006504660655708953919220893036577571971177618125126099468707468182469394610355634834280128349884020913632412981521262984752709410665659948361716554539161346534416888410139", "997", "200743", "997", "7418664063326667174171516407096672529836721739118262523809114802763367797444381", "748393", "37279718911189282282268926668827500149933275070946042833211632174690290439419", "997", "202781", "997", "1216142943931601900840499346326153294372963200662871598602878771751067301282935383481935570679941736286303494921026416345368409318863091781019560429709350064711390142526964314902108955296323216588439774090112698978970772874445246117374500899", "754519", "5763710634746928440002366570266129357217835074231618950724543941948186262004433097070784695165600645906651634696807660404589617624943562943220665543646208837494740011976134193848857608039446524115828313223282933549624515992631498186609009", "997", "215009", "997", "138691792998900981393067649792787848641037326193951782941236989320550933465674492476050781517256816980352563136501783747517774908582709149868844034074488483067697567425768441388229379485083067254522425925225280069810787466572004302011", "758603", "621936291474892293242455828667210083592095633156734452651286947625788939307957365363456419359896040270639296576241182724294954747007664349187641408405777950976222275451876418781297665852390436118934645404597668474487836172968629157", "997", "227237", "997", "2028493490644134181545071400466908110867796623181315854487633734557528690094386218346576853932530189093546742060337625157893636505419736098290811151374445048600018545156783393583253452964962427130653747772754254546889532223197256645401908955067327736231726068875643791579593259", "766771", "8936094672441119742489301323642767008228178956745884821531426143425236520239586864962893629658723299971571550926597467655919103548104564309651150446583458363876733679104772658957063669449173687800236774329313896682332741071353553503973167202939769763135357131610765601672217", "997", "231313", "997", "14149311638818710272508768215683034141538149399907158174569462453878173117322097753573649385838904038871126756217699203940141028311501017698570123066261061120171424198367746633234728713058889449330070324521632921517787014310284981552853646663319503779299", "772897", "61787387069077337434536105745340760443398032314005057530871015082437437193546278399884931815890410650092256577369865519389262132364633265059258179328650921922145957198112430712815409227331394975240481766470012757719593948953209526431675312940259841831", "997", "233351", "997", "30093876104292118234789101271657244880699998710604456683832260298422030702485065967861524326546606571039352053995299041938053973700300262936244544083334881309585916203495310045228392711906230431409629365533390067925197505085591927635071892148491", "776981", "129158266542026258518408159964194184037339050260104964308292962654171805590064660806272636594620629060254729845473386446086068556653649197151264137696716228796506078126589313498834303484576096272144332040915837201395697446719278659377990953427", "997", "237427", "997", "3341433274322410860909358920965655465914609433427753011787584445887163322575233606213353128070580943023650547154816689267633028226655069995528795004468493200031965955545943936872867057651796177238218640454146294226353627831975242231915884119383355513992675163415937324785211381", "785149", "13980892361181635401294388790651278100061127336517795028399934920029972060984241030181393841299501853655441619894630499027753256178473096215601652738361896234443372198937003919970155052936385678820998495624043072076793421891109800133539264097838307589927511143999737760607579", "997", "243541", "997", "4118476469007064308947375538559785902711241611772556924176911678360484298072250699", "789233", "17089113979282424518453840408961767231166977642209779768368928125977113270009339", "997", "245579", "997", "931152388751175201699068624778090289867417543528220592117152773927749269913068388840365617398521258477932276771590394237676949552026467097846301304616397612088831084369673137110207936130665169120295304026669889420982367047795994272488560887275037507805158319176442153344967337522071321821019", "803527", "3709770473112251799597882967243387609033536029992910725566345712859558844275172863905839113141518958079411461241395992978792627697316601983451399619985647856927613881950888992470947952711813422790021131580358125183196681465322686344575939789940388477311387725802558379860427639530164628769", "997", "255769", "997", "2891247412588934131535766310701430184913777993027195144625265514460073835877768281374678458180366942013537958473137407582426122601856395302375298667160312868283179007377451488414685852848881981660077537670642989489234007367886409503052947081175934785149006331", "813737", "11249989932252661990411542064986109668925206198549397449903756865603400139602211211574624350896369424177190499895476294095043278606445117908075092090117948903825599250495920188383991645326389033696799757473319025249937771859480192618883062572669006946105083", "997", "261883", "997", "13899422530678692053654718384395654516426347025655826879567494777451559730600568674546707009339019292739476335367327016017867581118288482087649526209799357787918091759795268071323583783939990378975910915464265365184472642331075137172120703394599859293071808179295648708579999684135452477", "825989", "52849515325774494500588282830401728199339722531010748591511386986507831675287333363295463913836575257564548803678049490562234148738739475618439263155130637976874873611388851982218949748821256193824756332563746635682405484148574666053690887431938628490767331480211592047832698418765979", "997", "267997", "997", "1355699963191169974672204718471466004562253812733568890856366430755543607435448494756142541415471836728113575979434855183498286076476238071951618737682287160425884197494461103908314040707400572892652361779504788601631816417329651376067771467758410992920761631", "828031", "5039776814837063102870649511046342024394995586370144575674224649648860994183823400580455544295434337279232624458865632652409985414409806958927950697703669741360164302953387003376632121588849713355584988027898842385248388168511715152668295419176249044315099", "997", "274111", "997", "197770168183920893490702355213946062548862275593686785036823325489830493680361725109", "838241", "729779218390852005500746698206443035235654153482239059176469835755832080001334779", "997", "276149", "997", "235066939145603730138455797181895332556660643522557763976711397934654296027286248141866352067440614645980785211857345634122543197521067658886043737467928065242170439144153675267262025034856560884161819395341422586089798939047835618577282359011", "840283", "848617108828894332629804321956300839554731565063385429518813710955430671578650715313596938871626767675020885241362258606940589160725876024859363673169415397986174870556511463058707671605980364202750250524698276484078696530858612341434232343", "997", "282263", "997", "653856944817121418564574769158558214241652061694177451283815899696349734329343253379", "844367", "2326893042053812877454002737219068378084171038057571001010020995360675211136452859", "997", "286339", "997", "153750924705191331202642487855432301214999247349347135664932925672884382532572106143629862520851000964392448797347295129760339890447171549018979033727220079019470962832403597856104509630053226079444303822073464068832801004488749074363606794131843019", "846409", "543289486590782089055273808676439226908124548937622387508596910504891811069159385666536616681452300227535154760944505758870458976845129148476957716350600985934526370432521547194715581731636841270121214918987505543578802136002646905878469237214993", "997", "288377", "997", "9247489933034770345008842513605671240539329503796940360077790769034919055860192075961498268156080222753546521642413997960863602513249430650096399945058850657850730509948718278723816846696059730196008820021372108447626975263432296338773003684247622175988091632568335607339591109011826268182783373997524131", "856619", "31561399088855871484671817452579082732216141651184096792074371225375150361297583877001700573911536596428486421987761085190660759430885428839919453737402220675258465904261837128750228145720340376095593242393761462278590359260861079654515370935998710498252872466103534496039560099016471905060694109206567", "997", "298567", "997", "1717407504335870232912715929360339133649245648531977431437710884144242413898244908199676348333630782469611821101441951565524681310844200869852683280497944626558680801715390769378642397671865997499800973267974091300091032739882947247896538134151189417", "870913", "5594161251908372094178227782932700761072461395869633327158667375062678872632719570682984847992282679054110166454208311288354010784508797621669978112371155135370295771059904786249649503817153086318569945498286942345573396546849991035493609557495731", "997", "312833", "997", "186094640094728709905582884915209478720162295193640169865982338425202130855964448777365803096561599373266189003786443004976861963671620462507490499001087000062228617512324435299563374854468112230954656065794720439794736047301775255274615166365555906615082699", "874997", "598375048536105176545282588151798966945859470076013407929203660531196562237827809573523482625599997984778742777448369790922385735278522387483892279746260450360863721904580177812100883776424798170272205999339937105449312049201849695416769023683459506800909", "997", "316909", "997", "99031418963697124674853988324325827852540883371919853044916122582908820976031775150461062479829273919254632432784471230762209126862746456311631012017430778342731130579275835965526802369447102695762351319328603240840216102895901102277717945225511617318692885468391820057855359602494115072883", "877039", "316394309788169727395699643208708715183836688089200808450211254258494635706171805592527356165588734566308729817202783484863287945248391234222463297180290026654093068943373277845133553895997133213298247026608956041023054641839939623890472668452113793350456503093903578459601787867393338891", "997", "318947", "997", "42242760426214852365008492021688249001199142271915160025206075397415289834494590552596465606988123248212551380300285932126774225020692469707080058167842164648746139668051737622910245137506042977114350839236678790426338968454103079402971043834421080175047132836133633496964302426327", "881123", "133257919325598903359648239816051258678861647545473690931249449203202807048878834550777494028353701098462307193376296315857331940128367412325173685072057301731060377501740497233155347436927580369445901701062078203237662361053952931870571116196911924842419977401052471599256474531", "997", "323023", "997", "107307369572290541384475737454740253494018594946523953948261811827034605510928874078489851241855815524617369122814813937716249011703046172889308428655342212025001891566435646387451504158097825535109820621633632481094109611807638752054352547330203174484844484659", "895417", "324191448858883810829231835210695629891294848781039135795352905821856814232413516853443659340954125452016220914848380476484135987018266383351384980831849583157105412587418871261182792018422433640815168041189221997263171032651476592309222197372215028655119289", "997", "337289", "997", "55064612321770155133157362474829199989035428581948598172981940137568403555187622908028564874669701059511946421406182521933816203496055859680958661046865172951343822363678488724509509061180572829585917059572354958143854719027588481590624599078397653942081134186048842079801519289417050168490082593323", "899501", "163396475732255653214116802595932344181114031400440944133477567173793482359607189638066958085073296912498357333549503032444558467347346764631924810228086566621198285945633497698841273178577367446842483856297789193305206881387502912731823736137678498344454404112904575904455546852869585069703509179", "997", "343403", "997", "191910400529505153557224617029107865694106741205348818904526992376067891765008424641623636027152487218384283069648741467693297373871543851103342180022015891721139900840652679154541010152081242584577176398651308152433498225132989871250359174352180752175700889727556239511651", "901543", "553055909306931278262895149939792120155927208084578728831489891573682685201753385134362063478825611580358164465846517197963393008275342510384271412167192771530662538445684954335853055193317701972844888756920196404707487680498529888329565343954411389555333976160104436633", "997", "353593", "997", "195306582131271451009334326954770025184144851578630324452422872021506820732014956379715234978255404349682123138757786675633123282560391857045894094521929176524667838378563095623212129113112952618142325576737520038648102942539205523023679173996788382216711019", "905627", "559617713843184673379181452592464255541962325440201502729005363958472265707779244641017865267207462320006083492142655231040467858339231682079925772269138041617959422288146405797169424392873789736797494489219255125066197543092279435597934595979336338729831", "997", "355631", "997", "1215456615647736981075511688343015609651098104001912463828764256884376773285956483375387", "926047", "3443219874356195413811647842331488979181581031166890832376102710720614088628771907579", "997", "359707", "997", "152371024479309333613791270766813059934644240963510757940065726092042020167346294014239858246488261844181541553866797374541435361748272964733304606225836878830766560242205779764084434055945144673618075979996122754129399688334667194097420399639375481262924139926860301", "930131", "424431823062142990567663706871345570848591200455461721281520128390089192666702768841893755561248640234488973687651246168639095715176247812627589432383946737690157549421186016055945498763078397419548958161549088451613926708453111961274151531028901062013716267205739", "997", "365821", "997", "8805855872789019240710264044493313902829667579523595450483405927948456557973767381593768592699990307656047373848464298739897608488173415985344555327733960422040018571984480783688585363881034183770028635322562755061525965264076157536693656742309428857200200534740552445744340920479346348313632819317", "938299", "23994157691523213189946223554477694558118985230309524388238163291412688168865851176004819053678447704784870228469929969318522093973224566717560096260855477989209859869167522571358543225833880609727598461369380803982359578376229312089083533357791359283924252138257636091946433025829281603034421851", "997", "373973", "997", "1095376316278855322873293779067055170364191817021514439349116525031244403693815779672168678363649208457797649035029957775057822028226826207868697627085868397348111959279609148252080232892263125008811953482298559446432650497666173228960391046465035759461531583942148845722771586537518927520699", "948509", "2936665727289156361590599943879504478188181815071084287799240013488590894621490025930747126980292784069162597949141977949216681040822590369621173262964794630960085681714769834455979176654860924956600411480693188864430698385164003294799975995884814368529575292070104144028878248089863076463", "997", "380087", "997", "15369226844695333062849381477909582790193081087319522766401784914789199098254937701754942361481513813591507178592892064416009512989526432006888411812015707106697003660843933262218400518290304215112593252662042221838402637726323711885254485048250408355850463886893101619739", "956677", "40552049722151274572161956406093885989955359069444651098685448323982055668218832986160797787550168373592367225838765341467043569893209583131631693435397644080994732614363940005853299520554892388159876656100375255510297197167081033998032942079816380886148981231907919841", "997", "386201", "997", "17936335753803465319644606369717202510207061261553117383696431100566559448104053392344197", "960761", "46831163848050823288889311670279902115423136453141298651948906267797805347530165515259", "997", "390277", "997", "25893139746956375074671910466488819057973682757474498176744179853848279269471981476034178206434626829662341282305098421017615074690674938772214414369410376488767243876576772000943323646306806499600311513657727872637967224802501913807127372752863262895742486671", "966887", "66563341251815874227948355954984110688878361844407450325820513763106116373963962663326936263328089536407046998213620619582558032623843030262761990666864721050815536957780904886743762586906957582520081011973593502925365616458873814414209184454661344204993539", "997", "396391", "997", "73974572111317406360276225631919880970967230930546543997873687812509688512760842513788622380060283819337381239289168279398371925148558197982252822440463431991798888852483797550848552471579198228007110388157478970670518327902466795935796129943875075370218141183995374789284599233523734628628605149143767", "973013", "186333934789212610479285203103072748037700833578202881606734730006321633533402625979316429168917591484477030829443748814605470844202917375270158242923081692674556395094417626072666379021610071103292469491580551563401809390182536009913844156029912028640347962680089105262681610160009407125009080980211", "997", "404543", "997", "1307141793874862084461913041302240551365792174026016528279865697359005336719217669177196976468676813204191353984957820150881355004620906305582162121381248966040062853839635204011545101328676009151433346953408816476579132602933740590965014866256568699705065819", "987307", "3259705221633072529830207085541747010887262279366624758802657599399015802292313389469319143313408511731150508690667880675514601009029691535117611275264960015062500882393105246911583793837097279679384905120720240589972899259186385513628466000639822193778219", "997", "408619", "997", "7093242912463185348072070110212638351742462073193796871217834643050267179901187029507018490754437695656607535423037831588564687811978689937562105842348187968983989171429748478114974959055204956755248726089665726321535007236838047456328883300447788907493192538880498815296925888779", "991391", "17342892206511455618758117628881756361228513626390701396620622599144907530320750683391243253678331774221534316437745309507493124234666723563721530176890435131990193573177869139645415547812237058081292728825588572913288526251437768841879910270043493661352548994817845514173412931", "997", "416771", "997", "1185579641965561589160299697265721932824027132750467864460376877428924099444308658448594136390967744065181760700818974092571770178341715224937792646992702816801853703682587972668759794434610387225171807457005618044826070319744092967744160173564727037441446431202779572868249757967428377671066761", "997517", "2829545684882008566015035077006496259723215113962930464105911401978339139485223528516931113104934950036233319095033351056257208062868055429445805840078049682104662777285412822598472063089762260680600972451087393901732864724926236199866730724498155220623977162775130245508949303024888729525219", "997", "426961", "997", "169052738021865017945085217436498678340551974017269410534135929153837234291820715450799841864356228195340732263779", "1003643", "401550446607755387042957761131825839288722028544582922883933323405789155087460131712113638632675126354728580199", "997", "428999", "997", "89600456898162554710940038315160351182309734414129170687610033541862560707475499371198298316876962891405560250165152771675263407396177488042619118232855720276625778667788670057647578107276749358158513983871052535363437572582097937450349496907401800441822855338949217171751568948262972788043043591458773382280560737161315249005363622939", "1011811", "207889691179031449445336515812437009703734882631390187210232096384831927395534801325286074981153046151753040023585041233585297928993451248358745053904537634052496006189764895725400413241941413824033675136591769223581061653322733033527493032267753597312814049510323009679237978998289960065065066337491353555175314935409084104420797269", "997", "439189", "997", "433", "1013", "1019"
};
char *off_60E2E8[845] =
{
"1994", "1009", "437683", "1009", "2991", "1009", "441671", "1009", "4985", "1009", "447653", "1009", "6979", "1009", "455629", "1009", "10967", "1009", "459617", "1009", "12961", "1009", "461611", "1009", "16949", "1009", "465599", "1009", "18943", "1009", "477563", "1009", "22931", "1009", "485539", "1009", "28913", "1009", "489527", "1009", "30907", "1009", "497503", "1009", "36889", "1009", "501491", "1009", "40877", "1009", "507473", "1009", "42871", "1009", "519437", "1009", "46859", "1009", "521431", "1009", "52841", "1009", "539377", "1009", "58823", "1009", "545359", "1009", "60817", "1009", "555329", "1009", "66799", "1009", "561311", "1009", "70787", "1009", "567293", "1009", "72781", "1009", "569287", "1009", "78763", "1009", "575269", "1009", "82751", "1009", "585239", "1009", "88733", "1009", "591221", "1009", "96709", "1009", "597203", "1009", "100697", "1009", "599197", "1009", "102691", "1009", "605179", "1009", "106679", "1009", "611161", "1009", "108673", "1009", "615149", "1009", "112661", "1009", "617143", "1009", "126619", "1009", "629107", "1009", "130607", "1009", "639077", "1009", "136589", "1009", "641071", "1009", "138583", "1009", "645059", "1009", "148553", "1009", "651041", "1009", "150547", "1009", "657023", "1009", "156529", "1009", "659017", "1009", "162511", "1009", "670981", "1009", "166499", "1009", "674969", "1009", "172481", "1009", "680951", "1009", "178463", "1009", "688927", "1009", "180457", "1009", "698897", "1009", "190427", "1009", "706873", "1009", "192421", "1009", "716843", "1009", "196409", "1009", "724819", "1009", "198403", "1009", "730801", "1009", "210367", "1009", "736783", "1009", "222331", "1009", "740771", "1009", "226319", "1009", "748747", "1009", "228313", "1009", "754729", "1009", "232301", "1009", "758717", "1009", "238283", "1009", "766693", "1009", "240277", "1009", "770681", "1009", "250247", "1009", "784639", "1009", "256229", "1009", "794609", "1009", "262211", "1009", "806573", "1009", "268193", "1009", "808567", "1009", "270187", "1009", "818537", "1009", "276169", "1009", "820531", "1009", "280157", "1009", "824519", "1009", "282151", "1009", "826513", "1009", "292121", "1009", "836483", "1009", "306079", "1009", "850441", "1009", "310067", "1009", "854429", "1009", "312061", "1009", "856423", "1009", "316049", "1009", "860411", "1009", "330007", "1009", "874369", "1009", "335989", "1009", "878357", "1009", "345959", "1009", "880351", "1009", "347953", "1009", "884339", "1009", "351941", "1009", "904279", "1009", "357923", "1009", "908267", "1009", "365899", "1009", "916243", "1009", "371881", "1009", "926213", "1009", "377863", "1009", "934189", "1009", "381851", "1009", "938177", "1009", "387833", "1009", "944159", "1009", "395809", "1009", "950141", "1009", "399797", "1009", "964099", "1009", "407773", "1009", "968087", "1009", "417743", "1009", "974069", "1009", "419737", "1009", "980051", "1009", "429707", "1009", "988027", "1009", "431701", "997", "1009", "628342186020279030208477196652234251466546172127229920271442149116418270266805114129323801879492482137898525457610034761318243685701612999753301446499402184019047334363868952491996606714667813682795710496729144356627735845123676166105603998123636223487640503561426022924983170637012661801780667366986496506030776535567526896671098662632123365168743664803047333533266651378724651134747558720373671125128918192606546275484822315302537833017347515852873969123863196991591128905797797953641849823901200591253758989661116185809449387114754110693862270878790685521494032855174559448217678703819332109924602615048084195117590112536399286371826740412069584415578436175604905487388386875110557418165843986191168930994241095051887359640391104091658653518621901534663248053930033780121015835031607604047633957687509170016778799461147891167654749638057549827992932889122995155539900942798016011513799665913318026811781018347609393399492693089473128154346668249800406988857586278307546023464942900979079319193897231953014331315745983540688409217523781284767071786748835334904114251151768066947066974655638700742353772603987770915012114230380632982060506677995390598274839813186589487880327769882355406369328704667144104785532210079866539787033200765829359931127219031553817186725838729517291842565585345287913859037622248318083084610913049915914358110409209100852502593148685289707303219729372851454213282755549475037954209582986949880668930047153621586488494270546617243702586105425080170041634818438278320529852112847863734593944644022898353545446882029646417103689943919192691294079623058308937404741503543204905870498980563398747865075941095954326295793595346961572874520213826034401809759600671385592618044358788220764179037648551723688883462655964529249402109637617708231973919514209153002131026182417912198411370401495384651131774509722038523496382808921942374492604612687129063485332311030348703446367201242825533393540915424705051574412572120162877997562692412185247999611773833311632900771473429755915441182540269617877214830627528032509574263455045777758312790203647404347503161728097958892560903112974915627570659454527665768438056409725068410760146580760573561825743041360562327507023011036093343294488329397226160195885463366678787014633928020875226483619664858890687676379225725094561398719056931046049652997474332655225198880371911150572119222293804816869964938939569929273415161422698066449231388944785154171990521448471715053090799940542872248125377623217571815993265916187470537162268436325773823823025764997980088398890569841898462161853267169228882950197460075182837289919940982931539635781819167833327053366074466169096663110752528063831392419664656628996209161385538062512860770349218644155662924022242464260618852724359227862586009757511987837154780681347585339557128064674324666633148721900366457274096873746373036267539915146015258255209166409983804123119669569892997296082665906047894529706757974988307364081640652759420620606279591460036311764255114156837496511088449627305129870293650489346534475746640218520980739890581556540008279019229663760636485837245208764597357678419738833265275277731038701789683747837440024384633103957164283508891650623445519394459252271959449686279179444136374415706603701561041515600084286014592770962766546924881353153028839585503598573550964862568899783340905087121767189848319028823764126564635152182745746588976064614585513882178320384662630419491983556919743035918979272357120571425297548004511661675273618557126654548778343459193970691487722304790664607581194061709590959173879314951330697843870052828316024354166567082187518547658698577696795531130565515421083180252264454883596870044949725930149179966847413679961101162747165984569728196830920577134702664306366364197595517421138209600525104047202300339400088872288316077221656240102231143786257343020802118922926269205047219736723123445530507690137692235730009368553776231094320766355040830168009092017813288396850664476916182018546812944453888512931302160127019704913501725813307841245312731953948196722380163601568492780144962109057602369074555334991621987390374358769710617552391326453785020526405147640026146312997938788804138998232289707025657098750218408744926601492274136339769211112547916354899730071425547372588105403900685731200370521951579349841013973635462586811702994385448941952099615457769200940648360138128946530932948358590141678294540263461985603817191898095061752838756758169435695558894946752558724707225186802024978616855725317670898178008742128975014258782925817349723286317727283132139495271815132726481668557882676887050885378442098538933512778731774361164801103687075162670233525972446022073437141634190995911089958638936702125877258733854190658955211486896795807799247056213685696237168010636560453178295430632262922179196184338010387026042081248735157060332183087380384908870579342268028791502144475517809808520966859616554102946100611417937595977703395161367239525150406899496101767146677522362467244175944639777276553647414851795784699778438111349113652477278343467027323819397269455041625832813112347020033822455376729028165116279358528229084987521170918228041096904599804373545811652965962629163714889427307592378384787948608392935161760512373031943294253135653945376467534645062128214176859177671917924470733170543663095164294078188577644263829357684653992808048115290898706559292435665031983147770618047696164278180114571883909560849919923071788171847093498306550580036114960340160679659003480666374351890273587413582104233093778316851445659944947034432138454639433320133679779403332875832288448336528056715331939264128997610951123085318980941191657450923186786281447594211168439296167068599875424211947381124503574287428653464197183586766917064698969607222676938892700337244499023740021533322407975632591913985176741704511237708175586215484912007730703539347900914569981861379239832893109915816827892646998809604355655684309972455745534857625387871413240766757912260561276872396077870424036155192914575494839379065148798577492895218102356645374808828351190560242930341412752377938339484272418298446253783645567893675139638014454360329933950740656010948440208956227962611495754650589391649847173952559561706238119700416870351183225680846641395695009002342404433610812356666485300887852999615689594544734258696785715335953720841080346734273745462225722854716944440612200907986986761974645226700321349237318729650027840661849263165071729001132412715683532938282372956492101123225224688540919293418074389951077117059370386174729181602053802620109858124680047124580359410149534093848987322604588465223269320290130009628419324527856018953957600035078765304742008540572117322791116024555796432461153651126300748828389259598990206877366444955852954604969428779178082528034059004222296475937635225715400197410351141529356047922229074568209997829979346838932511651507196184691420815697818582222639999405831514378102612043068259534775279462337493896484375000000000000000000000000000000000000000000000000000000000000000000000000000000", "997", "5020973558043690795472466436617612912981186347488363636494918897580345094619354831599150783154458643768824774086684855736649234567349871237720799314877192413924062850078649636850002055053944829186672671708163716322615209049354719596052941417213532076312584086034682854165737646092676148538845676199745010081171006469722614059402250242308785689918241284131648855341488804135227553569275395839797208481228297968911162075439845594462320763237357071166784713446778736264921216635219120279353441051381445681864657026276821922514536569544725327622938331970575312038054498527495497627987060787647164378259819498672242544076388147523885345280342831806880870923391335094231290063505894883622740743763068210341558532266730092057471805710970239830698232092553019009302257534520260356188869212033343552453220921330349478151838282759011653076078016714211215874482198987741235273840751410610227050746299055028652883630584960936757395646616847713407087225242767250411952408673845861387774237778205037416623206011306490376976238654472840823151891585075016585390922891098308045393593571415253634799881795632166478595261694471140226795538975637348108530604584641278570409344858021708185167591243455235623668321570654443319286878417340676933354064642723586253821998813504508098460362918587904912942418728303547539706696690550986778207008561820335924406226344605013700816659534219628975931010285852931303562594784807047348570737396800467230532753148948447635460563997386651374238754668022458990241654392066026389403056595070158613582087349737094737658808886315648062674551872063472621765109045797432205715733767132011793304312274933554077784748964538523889920306652843830639205498914392896052991230020283366189067754757119427529149351327101078032307908260603623126125800088927147739506163527183895257938715531016954102699245294031066253590763425350011991169491433278653398617395440744762010472263802586218941241055055743015914720823242262689467262506542601425806024500357983702028225857710867057862345336237222517523041907324188469202303664776657176177623265573649232807583121306909916426816016755317491385615404780845499430052098612881460431944822161954276179349694442740819075713633944412726802575579188952121635648787756123395044724581329422707259129800369169535652642639801159987649031332406466937818074557103914266685904770137348134689897321542175254693720185576746443281607586987415388428553993232704096407666570219410589863873312494539460705640975599199448114612634267109102407317730904132567388335904394477797328315856196208327128937370947369504646584356343462801435206697336876183024095674551448335131879630403438713907124638478413853269148185567784954639444384365569717712309310955147830166043443238005822635747057545664360288684594697328877448799025973804079099439380682972847878899045536018223183365782765974974091131423937943531681735723827404656800066615668567805386492162335823765656414065284523264752292185725090814264699334921326855584899083371098784162003309739906310772506255393733874274017314112532904577039191591007997878380622798755534627692925758417448816637818373973221551606967096451086316437822279771077272376148121571163290736638931514234910318028624294165025145259063674698090046911948075952284431571943853982442651363186672689212765267770285908709835564485153350230618682629074091170797310328555429502555362409867954701387470139759267436167728204441560324447484705204937156843869157813675957725786241495777896024839838398414785265343398641920748711625568412042688914128968190201059965530908706732754193849067931364670270274047648481440681370096814642988815043774848838838626624938922121096710544680023288597319646570406408354982897201465676769575294628096694930977248824011077321485418818924406431852258175057513393216350344049082542468361410424350720060469598506634455467477484979788747749796354609315723688211379376475460277770530264522516753753687913348610617627180044792600195906279194933087464933773782907713330404447333076666728339988449815215434318007623282986066831788891581783579614726180929544276009541965962239461776447541627074351182275490323828208628197483439346482508248446963369489796326385731064053724062808612872776418445167164620078205714184802118485145759294486622205254314132962840493288591203480571662819511051274785273705020148845879775227997407048971388002158100936213131756838746879763532259763345808459116288029766085022119913164248480557500068314593231088987160279569530688677315004982622289441794353406429725797216878712063025668632142903490923190360349140006080712281827399665057312208935502000825739775748382409547767113303970336836210669133926895235962501629552040586816345650814016614025782130788916609032745001899785992601494105680942665185307812466814213377653431289952318114685582720572586088812989364579521550555538171289271181678410758350157911033362222192696775165760690677062098520936755788225598782659548261103482659701827359313630846363889110910616705120073617014817614569968408898086698115057255739332773912661929818195363021921324903304920137570439912113419361155599656792846430129297557180197243737754764342250277820536833873850512952381832218723730563316514909646802035262898179819524477957536959221311168489498330910004725990255589480473575235173541252809932701389183846177964235287033830925857819001160586184156930429524672516539501165080375924833291345560537459192125694725922302068041992414208055805065909773572571976130403681164189313519334650691350894602614796418772828939871059035015115580766571764509536576557130464695399374994550899074089674240089589432866719236464202233403294885582612550745275632442296172192623564576641486142828317213702576891904379598321939228709403256536312047969623685194330246456663079749586499084220375579316652507872292946875012466482824470432774707250524489619450216896375750616444251664515756466570884810083576309586519141251515118124071845062312157097256288192961806792066900270500521144047770243562264487965415262662776051613168034656779642758114200039168472440692230333077279334828068865916779206390832407497613723856853959754467657674563538356200113237531415811715639082774172579453150559544048837197565500009080784265163136751719074454322189938394735894637025740187989314178929192969601790353384766140549815636197188798439691133630864251539048445431466504628211935886080852752935630094058548912025946009818396075472885206608300233436748206662616807944144796532094594620433469104447555629020079624892194386879122958004893129494842096402682811580537753137281234266545777016470955138841847355634423380012680312487848379430425081882125872830213363022475922799999654579438370854572957242484172090786677950121432476319475502042779427036319762004097420400844853692174042251171285933661004386621015926998839941599937383368984020896260270592470934269224540700618758089646022331731630333468362387499863220719689333769720594951447656934220607389756444636956576624383813057790571838503297531863499031792359610404317936111291681774481991887238261842808901836334223213707711107364485905291532705821130807123125454420222217016446133202332841807820589616482431348754917145101606467632094604680353363557871712551081392926909985237301152861238448196740016300218475973366025567832749173016062387042861194087419952458165039784986962997512974528829545248332349853718708838814455644705761832485931700173130071897488979237327246760914209146081519385108482784142154660288373455889906583829801152124158506717738674619195960806284400917112864093439783694796630478012378864676928266821333294750308467294460965175361532830951966724506606586746876954737693583126883851147396217944080036427834332965580301642572700340135310646747719129141401437460780643498914539005330191345728255970110381137385266964222518724087095866095862614718716057244839384375250846048030470719467935727917893539564429681478585454577297831321858756129328359401791440618517519405327157366260531819490852031046823010869408062657846696435219976461406268554894567770971764444584971135801033696477178443244408796389792415991584094216896934420766505635365939320304110028135204359699782309572808211604994257856468898963160670508388545426450891965355149110111299200922903858711721574257678665591805489566917051248264400361657973441314647767689458266932904273127096255063678875054002411113587425151644025362144946685722667666911552246977486100064975984657109331523076430943145383842843621837003905509584456012817099690437316894531250000000000000000000000000000000000000000000000000000000000000000000", "36245651685809845304492628113575794772175397649419099113249877307900325591212664159525112257976186262177576925165788428184727502868295212091525088936946409650133956767734324927766246011976989507374907377126249628035718622112298251507273187", "997", "1013", "1019", "1021", "997", "76993463136706695564099584", "448219", "38496731568353347782049792", "997", "2038", "997", "2550715459588113191740567853821480131", "452303", "850238486529371063913522617940493377", "997", "3057", "997", "823141644718296094427700641815714988069885293953120708465576171875", "458429", "164628328943659218885540128363142997613977058790624141693115234375", "997", "5095", "997", "631438627444550736415080642521598404068584545931170399811149426440245178848956151040482280551968904085414619", "466597", "90205518206364390916440091788799772009797792275881485687307060920035025549850878720068897221709843440773517", "997", "7133", "997", "5073109956636842437922137917951595815016016809", "470681", "461191814239712948902012537995599619546910619", "997", "11209", "997", "438913347985031337591501224029935452069274872286254190655683643165087965696023", "472723", "33762565229617795199346248002302727082251913252788783896591049474237535822771", "997", "13247", "997", "1327219005770146547008686156809262336252304098712358296185474497662899493331386682893480798625505521976657389795886656059621285172228153327439765792208091", "476807", "78071706221773326294628597459368372720723770512491664481498499862523499607728628405498870507382677763332787635052156238801252068954597254555280340718123", "997", "17323", "997", "1610805172267842357617095639683797092166770721", "489059", "84779219593044334611426086299147215377198459", "997", "19361", "997", "2139592160996833904444519196048266285572585258708462244562014613878578784718122611950631792346783335492062143279594557904625677746393365345309654855942839875030957", "497227", "93025746130297126280196486784707229807503706900367923676609331038199077596440113563070947493338405890959223620851937300201116423756233275883028471997514777175259", "997", "23437", "997", "3630479287668869549750268730991097182488777024603224804293163934532866119354925487660843942045312796152147554107969601026775451735159578840647282686001322831", "501311", "125188940954098949991388576930727489051337138779421544975626342570098831701893982333132549725700441246625777727861020725061222473626192373815423540896597339", "997", "29551", "997", "133988324106187784280288196620247367470528903233752384280195808358192193530364030141478616319286544825474620032432885193545948964662015331837905297972451259", "509479", "4322204003425412396138328923233786047436416233346851105812768011554586888076259036821890849009243381466923226852673715920837063376194042962513074128143589", "997", "31589", "997", "5738931991401785278290295421593851207075494906229631943", "513563", "155106270037886088602440416799833816407445808276476539", "997", "37703", "997", "34852745127404453271355467204505037583904157560232023595243138842012775445916534653451148210482054873983793399474308536689963560530019612055489851743503416053101848051770672331302987621294126588219", "519689", "850066954326937884667206517183049697168394086834927404762027776634457937705281333011003614889806216438629107304251427724145452695854136879402191505939107708612240196384650544665926527348637233859", "997", "41779", "997", "12248497864385846776394397892390056468417217564487186546243452016977586379266627254227299054926635541031409485825456387995220131626108414165879951336719480556031331", "531941", "284848787543856901776613904474187359730632966615981082470777953883199683238758773354123233835503152117009522926173404371981863526188567771299533752016732105954217", "997", "43817", "997", "1009515176242195759436333727151660084423170233448167305610109739888867033605693921607825857499212362037761794631882229647666556510526199774621660504072978457006363045937600675597892161507028576725666537473371", "533983", "21479046303025441690134760152162980519641919860599304374683185955082277310759445140592039521259837490165144566635792120163118223628217016481311925618574009723539639275268099480806216202277203760120564627093", "997", "47893", "997", "398646830977963183322447766593140434683576908048526864634254825288673604304004967", "552361", "7521638320338927987215995596096989333652394491481638955363298590352332156679339", "997", "54007", "997", "27944128401974460395330123754686275388009856688602196578125401", "558487", "473629294948719667717459724655699582847624689637325365730939", "997", "60121", "997", "77940803786893016647539322934964966025718379100488200464157090690974981385586170948362089960785846708669816939830504157041168608009049605052660003972843137251140280478249968574051330621847204291870411456652836799", "568697", "1277718094867098633566218408769917475831448837712921319084542470343852153862068376202657212471899126371636343275909904213789649311623764017256721376603985856576070171774589648754939846259790234292957564863161259", "997", "62159", "997", "557222273128694516674162426702913777225589943389658106186243857297684547349274454742677626685673955962922402597754341425208664507439159276967833017800342899319139904259010271667792380324047918033", "574823", "8316750345204395771256155622431548913814775274472509047555878467129620109690663503622054129636924715864513471608273752615054694140882974283101985340303625362972237377000153308474513139164894299", "997", "68273", "997", "17440508702575850052896911458212242773207097595049949521684725971965638090857668453673550447629042635774807276483992681915852975891558766105215085808976020372544754224990747638780047860989301211703499", "580949", "245640967641913381026717062791721729200099966127464077770207408055854057617713640192585217572240037123588834880056234956561309519599419240918522335337690427782320482042123206180000674098440862136669", "997", "72349", "997", "1424380298289275705894559600755711170503199000303179135694877603277659422923208851946781214320169642370322910276576643316546509039955592318643318520069355214503644382280559886430362113741588407066504267684585657137741659", "582991", "19512058880675009669788487681585084527441082195933960762943528812022731820865874684202482387947529347538670003788721141322554918355556059159497513973552811157584169620281642279867974160843676809130195447734050097777283", "997", "74387", "997", "426450076438797242652822176973974841347834224968515749390409652341", "589117", "5398102233402496742440787050303479004402964873019186701144425979", "997", "80501", "997", "824106655669782210425565987496491762126702214637601168400484229048639977197249286980373617053059742599416312068799210836902298656937345312575927639796580262327402995651567079800656463080089983019", "599327", "9928995851443159161753807078270985085863882104067483956632340109019758761412642011811730325940478826498991711672279648637377092252257172440673826985500967015992807176524904575911523651567349193", "997", "84577", "997", "4944528468545255770865574380114221190998471661157926844550406264799390854466449317327746143102114005846689827694830766828943828956818930311295208977848091145573604349436839941159175394504050467760661318694531", "605453", "55556499646575907537815442473193496528072715293909290388206811964038099488387070981210630821372067481423481210054278278976896954570999216980845044694922372422175329768953257765833431398921915368097318187579", "997", "90691", "997", "514996339419582002586289324658434030355366668863920078962167376692296652132613308797333141596921224150313108804994586497792307478786701439693069492499380684727657941859765639397142855552266467039291", "611579", "5309240612573010335941127058334371446962542977978557515073890481363883011676425863890032387597126022168176379432933881420539252358625788038072881365972996749769669503708924117496318098476973887003", "997", "98843", "997", "301442113655254712905909901926689012451481130124254792162323448571207614502495384196126869113454266413263841134002419787734946904753889329810749588333759276172364193230338694508431109559638625045463746364341506749635448119", "613621", "2984575382725294187187226751749396162885951783408463288735875728427798163391043407882444248648062043695681595386162572155791553512414745839710391963700586892795685081488501925826050589699392327182809369943975314352826219", "997", "102919", "997", "2555239879563593045696761114418609456507282255603548227099728781334221193057686271515208071736549649604470137028762071704870151737556338573583097780176553033728339957624547890696818131074248336445137980275782255127376514077", "619747", "24808154170520320832007389460374849092303711219451924534948823119749720320948410403060272541131549996159904242997690016552137395510255714306632017283267505181828543277908231948512797389070372198496485245395944224537636059", "997", "104957", "997", "1012323941142663752943575066252780797696120427731616910828998531998548452296595951381134724249072458579321607158097952811936582645824027310322752213386853835911703333296464759502534737503217216491270980521356531", "625873", "9460971412548259373304439871521315866318882502164644026439238616808864040155102349356399292047406154946930908019607035625575538746018946825446282368101437718800965731742661303762006892553431929824962434779033", "997", "109033", "997", "14538361229487745257682170457856734814405959216469425962052011400576054111276050364279603615018009986387137829571146551766463482651444282213513369961768211142997430772394358145784688162016585046608655019700504896800057220809286471", "629957", "133379460820988488602588719796850778113816139600636935431669829363083065241064682241097280871724862260432457152028867447398747547260956717555168531759341386633003952040315212346648515247858578409253715777068852264220708447791619", "997", "111071", "997", "3375454873554339821014112396646130304474852067498624799546619899489477269929546975713496262833655453356344306236948923050310411808869829632508321207505306583328796000277316597491734113305075324587336522411370280436859", "631999", "29871282066852564787735507934921507119246478473439157518111680526455551061323424563836250113572172153595967311831406398675313378839556014446976293871728376843617663719268288473378177993850224111392358605410356464043", "997", "115147", "997", "39459694765875470141576638079098465499479668623064100064810566131731733407973558410719836295273087266359541647498772639126368333953423358659625851571582603515211711056260787965851889797806599055825412860621841289331451", "644251", "310706257999019449933674315583452484247871406480819685549689497100249869354122507171022333033646356428027886988179312119105262472074199674485242925760492941064659142175281795006707793683516527998625298115132608577413", "997", "129413", "997", "7553129670700810117236177443049339501407393353024497112491720588260921329", "654461", "57657478402296260436917385061445339705399949259728985591539851818785659", "997", "133489", "997", "25980185209260680155983489091150957266592864263389645865369284413013694711280605231725376148215553402565525344770150494341675231231995828510711703056761109302213135579423282202157355856501247492062574715366490096512678476350758824550709012111849700772341340219", "656503", "189636388388764088729806489716430345011626746448099604856710105204479523440004417749820263855587981040624272589563142294464782709722597288399355496764679629943161573572432716804068290923366770015055289893186059098632689608399699449275248263590143801257965987", "997", "139603", "997", "1061284478093134120490574326138962643383576170348591120451178777693851339358901234566104134284107020944540308065951031722956299232212106738300915810230160757429918716369835743989417390909386076858457295662168989239554402068894161149423576941499", "660587", "7635140130166432521514923209632824772543713455745259859360998400675189491790656363784921829382064898881584950114755623906160426131022350635258387123957991060646897240070760748125304970571122855096815076706251721147873396179094684528227172241", "997", "141641", "997", "27806982057853581864459841488908693336336627810182075117867298413541027939991858305143598359129694257228778010677915055505909918139828064754213739020059405463623859463575550295673176217514418739572901818140347404036512846794190316979114076091957059089918247219", "666713", "186624040656735448754764036838313378096218978591826007502465090023765288187864820839889921873353652733079047051529631245006106833153208488283313684698385271567945365527352686548142122265197441205187260524431861772057133199961008838786000510684275564361867431", "997", "151831", "997", "3285953693565530256115800482073279437127404312775462128879985648281136509133852277946366476820598526610405012654942447679756925982034824013822476121812295179872880312347210182423656346523480923472854342890714431110955178199116118028229426669", "672839", "21761282738844571232554970079955492961108637832950080323708514227027394100224187271167989912719195540466258361953261242912297523059833271614718384912664206489224372929451723062408320175652191546177843330402082325238113762908053761776353819", "997", "153869", "997", "622356281582461391123389336535578068400307622361011899125957703826390742157096885215871433085702703260992789059584333983894288210865658524955265536811354609574720641602347188123108545087591929076283949532906136151478757549983", "674881", "3964052748932875102696747366468650117199411607394980249209921680422870969153483345324021866787915307394858529041938433018434956757106105254492137177142386048246628290460810115433812389092942223415821334604497682493495271019", "997", "159983", "997", "10241536787881076649864784083320725924155487294468200096074282642623762885457", "687133", "62831514036080224845796221370065803215677836162381595681437316825912655739", "997", "166097", "997", "11405250480124509891101363855667497861474483259204554342932963047962397866264996748378991721576010916172344867162584304709430613352445633564921189986187763396984414357275984363672100783488186693142363961454827603244723320557", "691217", "68294913054637783779050082968068849469907085384458409239119539209355675845898184122029890548359346803427214773428648531194195289535602596197132874168789002377152181780095714752527549601725668821211760248232500618231876171", "997", "170173", "997", "1944807869360994770207438536559919056634540443061560281988106382931336667032429874652507850233703229371452968943082618826443877218595974482072630868786603739049970890829171640243310329078072773142632259951108763745080055495578703651", "697343", "11241663984745634509869586916531324026789251115962776196463042675903680156256820084696577168980943522378340860942674097262681371205757077931055669761772275948265727692654171330886186873283657648223307860989067998526474309222998287", "997", "176287", "997", "225073418047842319520715088364130442319988885603897716155330438594055372663041", "705511", "1257393396915320220786117812090114202904965841362557073493466137396957389179", "997", "182401", "997", "225329171368509161580472750897026209271177545132054535919092795048175517709558661017404496471571909222764775628194943731479366517164081876622381021735832173151443162628171041881190685097728786249713457178472422049206541511338483211278808636889900059219", "715721", "1244912548997288185527473761862023255641864890232345502315429806895997335411926303963560753986585133827429699603286981941874953133503214787968955921192442945588083771426359347409893287832755725136538437450123878724898019399660128239109439982817127399", "997", "184439", "997", "147948824613896094021559256468208240621247063714817440181805623939619560948705390107983487027464637347879398154756846108483531621445912903031841905046959331289859397842582645928423887704550435180423126450785960262310310693874091438507922975428859476159809606172410845400699", "723889", "774601175988984785453189824440880840948937506360300733936155099160311837427776911560122968730181347371096325417575110515620584405475983785507025680874132624554237685039699716902742867563091283667136787700450053729373354418188960411036245944653714534868113121321522750789", "997", "194629", "997", "3663574983339472396374498535089718440151822588170139197923643104403964824873940016494197681580897911686389150772108064161475879219326417780345224634357375369523896053565948898451794062203069501481019903036711514600073580767056801019", "734099", "18982253799686385473442997591138437513740013410207975118775352872559403237688808375617604567776673117546057776021285306536144451913608382281581474789416452691833658308631859577470435555456318660523419186718712510881210263041745083", "997", "196667", "997", "8455278772776224374271023592698437808269362247194077422320886658621746174281418149174663922086515928205781678321990770649841595335371231946470738240060062353185284927152119985585357359688807996283753901135009827258161244214785267280127016797383", "742267", "42920196816122966366857987780195115778017067244639986915334450043765209006504660655708953919220893036577571971177618125126099468707468182469394610355634834280128349884020913632412981521262984752709410665659948361716554539161346534416888410139", "997", "200743", "997", "7418664063326667174171516407096672529836721739118262523809114802763367797444381", "748393", "37279718911189282282268926668827500149933275070946042833211632174690290439419", "997", "202781", "997", "1216142943931601900840499346326153294372963200662871598602878771751067301282935383481935570679941736286303494921026416345368409318863091781019560429709350064711390142526964314902108955296323216588439774090112698978970772874445246117374500899", "754519", "5763710634746928440002366570266129357217835074231618950724543941948186262004433097070784695165600645906651634696807660404589617624943562943220665543646208837494740011976134193848857608039446524115828313223282933549624515992631498186609009", "997", "215009", "997", "138691792998900981393067649792787848641037326193951782941236989320550933465674492476050781517256816980352563136501783747517774908582709149868844034074488483067697567425768441388229379485083067254522425925225280069810787466572004302011", "758603", "621936291474892293242455828667210083592095633156734452651286947625788939307957365363456419359896040270639296576241182724294954747007664349187641408405777950976222275451876418781297665852390436118934645404597668474487836172968629157", "997", "227237", "997", "2028493490644134181545071400466908110867796623181315854487633734557528690094386218346576853932530189093546742060337625157893636505419736098290811151374445048600018545156783393583253452964962427130653747772754254546889532223197256645401908955067327736231726068875643791579593259", "766771", "8936094672441119742489301323642767008228178956745884821531426143425236520239586864962893629658723299971571550926597467655919103548104564309651150446583458363876733679104772658957063669449173687800236774329313896682332741071353553503973167202939769763135357131610765601672217", "997", "231313", "997", "14149311638818710272508768215683034141538149399907158174569462453878173117322097753573649385838904038871126756217699203940141028311501017698570123066261061120171424198367746633234728713058889449330070324521632921517787014310284981552853646663319503779299", "772897", "61787387069077337434536105745340760443398032314005057530871015082437437193546278399884931815890410650092256577369865519389262132364633265059258179328650921922145957198112430712815409227331394975240481766470012757719593948953209526431675312940259841831", "997", "233351", "997", "30093876104292118234789101271657244880699998710604456683832260298422030702485065967861524326546606571039352053995299041938053973700300262936244544083334881309585916203495310045228392711906230431409629365533390067925197505085591927635071892148491", "776981", "129158266542026258518408159964194184037339050260104964308292962654171805590064660806272636594620629060254729845473386446086068556653649197151264137696716228796506078126589313498834303484576096272144332040915837201395697446719278659377990953427", "997", "237427", "997", "3341433274322410860909358920965655465914609433427753011787584445887163322575233606213353128070580943023650547154816689267633028226655069995528795004468493200031965955545943936872867057651796177238218640454146294226353627831975242231915884119383355513992675163415937324785211381", "785149", "13980892361181635401294388790651278100061127336517795028399934920029972060984241030181393841299501853655441619894630499027753256178473096215601652738361896234443372198937003919970155052936385678820998495624043072076793421891109800133539264097838307589927511143999737760607579", "997", "243541", "997", "4118476469007064308947375538559785902711241611772556924176911678360484298072250699", "789233", "17089113979282424518453840408961767231166977642209779768368928125977113270009339", "997", "245579", "997", "931152388751175201699068624778090289867417543528220592117152773927749269913068388840365617398521258477932276771590394237676949552026467097846301304616397612088831084369673137110207936130665169120295304026669889420982367047795994272488560887275037507805158319176442153344967337522071321821019", "803527", "3709770473112251799597882967243387609033536029992910725566345712859558844275172863905839113141518958079411461241395992978792627697316601983451399619985647856927613881950888992470947952711813422790021131580358125183196681465322686344575939789940388477311387725802558379860427639530164628769", "997", "255769", "997", "2891247412588934131535766310701430184913777993027195144625265514460073835877768281374678458180366942013537958473137407582426122601856395302375298667160312868283179007377451488414685852848881981660077537670642989489234007367886409503052947081175934785149006331", "813737", "11249989932252661990411542064986109668925206198549397449903756865603400139602211211574624350896369424177190499895476294095043278606445117908075092090117948903825599250495920188383991645326389033696799757473319025249937771859480192618883062572669006946105083", "997", "261883", "997", "13899422530678692053654718384395654516426347025655826879567494777451559730600568674546707009339019292739476335367327016017867581118288482087649526209799357787918091759795268071323583783939990378975910915464265365184472642331075137172120703394599859293071808179295648708579999684135452477", "825989", "52849515325774494500588282830401728199339722531010748591511386986507831675287333363295463913836575257564548803678049490562234148738739475618439263155130637976874873611388851982218949748821256193824756332563746635682405484148574666053690887431938628490767331480211592047832698418765979", "997", "267997", "997", "1355699963191169974672204718471466004562253812733568890856366430755543607435448494756142541415471836728113575979434855183498286076476238071951618737682287160425884197494461103908314040707400572892652361779504788601631816417329651376067771467758410992920761631", "828031", "5039776814837063102870649511046342024394995586370144575674224649648860994183823400580455544295434337279232624458865632652409985414409806958927950697703669741360164302953387003376632121588849713355584988027898842385248388168511715152668295419176249044315099", "997", "274111", "997", "197770168183920893490702355213946062548862275593686785036823325489830493680361725109", "838241", "729779218390852005500746698206443035235654153482239059176469835755832080001334779", "997", "276149", "997", "235066939145603730138455797181895332556660643522557763976711397934654296027286248141866352067440614645980785211857345634122543197521067658886043737467928065242170439144153675267262025034856560884161819395341422586089798939047835618577282359011", "840283", "848617108828894332629804321956300839554731565063385429518813710955430671578650715313596938871626767675020885241362258606940589160725876024859363673169415397986174870556511463058707671605980364202750250524698276484078696530858612341434232343", "997", "282263", "997", "653856944817121418564574769158558214241652061694177451283815899696349734329343253379", "844367", "2326893042053812877454002737219068378084171038057571001010020995360675211136452859", "997", "286339", "997", "153750924705191331202642487855432301214999247349347135664932925672884382532572106143629862520851000964392448797347295129760339890447171549018979033727220079019470962832403597856104509630053226079444303822073464068832801004488749074363606794131843019", "846409", "543289486590782089055273808676439226908124548937622387508596910504891811069159385666536616681452300227535154760944505758870458976845129148476957716350600985934526370432521547194715581731636841270121214918987505543578802136002646905878469237214993", "997", "288377", "997", "9247489933034770345008842513605671240539329503796940360077790769034919055860192075961498268156080222753546521642413997960863602513249430650096399945058850657850730509948718278723816846696059730196008820021372108447626975263432296338773003684247622175988091632568335607339591109011826268182783373997524131", "856619", "31561399088855871484671817452579082732216141651184096792074371225375150361297583877001700573911536596428486421987761085190660759430885428839919453737402220675258465904261837128750228145720340376095593242393761462278590359260861079654515370935998710498252872466103534496039560099016471905060694109206567", "997", "298567", "997", "1717407504335870232912715929360339133649245648531977431437710884144242413898244908199676348333630782469611821101441951565524681310844200869852683280497944626558680801715390769378642397671865997499800973267974091300091032739882947247896538134151189417", "870913", "5594161251908372094178227782932700761072461395869633327158667375062678872632719570682984847992282679054110166454208311288354010784508797621669978112371155135370295771059904786249649503817153086318569945498286942345573396546849991035493609557495731", "997", "312833", "997", "186094640094728709905582884915209478720162295193640169865982338425202130855964448777365803096561599373266189003786443004976861963671620462507490499001087000062228617512324435299563374854468112230954656065794720439794736047301775255274615166365555906615082699", "874997", "598375048536105176545282588151798966945859470076013407929203660531196562237827809573523482625599997984778742777448369790922385735278522387483892279746260450360863721904580177812100883776424798170272205999339937105449312049201849695416769023683459506800909", "997", "316909", "997", "99031418963697124674853988324325827852540883371919853044916122582908820976031775150461062479829273919254632432784471230762209126862746456311631012017430778342731130579275835965526802369447102695762351319328603240840216102895901102277717945225511617318692885468391820057855359602494115072883", "877039", "316394309788169727395699643208708715183836688089200808450211254258494635706171805592527356165588734566308729817202783484863287945248391234222463297180290026654093068943373277845133553895997133213298247026608956041023054641839939623890472668452113793350456503093903578459601787867393338891", "997", "318947", "997", "42242760426214852365008492021688249001199142271915160025206075397415289834494590552596465606988123248212551380300285932126774225020692469707080058167842164648746139668051737622910245137506042977114350839236678790426338968454103079402971043834421080175047132836133633496964302426327", "881123", "133257919325598903359648239816051258678861647545473690931249449203202807048878834550777494028353701098462307193376296315857331940128367412325173685072057301731060377501740497233155347436927580369445901701062078203237662361053952931870571116196911924842419977401052471599256474531", "997", "323023", "997", "107307369572290541384475737454740253494018594946523953948261811827034605510928874078489851241855815524617369122814813937716249011703046172889308428655342212025001891566435646387451504158097825535109820621633632481094109611807638752054352547330203174484844484659", "895417", "324191448858883810829231835210695629891294848781039135795352905821856814232413516853443659340954125452016220914848380476484135987018266383351384980831849583157105412587418871261182792018422433640815168041189221997263171032651476592309222197372215028655119289", "997", "337289", "997", "55064612321770155133157362474829199989035428581948598172981940137568403555187622908028564874669701059511946421406182521933816203496055859680958661046865172951343822363678488724509509061180572829585917059572354958143854719027588481590624599078397653942081134186048842079801519289417050168490082593323", "899501", "163396475732255653214116802595932344181114031400440944133477567173793482359607189638066958085073296912498357333549503032444558467347346764631924810228086566621198285945633497698841273178577367446842483856297789193305206881387502912731823736137678498344454404112904575904455546852869585069703509179", "997", "343403", "997", "191910400529505153557224617029107865694106741205348818904526992376067891765008424641623636027152487218384283069648741467693297373871543851103342180022015891721139900840652679154541010152081242584577176398651308152433498225132989871250359174352180752175700889727556239511651", "901543", "553055909306931278262895149939792120155927208084578728831489891573682685201753385134362063478825611580358164465846517197963393008275342510384271412167192771530662538445684954335853055193317701972844888756920196404707487680498529888329565343954411389555333976160104436633", "997", "353593", "997", "195306582131271451009334326954770025184144851578630324452422872021506820732014956379715234978255404349682123138757786675633123282560391857045894094521929176524667838378563095623212129113112952618142325576737520038648102942539205523023679173996788382216711019", "905627", "559617713843184673379181452592464255541962325440201502729005363958472265707779244641017865267207462320006083492142655231040467858339231682079925772269138041617959422288146405797169424392873789736797494489219255125066197543092279435597934595979336338729831", "997", "355631", "997", "1215456615647736981075511688343015609651098104001912463828764256884376773285956483375387", "926047", "3443219874356195413811647842331488979181581031166890832376102710720614088628771907579", "997", "359707", "997", "152371024479309333613791270766813059934644240963510757940065726092042020167346294014239858246488261844181541553866797374541435361748272964733304606225836878830766560242205779764084434055945144673618075979996122754129399688334667194097420399639375481262924139926860301", "930131", "424431823062142990567663706871345570848591200455461721281520128390089192666702768841893755561248640234488973687651246168639095715176247812627589432383946737690157549421186016055945498763078397419548958161549088451613926708453111961274151531028901062013716267205739", "997", "365821", "997", "8805855872789019240710264044493313902829667579523595450483405927948456557973767381593768592699990307656047373848464298739897608488173415985344555327733960422040018571984480783688585363881034183770028635322562755061525965264076157536693656742309428857200200534740552445744340920479346348313632819317", "938299", "23994157691523213189946223554477694558118985230309524388238163291412688168865851176004819053678447704784870228469929969318522093973224566717560096260855477989209859869167522571358543225833880609727598461369380803982359578376229312089083533357791359283924252138257636091946433025829281603034421851", "997", "373973", "997", "1095376316278855322873293779067055170364191817021514439349116525031244403693815779672168678363649208457797649035029957775057822028226826207868697627085868397348111959279609148252080232892263125008811953482298559446432650497666173228960391046465035759461531583942148845722771586537518927520699", "948509", "2936665727289156361590599943879504478188181815071084287799240013488590894621490025930747126980292784069162597949141977949216681040822590369621173262964794630960085681714769834455979176654860924956600411480693188864430698385164003294799975995884814368529575292070104144028878248089863076463", "997", "380087", "997", "15369226844695333062849381477909582790193081087319522766401784914789199098254937701754942361481513813591507178592892064416009512989526432006888411812015707106697003660843933262218400518290304215112593252662042221838402637726323711885254485048250408355850463886893101619739", "956677", "40552049722151274572161956406093885989955359069444651098685448323982055668218832986160797787550168373592367225838765341467043569893209583131631693435397644080994732614363940005853299520554892388159876656100375255510297197167081033998032942079816380886148981231907919841", "997", "386201", "997", "17936335753803465319644606369717202510207061261553117383696431100566559448104053392344197", "960761", "46831163848050823288889311670279902115423136453141298651948906267797805347530165515259", "997", "390277", "997", "25893139746956375074671910466488819057973682757474498176744179853848279269471981476034178206434626829662341282305098421017615074690674938772214414369410376488767243876576772000943323646306806499600311513657727872637967224802501913807127372752863262895742486671", "966887", "66563341251815874227948355954984110688878361844407450325820513763106116373963962663326936263328089536407046998213620619582558032623843030262761990666864721050815536957780904886743762586906957582520081011973593502925365616458873814414209184454661344204993539", "997", "396391", "997", "73974572111317406360276225631919880970967230930546543997873687812509688512760842513788622380060283819337381239289168279398371925148558197982252822440463431991798888852483797550848552471579198228007110388157478970670518327902466795935796129943875075370218141183995374789284599233523734628628605149143767", "973013", "186333934789212610479285203103072748037700833578202881606734730006321633533402625979316429168917591484477030829443748814605470844202917375270158242923081692674556395094417626072666379021610071103292469491580551563401809390182536009913844156029912028640347962680089105262681610160009407125009080980211", "997", "404543", "997", "1307141793874862084461913041302240551365792174026016528279865697359005336719217669177196976468676813204191353984957820150881355004620906305582162121381248966040062853839635204011545101328676009151433346953408816476579132602933740590965014866256568699705065819", "987307", "3259705221633072529830207085541747010887262279366624758802657599399015802292313389469319143313408511731150508690667880675514601009029691535117611275264960015062500882393105246911583793837097279679384905120720240589972899259186385513628466000639822193778219", "997", "408619", "997", "7093242912463185348072070110212638351742462073193796871217834643050267179901187029507018490754437695656607535423037831588564687811978689937562105842348187968983989171429748478114974959055204956755248726089665726321535007236838047456328883300447788907493192538880498815296925888779", "991391", "17342892206511455618758117628881756361228513626390701396620622599144907530320750683391243253678331774221534316437745309507493124234666723563721530176890435131990193573177869139645415547812237058081292728825588572913288526251437768841879910270043493661352548994817845514173412931", "997", "416771", "997", "1185579641965561589160299697265721932824027132750467864460376877428924099444308658448594136390967744065181760700818974092571770178341715224937792646992702816801853703682587972668759794434610387225171807457005618044826070319744092967744160173564727037441446431202779572868249757967428377671066761", "997517", "2829545684882008566015035077006496259723215113962930464105911401978339139485223528516931113104934950036233319095033351056257208062868055429445805840078049682104662777285412822598472063089762260680600972451087393901732864724926236199866730724498155220623977162775130245508949303024888729525219", "997", "426961", "997", "169052738021865017945085217436498678340551974017269410534135929153837234291820715450799841864356228195340732263779", "1003643", "401550446607755387042957761131825839288722028544582922883933323405789155087460131712113638632675126354728580199", "997", "428999", "997", "89600456898162554710940038315160351182309734414129170687610033541862560707475499371198298316876962891405560250165152771675263407396177488042619118232855720276625778667788670057647578107276749358158513983871052535363437572582097937450349496907401800441822855338949217171751568948262972788043043591458773382280560737161315249005363622939", "1011811", "207889691179031449445336515812437009703734882631390187210232096384831927395534801325286074981153046151753040023585041233585297928993451248358745053904537634052496006189764895725400413241941413824033675136591769223581061653322733033527493032267753597312814049510323009679237978998289960065065066337491353555175314935409084104420797269", "997", "439189", "997", "433", "1013", "1019"
};

__int64 length(__int64 a1)
{
int i;

for ( i = 0; *(_QWORD *)(16LL * i + a1); ++i )
;
return i;
}

int factor_print(__int64 a1)
{
char v2;
char v3;
char v4;
int c;
unsigned __int64 i;

__gmpz_init_set(&v4, a1);
__gmpz_init_set_ui(&v3, 2LL);
__gmpz_init(&v2;;
__gmpz_sqrt(&v2, &v4;;
for ( i = 0LL; i <= 0xAB; ++i )
{
c = 0;
while ( __gmpz_divisible_ui_p(&v4, primes[i]) )
{
__gmpz_tdiv_q_ui(&v4, &v4, primes[i]);
++c;
}
if ( !c )
break;
putchar(c);
}
return putchar(10);
}

int __cdecl main(int argc, const char **argv, const char **envp)
{
double v3;
unsigned __int64 v4;
char v6;
char v7;
char *lineptr;
size_t size;
char v10;
char v11;
int v12;
int j;
int v14;
int i;

__gmpz_init(&v11);
__gmpz_init(&v10);
__gmpz_set_ui(&v11, 1019LL);
size = 172LL;
lineptr = (char *)malloc(0xACuLL);
v12 = getline(&lineptr, &size, _bss_start);
lineptr[v12 - 1] = 0;
for ( i = 0; ; ++i )
{
v3 = (double)i;
if ( fmin((double)v12, 84.0) <= v3 )
break;
__gmpz_set_ui(&v10, primes[i]);//v10=primes[i];
__gmpz_pow_ui(&v10, &v10, lineptr[i]);//v10=pow(v10,lineptr[i])
__gmpz_mul(&v11, &v11, &v10);//v11*=v10
}
__gmpz_init(&v7;;
__gmpz_init(&v6;;
do
{
v14 = 0;
for ( j = 0; ; ++j )
{
v4 = j;
if ( v4 >= length((__int64)program) )
break;
__gmp_sscanf(program[2 * j], "%Zi", &v7;;
__gmp_sscanf(off_60E2E8[2 * j], "%Zi", &v6;;
__gmpz_set(&v10, &v11);
__gmpz_mul(&v10, &v10, &v7;;
if ( __gmpz_divisible_p(&v10, &v6) )//if v10%v6 == 0
{
__gmpz_tdiv_q(&v11, &v10, &v6;;//v11=v10/v6
v14 = 1;
break;
}
}
}
while ( v14 );
factor_print((__int64)&v11);
return 0;
}
```
Seeing the program we can say the code is pretty small. All the logic is written in the array as a vm.
I was able to figure out this much during the CTF. I wrote a [py](05223a3cae8b71d81592d5977fb1c3622bcbf793.py) for the same to debug the states when I enter a password.

After the CTF got over I went on the IRC and asked for a writeup on this.
[crowell](https://twitter.com/jeffreycrowell) told me about [FRACTRAN](https://en.wikipedia.org/wiki/FRACTRAN).
However this solution did not need that logic. As I was playing around with the program I notice that the program array has our "program". More importantly every number in that array can be factorized to primes < 1024.

As every password was fed to the program as

```python
for i,j in enumerate(password):
v11*=pow(primes[i],ord(j))
```

We also see that the program iterates in program array alternately and tries to divide the password.
I thought of factorizing the program array with the possible divisors.

```python
primes=[2, 3, 5, 7, 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 ,127,131,137,139,149,151,157,163,167,173 ,179,181,191,193,197,199,211,223,227,229 ,233,239,241,251,257,263,269,271,277,281 ,283,293,307,311,313,317,331,337,347,349 ,353,359,367,373,379,383,389,397,401,409 ,419,421,431,433,439,443,449,457,461,463 ,467,479,487,491,499,503,509,521,523,541 ,547,557,563,569,571,577,587,593,599,601 ,607,613,617,619,631,641,643,647,653,659 ,661,673,677,683,691,701,709,719,727,733 ,739,743,751,757,761,769,773,787,797,809 ,811,821,823,827,829,839,853,857,859,863 ,877,881,883,887,907,911,919,929,937,941 ,947,953,967,971,977,983,991,997,1009,1013,1019,1021]
program=[1009,1994,1009,437683,1009,2991,1009,441671,1009,4985,1009,447653,1009,6979,1009,455629,1009,10967,1009,459617,1009,12961,1009,461611,1009,16949,1009,465599,1009,18943,1009,477563,1009,22931,1009,485539,1009,28913,1009,489527,1009,30907,1009,497503,1009,36889,1009,501491,1009,40877,1009,507473,1009,42871,1009,519437,1009,46859,1009,521431,1009,52841,1009,539377,1009,58823,1009,545359,1009,60817,1009,555329,1009,66799,1009,561311,1009,70787,1009,567293,1009,72781,1009,569287,1009,78763,1009,575269,1009,82751,1009,585239,1009,88733,1009,591221,1009,96709,1009,597203,1009,100697,1009,599197,1009,102691,1009,605179,1009,106679,1009,611161,1009,108673,1009,615149,1009,112661,1009,617143,1009,126619,1009,629107,1009,130607,1009,639077,1009,136589,1009,641071,1009,138583,1009,645059,1009,148553,1009,651041,1009,150547,1009,657023,1009,156529,1009,659017,1009,162511,1009,670981,1009,166499,1009,674969,1009,172481,1009,680951,1009,178463,1009,688927,1009,180457,1009,698897,1009,190427,1009,706873,1009,192421,1009,716843,1009,196409,1009,724819,1009,198403,1009,730801,1009,210367,1009,736783,1009,222331,1009,740771,1009,226319,1009,748747,1009,228313,1009,754729,1009,232301,1009,758717,1009,238283,1009,766693,1009,240277,1009,770681,1009,250247,1009,784639,1009,256229,1009,794609,1009,262211,1009,806573,1009,268193,1009,808567,1009,270187,1009,818537,1009,276169,1009,820531,1009,280157,1009,824519,1009,282151,1009,826513,1009,292121,1009,836483,1009,306079,1009,850441,1009,310067,1009,854429,1009,312061,1009,856423,1009,316049,1009,860411,1009,330007,1009,874369,1009,335989,1009,878357,1009,345959,1009,880351,1009,347953,1009,884339,1009,351941,1009,904279,1009,357923,1009,908267,1009,365899,1009,916243,1009,371881,1009,926213,1009,377863,1009,934189,1009,381851,1009,938177,1009,387833,1009,944159,1009,395809,1009,950141,1009,399797,1009,964099,1009,407773,1009,968087,1009,417743,1009,974069,1009,419737,1009,980051,1009,429707,1009,988027,1009,431701,997,1009,628342186020279030208477196652234251466546172127229920271442149116418270266805114129323801879492482137898525457610034761318243685701612999753301446499402184019047334363868952491996606714667813682795710496729144356627735845123676166105603998123636223487640503561426022924983170637012661801780667366986496506030776535567526896671098662632123365168743664803047333533266651378724651134747558720373671125128918192606546275484822315302537833017347515852873969123863196991591128905797797953641849823901200591253758989661116185809449387114754110693862270878790685521494032855174559448217678703819332109924602615048084195117590112536399286371826740412069584415578436175604905487388386875110557418165843986191168930994241095051887359640391104091658653518621901534663248053930033780121015835031607604047633957687509170016778799461147891167654749638057549827992932889122995155539900942798016011513799665913318026811781018347609393399492693089473128154346668249800406988857586278307546023464942900979079319193897231953014331315745983540688409217523781284767071786748835334904114251151768066947066974655638700742353772603987770915012114230380632982060506677995390598274839813186589487880327769882355406369328704667144104785532210079866539787033200765829359931127219031553817186725838729517291842565585345287913859037622248318083084610913049915914358110409209100852502593148685289707303219729372851454213282755549475037954209582986949880668930047153621586488494270546617243702586105425080170041634818438278320529852112847863734593944644022898353545446882029646417103689943919192691294079623058308937404741503543204905870498980563398747865075941095954326295793595346961572874520213826034401809759600671385592618044358788220764179037648551723688883462655964529249402109637617708231973919514209153002131026182417912198411370401495384651131774509722038523496382808921942374492604612687129063485332311030348703446367201242825533393540915424705051574412572120162877997562692412185247999611773833311632900771473429755915441182540269617877214830627528032509574263455045777758312790203647404347503161728097958892560903112974915627570659454527665768438056409725068410760146580760573561825743041360562327507023011036093343294488329397226160195885463366678787014633928020875226483619664858890687676379225725094561398719056931046049652997474332655225198880371911150572119222293804816869964938939569929273415161422698066449231388944785154171990521448471715053090799940542872248125377623217571815993265916187470537162268436325773823823025764997980088398890569841898462161853267169228882950197460075182837289919940982931539635781819167833327053366074466169096663110752528063831392419664656628996209161385538062512860770349218644155662924022242464260618852724359227862586009757511987837154780681347585339557128064674324666633148721900366457274096873746373036267539915146015258255209166409983804123119669569892997296082665906047894529706757974988307364081640652759420620606279591460036311764255114156837496511088449627305129870293650489346534475746640218520980739890581556540008279019229663760636485837245208764597357678419738833265275277731038701789683747837440024384633103957164283508891650623445519394459252271959449686279179444136374415706603701561041515600084286014592770962766546924881353153028839585503598573550964862568899783340905087121767189848319028823764126564635152182745746588976064614585513882178320384662630419491983556919743035918979272357120571425297548004511661675273618557126654548778343459193970691487722304790664607581194061709590959173879314951330697843870052828316024354166567082187518547658698577696795531130565515421083180252264454883596870044949725930149179966847413679961101162747165984569728196830920577134702664306366364197595517421138209600525104047202300339400088872288316077221656240102231143786257343020802118922926269205047219736723123445530507690137692235730009368553776231094320766355040830168009092017813288396850664476916182018546812944453888512931302160127019704913501725813307841245312731953948196722380163601568492780144962109057602369074555334991621987390374358769710617552391326453785020526405147640026146312997938788804138998232289707025657098750218408744926601492274136339769211112547916354899730071425547372588105403900685731200370521951579349841013973635462586811702994385448941952099615457769200940648360138128946530932948358590141678294540263461985603817191898095061752838756758169435695558894946752558724707225186802024978616855725317670898178008742128975014258782925817349723286317727283132139495271815132726481668557882676887050885378442098538933512778731774361164801103687075162670233525972446022073437141634190995911089958638936702125877258733854190658955211486896795807799247056213685696237168010636560453178295430632262922179196184338010387026042081248735157060332183087380384908870579342268028791502144475517809808520966859616554102946100611417937595977703395161367239525150406899496101767146677522362467244175944639777276553647414851795784699778438111349113652477278343467027323819397269455041625832813112347020033822455376729028165116279358528229084987521170918228041096904599804373545811652965962629163714889427307592378384787948608392935161760512373031943294253135653945376467534645062128214176859177671917924470733170543663095164294078188577644263829357684653992808048115290898706559292435665031983147770618047696164278180114571883909560849919923071788171847093498306550580036114960340160679659003480666374351890273587413582104233093778316851445659944947034432138454639433320133679779403332875832288448336528056715331939264128997610951123085318980941191657450923186786281447594211168439296167068599875424211947381124503574287428653464197183586766917064698969607222676938892700337244499023740021533322407975632591913985176741704511237708175586215484912007730703539347900914569981861379239832893109915816827892646998809604355655684309972455745534857625387871413240766757912260561276872396077870424036155192914575494839379065148798577492895218102356645374808828351190560242930341412752377938339484272418298446253783645567893675139638014454360329933950740656010948440208956227962611495754650589391649847173952559561706238119700416870351183225680846641395695009002342404433610812356666485300887852999615689594544734258696785715335953720841080346734273745462225722854716944440612200907986986761974645226700321349237318729650027840661849263165071729001132412715683532938282372956492101123225224688540919293418074389951077117059370386174729181602053802620109858124680047124580359410149534093848987322604588465223269320290130009628419324527856018953957600035078765304742008540572117322791116024555796432461153651126300748828389259598990206877366444955852954604969428779178082528034059004222296475937635225715400197410351141529356047922229074568209997829979346838932511651507196184691420815697818582222639999405831514378102612043068259534775279462337493896484375000000000000000000000000000000000000000000000000000000000000000000000000000000,997,5020973558043690795472466436617612912981186347488363636494918897580345094619354831599150783154458643768824774086684855736649234567349871237720799314877192413924062850078649636850002055053944829186672671708163716322615209049354719596052941417213532076312584086034682854165737646092676148538845676199745010081171006469722614059402250242308785689918241284131648855341488804135227553569275395839797208481228297968911162075439845594462320763237357071166784713446778736264921216635219120279353441051381445681864657026276821922514536569544725327622938331970575312038054498527495497627987060787647164378259819498672242544076388147523885345280342831806880870923391335094231290063505894883622740743763068210341558532266730092057471805710970239830698232092553019009302257534520260356188869212033343552453220921330349478151838282759011653076078016714211215874482198987741235273840751410610227050746299055028652883630584960936757395646616847713407087225242767250411952408673845861387774237778205037416623206011306490376976238654472840823151891585075016585390922891098308045393593571415253634799881795632166478595261694471140226795538975637348108530604584641278570409344858021708185167591243455235623668321570654443319286878417340676933354064642723586253821998813504508098460362918587904912942418728303547539706696690550986778207008561820335924406226344605013700816659534219628975931010285852931303562594784807047348570737396800467230532753148948447635460563997386651374238754668022458990241654392066026389403056595070158613582087349737094737658808886315648062674551872063472621765109045797432205715733767132011793304312274933554077784748964538523889920306652843830639205498914392896052991230020283366189067754757119427529149351327101078032307908260603623126125800088927147739506163527183895257938715531016954102699245294031066253590763425350011991169491433278653398617395440744762010472263802586218941241055055743015914720823242262689467262506542601425806024500357983702028225857710867057862345336237222517523041907324188469202303664776657176177623265573649232807583121306909916426816016755317491385615404780845499430052098612881460431944822161954276179349694442740819075713633944412726802575579188952121635648787756123395044724581329422707259129800369169535652642639801159987649031332406466937818074557103914266685904770137348134689897321542175254693720185576746443281607586987415388428553993232704096407666570219410589863873312494539460705640975599199448114612634267109102407317730904132567388335904394477797328315856196208327128937370947369504646584356343462801435206697336876183024095674551448335131879630403438713907124638478413853269148185567784954639444384365569717712309310955147830166043443238005822635747057545664360288684594697328877448799025973804079099439380682972847878899045536018223183365782765974974091131423937943531681735723827404656800066615668567805386492162335823765656414065284523264752292185725090814264699334921326855584899083371098784162003309739906310772506255393733874274017314112532904577039191591007997878380622798755534627692925758417448816637818373973221551606967096451086316437822279771077272376148121571163290736638931514234910318028624294165025145259063674698090046911948075952284431571943853982442651363186672689212765267770285908709835564485153350230618682629074091170797310328555429502555362409867954701387470139759267436167728204441560324447484705204937156843869157813675957725786241495777896024839838398414785265343398641920748711625568412042688914128968190201059965530908706732754193849067931364670270274047648481440681370096814642988815043774848838838626624938922121096710544680023288597319646570406408354982897201465676769575294628096694930977248824011077321485418818924406431852258175057513393216350344049082542468361410424350720060469598506634455467477484979788747749796354609315723688211379376475460277770530264522516753753687913348610617627180044792600195906279194933087464933773782907713330404447333076666728339988449815215434318007623282986066831788891581783579614726180929544276009541965962239461776447541627074351182275490323828208628197483439346482508248446963369489796326385731064053724062808612872776418445167164620078205714184802118485145759294486622205254314132962840493288591203480571662819511051274785273705020148845879775227997407048971388002158100936213131756838746879763532259763345808459116288029766085022119913164248480557500068314593231088987160279569530688677315004982622289441794353406429725797216878712063025668632142903490923190360349140006080712281827399665057312208935502000825739775748382409547767113303970336836210669133926895235962501629552040586816345650814016614025782130788916609032745001899785992601494105680942665185307812466814213377653431289952318114685582720572586088812989364579521550555538171289271181678410758350157911033362222192696775165760690677062098520936755788225598782659548261103482659701827359313630846363889110910616705120073617014817614569968408898086698115057255739332773912661929818195363021921324903304920137570439912113419361155599656792846430129297557180197243737754764342250277820536833873850512952381832218723730563316514909646802035262898179819524477957536959221311168489498330910004725990255589480473575235173541252809932701389183846177964235287033830925857819001160586184156930429524672516539501165080375924833291345560537459192125694725922302068041992414208055805065909773572571976130403681164189313519334650691350894602614796418772828939871059035015115580766571764509536576557130464695399374994550899074089674240089589432866719236464202233403294885582612550745275632442296172192623564576641486142828317213702576891904379598321939228709403256536312047969623685194330246456663079749586499084220375579316652507872292946875012466482824470432774707250524489619450216896375750616444251664515756466570884810083576309586519141251515118124071845062312157097256288192961806792066900270500521144047770243562264487965415262662776051613168034656779642758114200039168472440692230333077279334828068865916779206390832407497613723856853959754467657674563538356200113237531415811715639082774172579453150559544048837197565500009080784265163136751719074454322189938394735894637025740187989314178929192969601790353384766140549815636197188798439691133630864251539048445431466504628211935886080852752935630094058548912025946009818396075472885206608300233436748206662616807944144796532094594620433469104447555629020079624892194386879122958004893129494842096402682811580537753137281234266545777016470955138841847355634423380012680312487848379430425081882125872830213363022475922799999654579438370854572957242484172090786677950121432476319475502042779427036319762004097420400844853692174042251171285933661004386621015926998839941599937383368984020896260270592470934269224540700618758089646022331731630333468362387499863220719689333769720594951447656934220607389756444636956576624383813057790571838503297531863499031792359610404317936111291681774481991887238261842808901836334223213707711107364485905291532705821130807123125454420222217016446133202332841807820589616482431348754917145101606467632094604680353363557871712551081392926909985237301152861238448196740016300218475973366025567832749173016062387042861194087419952458165039784986962997512974528829545248332349853718708838814455644705761832485931700173130071897488979237327246760914209146081519385108482784142154660288373455889906583829801152124158506717738674619195960806284400917112864093439783694796630478012378864676928266821333294750308467294460965175361532830951966724506606586746876954737693583126883851147396217944080036427834332965580301642572700340135310646747719129141401437460780643498914539005330191345728255970110381137385266964222518724087095866095862614718716057244839384375250846048030470719467935727917893539564429681478585454577297831321858756129328359401791440618517519405327157366260531819490852031046823010869408062657846696435219976461406268554894567770971764444584971135801033696477178443244408796389792415991584094216896934420766505635365939320304110028135204359699782309572808211604994257856468898963160670508388545426450891965355149110111299200922903858711721574257678665591805489566917051248264400361657973441314647767689458266932904273127096255063678875054002411113587425151644025362144946685722667666911552246977486100064975984657109331523076430943145383842843621837003905509584456012817099690437316894531250000000000000000000000000000000000000000000000000000000000000000000,36245651685809845304492628113575794772175397649419099113249877307900325591212664159525112257976186262177576925165788428184727502868295212091525088936946409650133956767734324927766246011976989507374907377126249628035718622112298251507273187,997,1013,1019,1021,997,76993463136706695564099584,448219,38496731568353347782049792,997,2038,997,2550715459588113191740567853821480131,452303,850238486529371063913522617940493377,997,3057,997,823141644718296094427700641815714988069885293953120708465576171875,458429,164628328943659218885540128363142997613977058790624141693115234375,997,5095,997,631438627444550736415080642521598404068584545931170399811149426440245178848956151040482280551968904085414619,466597,90205518206364390916440091788799772009797792275881485687307060920035025549850878720068897221709843440773517,997,7133,997,5073109956636842437922137917951595815016016809,470681,461191814239712948902012537995599619546910619,997,11209,997,438913347985031337591501224029935452069274872286254190655683643165087965696023,472723,33762565229617795199346248002302727082251913252788783896591049474237535822771,997,13247,997,1327219005770146547008686156809262336252304098712358296185474497662899493331386682893480798625505521976657389795886656059621285172228153327439765792208091,476807,78071706221773326294628597459368372720723770512491664481498499862523499607728628405498870507382677763332787635052156238801252068954597254555280340718123,997,17323,997,1610805172267842357617095639683797092166770721,489059,84779219593044334611426086299147215377198459,997,19361,997,2139592160996833904444519196048266285572585258708462244562014613878578784718122611950631792346783335492062143279594557904625677746393365345309654855942839875030957,497227,93025746130297126280196486784707229807503706900367923676609331038199077596440113563070947493338405890959223620851937300201116423756233275883028471997514777175259,997,23437,997,3630479287668869549750268730991097182488777024603224804293163934532866119354925487660843942045312796152147554107969601026775451735159578840647282686001322831,501311,125188940954098949991388576930727489051337138779421544975626342570098831701893982333132549725700441246625777727861020725061222473626192373815423540896597339,997,29551,997,133988324106187784280288196620247367470528903233752384280195808358192193530364030141478616319286544825474620032432885193545948964662015331837905297972451259,509479,4322204003425412396138328923233786047436416233346851105812768011554586888076259036821890849009243381466923226852673715920837063376194042962513074128143589,997,31589,997,5738931991401785278290295421593851207075494906229631943,513563,155106270037886088602440416799833816407445808276476539,997,37703,997,34852745127404453271355467204505037583904157560232023595243138842012775445916534653451148210482054873983793399474308536689963560530019612055489851743503416053101848051770672331302987621294126588219,519689,850066954326937884667206517183049697168394086834927404762027776634457937705281333011003614889806216438629107304251427724145452695854136879402191505939107708612240196384650544665926527348637233859,997,41779,997,12248497864385846776394397892390056468417217564487186546243452016977586379266627254227299054926635541031409485825456387995220131626108414165879951336719480556031331,531941,284848787543856901776613904474187359730632966615981082470777953883199683238758773354123233835503152117009522926173404371981863526188567771299533752016732105954217,997,43817,997,1009515176242195759436333727151660084423170233448167305610109739888867033605693921607825857499212362037761794631882229647666556510526199774621660504072978457006363045937600675597892161507028576725666537473371,533983,21479046303025441690134760152162980519641919860599304374683185955082277310759445140592039521259837490165144566635792120163118223628217016481311925618574009723539639275268099480806216202277203760120564627093,997,47893,997,398646830977963183322447766593140434683576908048526864634254825288673604304004967,552361,7521638320338927987215995596096989333652394491481638955363298590352332156679339,997,54007,997,27944128401974460395330123754686275388009856688602196578125401,558487,473629294948719667717459724655699582847624689637325365730939,997,60121,997,77940803786893016647539322934964966025718379100488200464157090690974981385586170948362089960785846708669816939830504157041168608009049605052660003972843137251140280478249968574051330621847204291870411456652836799,568697,1277718094867098633566218408769917475831448837712921319084542470343852153862068376202657212471899126371636343275909904213789649311623764017256721376603985856576070171774589648754939846259790234292957564863161259,997,62159,997,557222273128694516674162426702913777225589943389658106186243857297684547349274454742677626685673955962922402597754341425208664507439159276967833017800342899319139904259010271667792380324047918033,574823,8316750345204395771256155622431548913814775274472509047555878467129620109690663503622054129636924715864513471608273752615054694140882974283101985340303625362972237377000153308474513139164894299,997,68273,997,17440508702575850052896911458212242773207097595049949521684725971965638090857668453673550447629042635774807276483992681915852975891558766105215085808976020372544754224990747638780047860989301211703499,580949,245640967641913381026717062791721729200099966127464077770207408055854057617713640192585217572240037123588834880056234956561309519599419240918522335337690427782320482042123206180000674098440862136669,997,72349,997,1424380298289275705894559600755711170503199000303179135694877603277659422923208851946781214320169642370322910276576643316546509039955592318643318520069355214503644382280559886430362113741588407066504267684585657137741659,582991,19512058880675009669788487681585084527441082195933960762943528812022731820865874684202482387947529347538670003788721141322554918355556059159497513973552811157584169620281642279867974160843676809130195447734050097777283,997,74387,997,426450076438797242652822176973974841347834224968515749390409652341,589117,5398102233402496742440787050303479004402964873019186701144425979,997,80501,997,824106655669782210425565987496491762126702214637601168400484229048639977197249286980373617053059742599416312068799210836902298656937345312575927639796580262327402995651567079800656463080089983019,599327,9928995851443159161753807078270985085863882104067483956632340109019758761412642011811730325940478826498991711672279648637377092252257172440673826985500967015992807176524904575911523651567349193,997,84577,997,4944528468545255770865574380114221190998471661157926844550406264799390854466449317327746143102114005846689827694830766828943828956818930311295208977848091145573604349436839941159175394504050467760661318694531,605453,55556499646575907537815442473193496528072715293909290388206811964038099488387070981210630821372067481423481210054278278976896954570999216980845044694922372422175329768953257765833431398921915368097318187579,997,90691,997,514996339419582002586289324658434030355366668863920078962167376692296652132613308797333141596921224150313108804994586497792307478786701439693069492499380684727657941859765639397142855552266467039291,611579,5309240612573010335941127058334371446962542977978557515073890481363883011676425863890032387597126022168176379432933881420539252358625788038072881365972996749769669503708924117496318098476973887003,997,98843,997,301442113655254712905909901926689012451481130124254792162323448571207614502495384196126869113454266413263841134002419787734946904753889329810749588333759276172364193230338694508431109559638625045463746364341506749635448119,613621,2984575382725294187187226751749396162885951783408463288735875728427798163391043407882444248648062043695681595386162572155791553512414745839710391963700586892795685081488501925826050589699392327182809369943975314352826219,997,102919,997,2555239879563593045696761114418609456507282255603548227099728781334221193057686271515208071736549649604470137028762071704870151737556338573583097780176553033728339957624547890696818131074248336445137980275782255127376514077,619747,24808154170520320832007389460374849092303711219451924534948823119749720320948410403060272541131549996159904242997690016552137395510255714306632017283267505181828543277908231948512797389070372198496485245395944224537636059,997,104957,997,1012323941142663752943575066252780797696120427731616910828998531998548452296595951381134724249072458579321607158097952811936582645824027310322752213386853835911703333296464759502534737503217216491270980521356531,625873,9460971412548259373304439871521315866318882502164644026439238616808864040155102349356399292047406154946930908019607035625575538746018946825446282368101437718800965731742661303762006892553431929824962434779033,997,109033,997,14538361229487745257682170457856734814405959216469425962052011400576054111276050364279603615018009986387137829571146551766463482651444282213513369961768211142997430772394358145784688162016585046608655019700504896800057220809286471,629957,133379460820988488602588719796850778113816139600636935431669829363083065241064682241097280871724862260432457152028867447398747547260956717555168531759341386633003952040315212346648515247858578409253715777068852264220708447791619,997,111071,997,3375454873554339821014112396646130304474852067498624799546619899489477269929546975713496262833655453356344306236948923050310411808869829632508321207505306583328796000277316597491734113305075324587336522411370280436859,631999,29871282066852564787735507934921507119246478473439157518111680526455551061323424563836250113572172153595967311831406398675313378839556014446976293871728376843617663719268288473378177993850224111392358605410356464043,997,115147,997,39459694765875470141576638079098465499479668623064100064810566131731733407973558410719836295273087266359541647498772639126368333953423358659625851571582603515211711056260787965851889797806599055825412860621841289331451,644251,310706257999019449933674315583452484247871406480819685549689497100249869354122507171022333033646356428027886988179312119105262472074199674485242925760492941064659142175281795006707793683516527998625298115132608577413,997,129413,997,7553129670700810117236177443049339501407393353024497112491720588260921329,654461,57657478402296260436917385061445339705399949259728985591539851818785659,997,133489,997,25980185209260680155983489091150957266592864263389645865369284413013694711280605231725376148215553402565525344770150494341675231231995828510711703056761109302213135579423282202157355856501247492062574715366490096512678476350758824550709012111849700772341340219,656503,189636388388764088729806489716430345011626746448099604856710105204479523440004417749820263855587981040624272589563142294464782709722597288399355496764679629943161573572432716804068290923366770015055289893186059098632689608399699449275248263590143801257965987,997,139603,997,1061284478093134120490574326138962643383576170348591120451178777693851339358901234566104134284107020944540308065951031722956299232212106738300915810230160757429918716369835743989417390909386076858457295662168989239554402068894161149423576941499,660587,7635140130166432521514923209632824772543713455745259859360998400675189491790656363784921829382064898881584950114755623906160426131022350635258387123957991060646897240070760748125304970571122855096815076706251721147873396179094684528227172241,997,141641,997,27806982057853581864459841488908693336336627810182075117867298413541027939991858305143598359129694257228778010677915055505909918139828064754213739020059405463623859463575550295673176217514418739572901818140347404036512846794190316979114076091957059089918247219,666713,186624040656735448754764036838313378096218978591826007502465090023765288187864820839889921873353652733079047051529631245006106833153208488283313684698385271567945365527352686548142122265197441205187260524431861772057133199961008838786000510684275564361867431,997,151831,997,3285953693565530256115800482073279437127404312775462128879985648281136509133852277946366476820598526610405012654942447679756925982034824013822476121812295179872880312347210182423656346523480923472854342890714431110955178199116118028229426669,672839,21761282738844571232554970079955492961108637832950080323708514227027394100224187271167989912719195540466258361953261242912297523059833271614718384912664206489224372929451723062408320175652191546177843330402082325238113762908053761776353819,997,153869,997,622356281582461391123389336535578068400307622361011899125957703826390742157096885215871433085702703260992789059584333983894288210865658524955265536811354609574720641602347188123108545087591929076283949532906136151478757549983,674881,3964052748932875102696747366468650117199411607394980249209921680422870969153483345324021866787915307394858529041938433018434956757106105254492137177142386048246628290460810115433812389092942223415821334604497682493495271019,997,159983,997,10241536787881076649864784083320725924155487294468200096074282642623762885457,687133,62831514036080224845796221370065803215677836162381595681437316825912655739,997,166097,997,11405250480124509891101363855667497861474483259204554342932963047962397866264996748378991721576010916172344867162584304709430613352445633564921189986187763396984414357275984363672100783488186693142363961454827603244723320557,691217,68294913054637783779050082968068849469907085384458409239119539209355675845898184122029890548359346803427214773428648531194195289535602596197132874168789002377152181780095714752527549601725668821211760248232500618231876171,997,170173,997,1944807869360994770207438536559919056634540443061560281988106382931336667032429874652507850233703229371452968943082618826443877218595974482072630868786603739049970890829171640243310329078072773142632259951108763745080055495578703651,697343,11241663984745634509869586916531324026789251115962776196463042675903680156256820084696577168980943522378340860942674097262681371205757077931055669761772275948265727692654171330886186873283657648223307860989067998526474309222998287,997,176287,997,225073418047842319520715088364130442319988885603897716155330438594055372663041,705511,1257393396915320220786117812090114202904965841362557073493466137396957389179,997,182401,997,225329171368509161580472750897026209271177545132054535919092795048175517709558661017404496471571909222764775628194943731479366517164081876622381021735832173151443162628171041881190685097728786249713457178472422049206541511338483211278808636889900059219,715721,1244912548997288185527473761862023255641864890232345502315429806895997335411926303963560753986585133827429699603286981941874953133503214787968955921192442945588083771426359347409893287832755725136538437450123878724898019399660128239109439982817127399,997,184439,997,147948824613896094021559256468208240621247063714817440181805623939619560948705390107983487027464637347879398154756846108483531621445912903031841905046959331289859397842582645928423887704550435180423126450785960262310310693874091438507922975428859476159809606172410845400699,723889,774601175988984785453189824440880840948937506360300733936155099160311837427776911560122968730181347371096325417575110515620584405475983785507025680874132624554237685039699716902742867563091283667136787700450053729373354418188960411036245944653714534868113121321522750789,997,194629,997,3663574983339472396374498535089718440151822588170139197923643104403964824873940016494197681580897911686389150772108064161475879219326417780345224634357375369523896053565948898451794062203069501481019903036711514600073580767056801019,734099,18982253799686385473442997591138437513740013410207975118775352872559403237688808375617604567776673117546057776021285306536144451913608382281581474789416452691833658308631859577470435555456318660523419186718712510881210263041745083,997,196667,997,8455278772776224374271023592698437808269362247194077422320886658621746174281418149174663922086515928205781678321990770649841595335371231946470738240060062353185284927152119985585357359688807996283753901135009827258161244214785267280127016797383,742267,42920196816122966366857987780195115778017067244639986915334450043765209006504660655708953919220893036577571971177618125126099468707468182469394610355634834280128349884020913632412981521262984752709410665659948361716554539161346534416888410139,997,200743,997,7418664063326667174171516407096672529836721739118262523809114802763367797444381,748393,37279718911189282282268926668827500149933275070946042833211632174690290439419,997,202781,997,1216142943931601900840499346326153294372963200662871598602878771751067301282935383481935570679941736286303494921026416345368409318863091781019560429709350064711390142526964314902108955296323216588439774090112698978970772874445246117374500899,754519,5763710634746928440002366570266129357217835074231618950724543941948186262004433097070784695165600645906651634696807660404589617624943562943220665543646208837494740011976134193848857608039446524115828313223282933549624515992631498186609009,997,215009,997,138691792998900981393067649792787848641037326193951782941236989320550933465674492476050781517256816980352563136501783747517774908582709149868844034074488483067697567425768441388229379485083067254522425925225280069810787466572004302011,758603,621936291474892293242455828667210083592095633156734452651286947625788939307957365363456419359896040270639296576241182724294954747007664349187641408405777950976222275451876418781297665852390436118934645404597668474487836172968629157,997,227237,997,2028493490644134181545071400466908110867796623181315854487633734557528690094386218346576853932530189093546742060337625157893636505419736098290811151374445048600018545156783393583253452964962427130653747772754254546889532223197256645401908955067327736231726068875643791579593259,766771,8936094672441119742489301323642767008228178956745884821531426143425236520239586864962893629658723299971571550926597467655919103548104564309651150446583458363876733679104772658957063669449173687800236774329313896682332741071353553503973167202939769763135357131610765601672217,997,231313,997,14149311638818710272508768215683034141538149399907158174569462453878173117322097753573649385838904038871126756217699203940141028311501017698570123066261061120171424198367746633234728713058889449330070324521632921517787014310284981552853646663319503779299,772897,61787387069077337434536105745340760443398032314005057530871015082437437193546278399884931815890410650092256577369865519389262132364633265059258179328650921922145957198112430712815409227331394975240481766470012757719593948953209526431675312940259841831,997,233351,997,30093876104292118234789101271657244880699998710604456683832260298422030702485065967861524326546606571039352053995299041938053973700300262936244544083334881309585916203495310045228392711906230431409629365533390067925197505085591927635071892148491,776981,129158266542026258518408159964194184037339050260104964308292962654171805590064660806272636594620629060254729845473386446086068556653649197151264137696716228796506078126589313498834303484576096272144332040915837201395697446719278659377990953427,997,237427,997,3341433274322410860909358920965655465914609433427753011787584445887163322575233606213353128070580943023650547154816689267633028226655069995528795004468493200031965955545943936872867057651796177238218640454146294226353627831975242231915884119383355513992675163415937324785211381,785149,13980892361181635401294388790651278100061127336517795028399934920029972060984241030181393841299501853655441619894630499027753256178473096215601652738361896234443372198937003919970155052936385678820998495624043072076793421891109800133539264097838307589927511143999737760607579,997,243541,997,4118476469007064308947375538559785902711241611772556924176911678360484298072250699,789233,17089113979282424518453840408961767231166977642209779768368928125977113270009339,997,245579,997,931152388751175201699068624778090289867417543528220592117152773927749269913068388840365617398521258477932276771590394237676949552026467097846301304616397612088831084369673137110207936130665169120295304026669889420982367047795994272488560887275037507805158319176442153344967337522071321821019,803527,3709770473112251799597882967243387609033536029992910725566345712859558844275172863905839113141518958079411461241395992978792627697316601983451399619985647856927613881950888992470947952711813422790021131580358125183196681465322686344575939789940388477311387725802558379860427639530164628769,997,255769,997,2891247412588934131535766310701430184913777993027195144625265514460073835877768281374678458180366942013537958473137407582426122601856395302375298667160312868283179007377451488414685852848881981660077537670642989489234007367886409503052947081175934785149006331,813737,11249989932252661990411542064986109668925206198549397449903756865603400139602211211574624350896369424177190499895476294095043278606445117908075092090117948903825599250495920188383991645326389033696799757473319025249937771859480192618883062572669006946105083,997,261883,997,13899422530678692053654718384395654516426347025655826879567494777451559730600568674546707009339019292739476335367327016017867581118288482087649526209799357787918091759795268071323583783939990378975910915464265365184472642331075137172120703394599859293071808179295648708579999684135452477,825989,52849515325774494500588282830401728199339722531010748591511386986507831675287333363295463913836575257564548803678049490562234148738739475618439263155130637976874873611388851982218949748821256193824756332563746635682405484148574666053690887431938628490767331480211592047832698418765979,997,267997,997,1355699963191169974672204718471466004562253812733568890856366430755543607435448494756142541415471836728113575979434855183498286076476238071951618737682287160425884197494461103908314040707400572892652361779504788601631816417329651376067771467758410992920761631,828031,5039776814837063102870649511046342024394995586370144575674224649648860994183823400580455544295434337279232624458865632652409985414409806958927950697703669741360164302953387003376632121588849713355584988027898842385248388168511715152668295419176249044315099,997,274111,997,197770168183920893490702355213946062548862275593686785036823325489830493680361725109,838241,729779218390852005500746698206443035235654153482239059176469835755832080001334779,997,276149,997,235066939145603730138455797181895332556660643522557763976711397934654296027286248141866352067440614645980785211857345634122543197521067658886043737467928065242170439144153675267262025034856560884161819395341422586089798939047835618577282359011,840283,848617108828894332629804321956300839554731565063385429518813710955430671578650715313596938871626767675020885241362258606940589160725876024859363673169415397986174870556511463058707671605980364202750250524698276484078696530858612341434232343,997,282263,997,653856944817121418564574769158558214241652061694177451283815899696349734329343253379,844367,2326893042053812877454002737219068378084171038057571001010020995360675211136452859,997,286339,997,153750924705191331202642487855432301214999247349347135664932925672884382532572106143629862520851000964392448797347295129760339890447171549018979033727220079019470962832403597856104509630053226079444303822073464068832801004488749074363606794131843019,846409,543289486590782089055273808676439226908124548937622387508596910504891811069159385666536616681452300227535154760944505758870458976845129148476957716350600985934526370432521547194715581731636841270121214918987505543578802136002646905878469237214993,997,288377,997,9247489933034770345008842513605671240539329503796940360077790769034919055860192075961498268156080222753546521642413997960863602513249430650096399945058850657850730509948718278723816846696059730196008820021372108447626975263432296338773003684247622175988091632568335607339591109011826268182783373997524131,856619,31561399088855871484671817452579082732216141651184096792074371225375150361297583877001700573911536596428486421987761085190660759430885428839919453737402220675258465904261837128750228145720340376095593242393761462278590359260861079654515370935998710498252872466103534496039560099016471905060694109206567,997,298567,997,1717407504335870232912715929360339133649245648531977431437710884144242413898244908199676348333630782469611821101441951565524681310844200869852683280497944626558680801715390769378642397671865997499800973267974091300091032739882947247896538134151189417,870913,5594161251908372094178227782932700761072461395869633327158667375062678872632719570682984847992282679054110166454208311288354010784508797621669978112371155135370295771059904786249649503817153086318569945498286942345573396546849991035493609557495731,997,312833,997,186094640094728709905582884915209478720162295193640169865982338425202130855964448777365803096561599373266189003786443004976861963671620462507490499001087000062228617512324435299563374854468112230954656065794720439794736047301775255274615166365555906615082699,874997,598375048536105176545282588151798966945859470076013407929203660531196562237827809573523482625599997984778742777448369790922385735278522387483892279746260450360863721904580177812100883776424798170272205999339937105449312049201849695416769023683459506800909,997,316909,997,99031418963697124674853988324325827852540883371919853044916122582908820976031775150461062479829273919254632432784471230762209126862746456311631012017430778342731130579275835965526802369447102695762351319328603240840216102895901102277717945225511617318692885468391820057855359602494115072883,877039,316394309788169727395699643208708715183836688089200808450211254258494635706171805592527356165588734566308729817202783484863287945248391234222463297180290026654093068943373277845133553895997133213298247026608956041023054641839939623890472668452113793350456503093903578459601787867393338891,997,318947,997,42242760426214852365008492021688249001199142271915160025206075397415289834494590552596465606988123248212551380300285932126774225020692469707080058167842164648746139668051737622910245137506042977114350839236678790426338968454103079402971043834421080175047132836133633496964302426327,881123,133257919325598903359648239816051258678861647545473690931249449203202807048878834550777494028353701098462307193376296315857331940128367412325173685072057301731060377501740497233155347436927580369445901701062078203237662361053952931870571116196911924842419977401052471599256474531,997,323023,997,107307369572290541384475737454740253494018594946523953948261811827034605510928874078489851241855815524617369122814813937716249011703046172889308428655342212025001891566435646387451504158097825535109820621633632481094109611807638752054352547330203174484844484659,895417,324191448858883810829231835210695629891294848781039135795352905821856814232413516853443659340954125452016220914848380476484135987018266383351384980831849583157105412587418871261182792018422433640815168041189221997263171032651476592309222197372215028655119289,997,337289,997,55064612321770155133157362474829199989035428581948598172981940137568403555187622908028564874669701059511946421406182521933816203496055859680958661046865172951343822363678488724509509061180572829585917059572354958143854719027588481590624599078397653942081134186048842079801519289417050168490082593323,899501,163396475732255653214116802595932344181114031400440944133477567173793482359607189638066958085073296912498357333549503032444558467347346764631924810228086566621198285945633497698841273178577367446842483856297789193305206881387502912731823736137678498344454404112904575904455546852869585069703509179,997,343403,997,191910400529505153557224617029107865694106741205348818904526992376067891765008424641623636027152487218384283069648741467693297373871543851103342180022015891721139900840652679154541010152081242584577176398651308152433498225132989871250359174352180752175700889727556239511651,901543,553055909306931278262895149939792120155927208084578728831489891573682685201753385134362063478825611580358164465846517197963393008275342510384271412167192771530662538445684954335853055193317701972844888756920196404707487680498529888329565343954411389555333976160104436633,997,353593,997,195306582131271451009334326954770025184144851578630324452422872021506820732014956379715234978255404349682123138757786675633123282560391857045894094521929176524667838378563095623212129113112952618142325576737520038648102942539205523023679173996788382216711019,905627,559617713843184673379181452592464255541962325440201502729005363958472265707779244641017865267207462320006083492142655231040467858339231682079925772269138041617959422288146405797169424392873789736797494489219255125066197543092279435597934595979336338729831,997,355631,997,1215456615647736981075511688343015609651098104001912463828764256884376773285956483375387,926047,3443219874356195413811647842331488979181581031166890832376102710720614088628771907579,997,359707,997,152371024479309333613791270766813059934644240963510757940065726092042020167346294014239858246488261844181541553866797374541435361748272964733304606225836878830766560242205779764084434055945144673618075979996122754129399688334667194097420399639375481262924139926860301,930131,424431823062142990567663706871345570848591200455461721281520128390089192666702768841893755561248640234488973687651246168639095715176247812627589432383946737690157549421186016055945498763078397419548958161549088451613926708453111961274151531028901062013716267205739,997,365821,997,8805855872789019240710264044493313902829667579523595450483405927948456557973767381593768592699990307656047373848464298739897608488173415985344555327733960422040018571984480783688585363881034183770028635322562755061525965264076157536693656742309428857200200534740552445744340920479346348313632819317,938299,23994157691523213189946223554477694558118985230309524388238163291412688168865851176004819053678447704784870228469929969318522093973224566717560096260855477989209859869167522571358543225833880609727598461369380803982359578376229312089083533357791359283924252138257636091946433025829281603034421851,997,373973,997,1095376316278855322873293779067055170364191817021514439349116525031244403693815779672168678363649208457797649035029957775057822028226826207868697627085868397348111959279609148252080232892263125008811953482298559446432650497666173228960391046465035759461531583942148845722771586537518927520699,948509,2936665727289156361590599943879504478188181815071084287799240013488590894621490025930747126980292784069162597949141977949216681040822590369621173262964794630960085681714769834455979176654860924956600411480693188864430698385164003294799975995884814368529575292070104144028878248089863076463,997,380087,997,15369226844695333062849381477909582790193081087319522766401784914789199098254937701754942361481513813591507178592892064416009512989526432006888411812015707106697003660843933262218400518290304215112593252662042221838402637726323711885254485048250408355850463886893101619739,956677,40552049722151274572161956406093885989955359069444651098685448323982055668218832986160797787550168373592367225838765341467043569893209583131631693435397644080994732614363940005853299520554892388159876656100375255510297197167081033998032942079816380886148981231907919841,997,386201,997,17936335753803465319644606369717202510207061261553117383696431100566559448104053392344197,960761,46831163848050823288889311670279902115423136453141298651948906267797805347530165515259,997,390277,997,25893139746956375074671910466488819057973682757474498176744179853848279269471981476034178206434626829662341282305098421017615074690674938772214414369410376488767243876576772000943323646306806499600311513657727872637967224802501913807127372752863262895742486671,966887,66563341251815874227948355954984110688878361844407450325820513763106116373963962663326936263328089536407046998213620619582558032623843030262761990666864721050815536957780904886743762586906957582520081011973593502925365616458873814414209184454661344204993539,997,396391,997,73974572111317406360276225631919880970967230930546543997873687812509688512760842513788622380060283819337381239289168279398371925148558197982252822440463431991798888852483797550848552471579198228007110388157478970670518327902466795935796129943875075370218141183995374789284599233523734628628605149143767,973013,186333934789212610479285203103072748037700833578202881606734730006321633533402625979316429168917591484477030829443748814605470844202917375270158242923081692674556395094417626072666379021610071103292469491580551563401809390182536009913844156029912028640347962680089105262681610160009407125009080980211,997,404543,997,1307141793874862084461913041302240551365792174026016528279865697359005336719217669177196976468676813204191353984957820150881355004620906305582162121381248966040062853839635204011545101328676009151433346953408816476579132602933740590965014866256568699705065819,987307,3259705221633072529830207085541747010887262279366624758802657599399015802292313389469319143313408511731150508690667880675514601009029691535117611275264960015062500882393105246911583793837097279679384905120720240589972899259186385513628466000639822193778219,997,408619,997,7093242912463185348072070110212638351742462073193796871217834643050267179901187029507018490754437695656607535423037831588564687811978689937562105842348187968983989171429748478114974959055204956755248726089665726321535007236838047456328883300447788907493192538880498815296925888779,991391,17342892206511455618758117628881756361228513626390701396620622599144907530320750683391243253678331774221534316437745309507493124234666723563721530176890435131990193573177869139645415547812237058081292728825588572913288526251437768841879910270043493661352548994817845514173412931,997,416771,997,1185579641965561589160299697265721932824027132750467864460376877428924099444308658448594136390967744065181760700818974092571770178341715224937792646992702816801853703682587972668759794434610387225171807457005618044826070319744092967744160173564727037441446431202779572868249757967428377671066761,997517,2829545684882008566015035077006496259723215113962930464105911401978339139485223528516931113104934950036233319095033351056257208062868055429445805840078049682104662777285412822598472063089762260680600972451087393901732864724926236199866730724498155220623977162775130245508949303024888729525219,997,426961,997,169052738021865017945085217436498678340551974017269410534135929153837234291820715450799841864356228195340732263779,1003643,401550446607755387042957761131825839288722028544582922883933323405789155087460131712113638632675126354728580199,997,428999,997,89600456898162554710940038315160351182309734414129170687610033541862560707475499371198298316876962891405560250165152771675263407396177488042619118232855720276625778667788670057647578107276749358158513983871052535363437572582097937450349496907401800441822855338949217171751568948262972788043043591458773382280560737161315249005363622939,1011811,207889691179031449445336515812437009703734882631390187210232096384831927395534801325286074981153046151753040023585041233585297928993451248358745053904537634052496006189764895725400413241941413824033675136591769223581061653322733033527493032267753597312814049510323009679237978998289960065065066337491353555175314935409084104420797269,997,439189,997,433,1013,1019]

fail=628342186020279030208477196652234251466546172127229920271442149116418270266805114129323801879492482137898525457610034761318243685701612999753301446499402184019047334363868952491996606714667813682795710496729144356627735845123676166105603998123636223487640503561426022924983170637012661801780667366986496506030776535567526896671098662632123365168743664803047333533266651378724651134747558720373671125128918192606546275484822315302537833017347515852873969123863196991591128905797797953641849823901200591253758989661116185809449387114754110693862270878790685521494032855174559448217678703819332109924602615048084195117590112536399286371826740412069584415578436175604905487388386875110557418165843986191168930994241095051887359640391104091658653518621901534663248053930033780121015835031607604047633957687509170016778799461147891167654749638057549827992932889122995155539900942798016011513799665913318026811781018347609393399492693089473128154346668249800406988857586278307546023464942900979079319193897231953014331315745983540688409217523781284767071786748835334904114251151768066947066974655638700742353772603987770915012114230380632982060506677995390598274839813186589487880327769882355406369328704667144104785532210079866539787033200765829359931127219031553817186725838729517291842565585345287913859037622248318083084610913049915914358110409209100852502593148685289707303219729372851454213282755549475037954209582986949880668930047153621586488494270546617243702586105425080170041634818438278320529852112847863734593944644022898353545446882029646417103689943919192691294079623058308937404741503543204905870498980563398747865075941095954326295793595346961572874520213826034401809759600671385592618044358788220764179037648551723688883462655964529249402109637617708231973919514209153002131026182417912198411370401495384651131774509722038523496382808921942374492604612687129063485332311030348703446367201242825533393540915424705051574412572120162877997562692412185247999611773833311632900771473429755915441182540269617877214830627528032509574263455045777758312790203647404347503161728097958892560903112974915627570659454527665768438056409725068410760146580760573561825743041360562327507023011036093343294488329397226160195885463366678787014633928020875226483619664858890687676379225725094561398719056931046049652997474332655225198880371911150572119222293804816869964938939569929273415161422698066449231388944785154171990521448471715053090799940542872248125377623217571815993265916187470537162268436325773823823025764997980088398890569841898462161853267169228882950197460075182837289919940982931539635781819167833327053366074466169096663110752528063831392419664656628996209161385538062512860770349218644155662924022242464260618852724359227862586009757511987837154780681347585339557128064674324666633148721900366457274096873746373036267539915146015258255209166409983804123119669569892997296082665906047894529706757974988307364081640652759420620606279591460036311764255114156837496511088449627305129870293650489346534475746640218520980739890581556540008279019229663760636485837245208764597357678419738833265275277731038701789683747837440024384633103957164283508891650623445519394459252271959449686279179444136374415706603701561041515600084286014592770962766546924881353153028839585503598573550964862568899783340905087121767189848319028823764126564635152182745746588976064614585513882178320384662630419491983556919743035918979272357120571425297548004511661675273618557126654548778343459193970691487722304790664607581194061709590959173879314951330697843870052828316024354166567082187518547658698577696795531130565515421083180252264454883596870044949725930149179966847413679961101162747165984569728196830920577134702664306366364197595517421138209600525104047202300339400088872288316077221656240102231143786257343020802118922926269205047219736723123445530507690137692235730009368553776231094320766355040830168009092017813288396850664476916182018546812944453888512931302160127019704913501725813307841245312731953948196722380163601568492780144962109057602369074555334991621987390374358769710617552391326453785020526405147640026146312997938788804138998232289707025657098750218408744926601492274136339769211112547916354899730071425547372588105403900685731200370521951579349841013973635462586811702994385448941952099615457769200940648360138128946530932948358590141678294540263461985603817191898095061752838756758169435695558894946752558724707225186802024978616855725317670898178008742128975014258782925817349723286317727283132139495271815132726481668557882676887050885378442098538933512778731774361164801103687075162670233525972446022073437141634190995911089958638936702125877258733854190658955211486896795807799247056213685696237168010636560453178295430632262922179196184338010387026042081248735157060332183087380384908870579342268028791502144475517809808520966859616554102946100611417937595977703395161367239525150406899496101767146677522362467244175944639777276553647414851795784699778438111349113652477278343467027323819397269455041625832813112347020033822455376729028165116279358528229084987521170918228041096904599804373545811652965962629163714889427307592378384787948608392935161760512373031943294253135653945376467534645062128214176859177671917924470733170543663095164294078188577644263829357684653992808048115290898706559292435665031983147770618047696164278180114571883909560849919923071788171847093498306550580036114960340160679659003480666374351890273587413582104233093778316851445659944947034432138454639433320133679779403332875832288448336528056715331939264128997610951123085318980941191657450923186786281447594211168439296167068599875424211947381124503574287428653464197183586766917064698969607222676938892700337244499023740021533322407975632591913985176741704511237708175586215484912007730703539347900914569981861379239832893109915816827892646998809604355655684309972455745534857625387871413240766757912260561276872396077870424036155192914575494839379065148798577492895218102356645374808828351190560242930341412752377938339484272418298446253783645567893675139638014454360329933950740656010948440208956227962611495754650589391649847173952559561706238119700416870351183225680846641395695009002342404433610812356666485300887852999615689594544734258696785715335953720841080346734273745462225722854716944440612200907986986761974645226700321349237318729650027840661849263165071729001132412715683532938282372956492101123225224688540919293418074389951077117059370386174729181602053802620109858124680047124580359410149534093848987322604588465223269320290130009628419324527856018953957600035078765304742008540572117322791116024555796432461153651126300748828389259598990206877366444955852954604969428779178082528034059004222296475937635225715400197410351141529356047922229074568209997829979346838932511651507196184691420815697818582222639999405831514378102612043068259534775279462337493896484375000000000000000000000000000000000000000000000000000000000000000000000000000000
success=5020973558043690795472466436617612912981186347488363636494918897580345094619354831599150783154458643768824774086684855736649234567349871237720799314877192413924062850078649636850002055053944829186672671708163716322615209049354719596052941417213532076312584086034682854165737646092676148538845676199745010081171006469722614059402250242308785689918241284131648855341488804135227553569275395839797208481228297968911162075439845594462320763237357071166784713446778736264921216635219120279353441051381445681864657026276821922514536569544725327622938331970575312038054498527495497627987060787647164378259819498672242544076388147523885345280342831806880870923391335094231290063505894883622740743763068210341558532266730092057471805710970239830698232092553019009302257534520260356188869212033343552453220921330349478151838282759011653076078016714211215874482198987741235273840751410610227050746299055028652883630584960936757395646616847713407087225242767250411952408673845861387774237778205037416623206011306490376976238654472840823151891585075016585390922891098308045393593571415253634799881795632166478595261694471140226795538975637348108530604584641278570409344858021708185167591243455235623668321570654443319286878417340676933354064642723586253821998813504508098460362918587904912942418728303547539706696690550986778207008561820335924406226344605013700816659534219628975931010285852931303562594784807047348570737396800467230532753148948447635460563997386651374238754668022458990241654392066026389403056595070158613582087349737094737658808886315648062674551872063472621765109045797432205715733767132011793304312274933554077784748964538523889920306652843830639205498914392896052991230020283366189067754757119427529149351327101078032307908260603623126125800088927147739506163527183895257938715531016954102699245294031066253590763425350011991169491433278653398617395440744762010472263802586218941241055055743015914720823242262689467262506542601425806024500357983702028225857710867057862345336237222517523041907324188469202303664776657176177623265573649232807583121306909916426816016755317491385615404780845499430052098612881460431944822161954276179349694442740819075713633944412726802575579188952121635648787756123395044724581329422707259129800369169535652642639801159987649031332406466937818074557103914266685904770137348134689897321542175254693720185576746443281607586987415388428553993232704096407666570219410589863873312494539460705640975599199448114612634267109102407317730904132567388335904394477797328315856196208327128937370947369504646584356343462801435206697336876183024095674551448335131879630403438713907124638478413853269148185567784954639444384365569717712309310955147830166043443238005822635747057545664360288684594697328877448799025973804079099439380682972847878899045536018223183365782765974974091131423937943531681735723827404656800066615668567805386492162335823765656414065284523264752292185725090814264699334921326855584899083371098784162003309739906310772506255393733874274017314112532904577039191591007997878380622798755534627692925758417448816637818373973221551606967096451086316437822279771077272376148121571163290736638931514234910318028624294165025145259063674698090046911948075952284431571943853982442651363186672689212765267770285908709835564485153350230618682629074091170797310328555429502555362409867954701387470139759267436167728204441560324447484705204937156843869157813675957725786241495777896024839838398414785265343398641920748711625568412042688914128968190201059965530908706732754193849067931364670270274047648481440681370096814642988815043774848838838626624938922121096710544680023288597319646570406408354982897201465676769575294628096694930977248824011077321485418818924406431852258175057513393216350344049082542468361410424350720060469598506634455467477484979788747749796354609315723688211379376475460277770530264522516753753687913348610617627180044792600195906279194933087464933773782907713330404447333076666728339988449815215434318007623282986066831788891581783579614726180929544276009541965962239461776447541627074351182275490323828208628197483439346482508248446963369489796326385731064053724062808612872776418445167164620078205714184802118485145759294486622205254314132962840493288591203480571662819511051274785273705020148845879775227997407048971388002158100936213131756838746879763532259763345808459116288029766085022119913164248480557500068314593231088987160279569530688677315004982622289441794353406429725797216878712063025668632142903490923190360349140006080712281827399665057312208935502000825739775748382409547767113303970336836210669133926895235962501629552040586816345650814016614025782130788916609032745001899785992601494105680942665185307812466814213377653431289952318114685582720572586088812989364579521550555538171289271181678410758350157911033362222192696775165760690677062098520936755788225598782659548261103482659701827359313630846363889110910616705120073617014817614569968408898086698115057255739332773912661929818195363021921324903304920137570439912113419361155599656792846430129297557180197243737754764342250277820536833873850512952381832218723730563316514909646802035262898179819524477957536959221311168489498330910004725990255589480473575235173541252809932701389183846177964235287033830925857819001160586184156930429524672516539501165080375924833291345560537459192125694725922302068041992414208055805065909773572571976130403681164189313519334650691350894602614796418772828939871059035015115580766571764509536576557130464695399374994550899074089674240089589432866719236464202233403294885582612550745275632442296172192623564576641486142828317213702576891904379598321939228709403256536312047969623685194330246456663079749586499084220375579316652507872292946875012466482824470432774707250524489619450216896375750616444251664515756466570884810083576309586519141251515118124071845062312157097256288192961806792066900270500521144047770243562264487965415262662776051613168034656779642758114200039168472440692230333077279334828068865916779206390832407497613723856853959754467657674563538356200113237531415811715639082774172579453150559544048837197565500009080784265163136751719074454322189938394735894637025740187989314178929192969601790353384766140549815636197188798439691133630864251539048445431466504628211935886080852752935630094058548912025946009818396075472885206608300233436748206662616807944144796532094594620433469104447555629020079624892194386879122958004893129494842096402682811580537753137281234266545777016470955138841847355634423380012680312487848379430425081882125872830213363022475922799999654579438370854572957242484172090786677950121432476319475502042779427036319762004097420400844853692174042251171285933661004386621015926998839941599937383368984020896260270592470934269224540700618758089646022331731630333468362387499863220719689333769720594951447656934220607389756444636956576624383813057790571838503297531863499031792359610404317936111291681774481991887238261842808901836334223213707711107364485905291532705821130807123125454420222217016446133202332841807820589616482431348754917145101606467632094604680353363557871712551081392926909985237301152861238448196740016300218475973366025567832749173016062387042861194087419952458165039784986962997512974528829545248332349853718708838814455644705761832485931700173130071897488979237327246760914209146081519385108482784142154660288373455889906583829801152124158506717738674619195960806284400917112864093439783694796630478012378864676928266821333294750308467294460965175361532830951966724506606586746876954737693583126883851147396217944080036427834332965580301642572700340135310646747719129141401437460780643498914539005330191345728255970110381137385266964222518724087095866095862614718716057244839384375250846048030470719467935727917893539564429681478585454577297831321858756129328359401791440618517519405327157366260531819490852031046823010869408062657846696435219976461406268554894567770971764444584971135801033696477178443244408796389792415991584094216896934420766505635365939320304110028135204359699782309572808211604994257856468898963160670508388545426450891965355149110111299200922903858711721574257678665591805489566917051248264400361657973441314647767689458266932904273127096255063678875054002411113587425151644025362144946685722667666911552246977486100064975984657109331523076430943145383842843621837003905509584456012817099690437316894531250000000000000000000000000000000000000000000000000000000000000000000

v6=[program[1+(2*i)] for i in xrange(len(program)/2)]
v7=[program[(2*i)] for i in xrange(len(program)/2)]

from sympy.ntheory import factorint

fv6=[factorint(i) for i in v6]
fv7=[factorint(i) for i in v7]
```

gives

```python
>>>fv6
[{2: 1, 997: 1}, {997: 1, 439: 1}, {3: 1, 997: 1}, {443: 1, 997: 1}, {5: 1, 997: 1}, {449: 1, 997: 1}, {997: 1, 7: 1}, {457: 1, 997: 1}, {11: 1, 997: 1}, {461: 1, 997: 1}, {13: 1, 997: 1}, {997: 1, 463: 1}, {17: 1, 997: 1}, {467: 1, 997: 1}, {19: 1, 997: 1}, {997: 1, 479: 1}, {997: 1, 23: 1}, {997: 1, 487: 1}, {29: 1, 997: 1}, {491: 1, 997: 1}, {997: 1, 31: 1}, {499: 1, 997: 1}, {37: 1, 997: 1}, {997: 1, 503: 1}, {41: 1, 997: 1}, {509: 1, 997: 1}, {43: 1, 997: 1}, {521: 1, 997: 1}, {997: 1, 47: 1}, {523: 1, 997: 1}, {53: 1, 997: 1}, {541: 1, 997: 1}, {59: 1, 997: 1}, {547: 1, 997: 1}, {61: 1, 997: 1}, {557: 1, 997: 1}, {67: 1, 997: 1}, {563: 1, 997: 1}, {997: 1, 71: 1}, {569: 1, 997: 1}, {73: 1, 997: 1}, {571: 1, 997: 1}, {997: 1, 79: 1}, {577: 1, 997: 1}, {83: 1, 997: 1}, {587: 1, 997: 1}, {89: 1, 997: 1}, {593: 1, 997: 1}, {97: 1, 997: 1}, {997: 1, 599: 1}, {101: 1, 997: 1}, {601: 1, 997: 1}, {997: 1, 103: 1}, {997: 1, 607: 1}, {107: 1, 997: 1}, {613: 1, 997: 1}, {109: 1, 997: 1}, {617: 1, 997: 1}, {113: 1, 997: 1}, {619: 1, 997: 1}, {997: 1, 127: 1}, {997: 1, 631: 1}, {131: 1, 997: 1}, {641: 1, 997: 1}, {137: 1, 997: 1}, {643: 1, 997: 1}, {139: 1, 997: 1}, {997: 1, 647: 1}, {149: 1, 997: 1}, {653: 1, 997: 1}, {997: 1, 151: 1}, {659: 1, 997: 1}, {157: 1, 997: 1}, {661: 1, 997: 1}, {163: 1, 997: 1}, {673: 1, 997: 1}, {997: 1, 167: 1}, {677: 1, 997: 1}, {173: 1, 997: 1}, {683: 1, 997: 1}, {179: 1, 997: 1}, {691: 1, 997: 1}, {181: 1, 997: 1}, {701: 1, 997: 1}, {997: 1, 191: 1}, {709: 1, 997: 1}, {193: 1, 997: 1}, {997: 1, 719: 1}, {197: 1, 997: 1}, {997: 1, 727: 1}, {997: 1, 199: 1}, {733: 1, 997: 1}, {211: 1, 997: 1}, {739: 1, 997: 1}, {997: 1, 223: 1}, {997: 1, 743: 1}, {227: 1, 997: 1}, {997: 1, 751: 1}, {229: 1, 997: 1}, {757: 1, 997: 1}, {233: 1, 997: 1}, {761: 1, 997: 1}, {997: 1, 239: 1}, {769: 1, 997: 1}, {241: 1, 997: 1}, {773: 1, 997: 1}, {251: 1, 997: 1}, {787: 1, 997: 1}, {257: 1, 997: 1}, {797: 1, 997: 1}, {997: 1, 263: 1}, {809: 1, 997: 1}, {269: 1, 997: 1}, {811: 1, 997: 1}, {997: 1, 271: 1}, {821: 1, 997: 1}, {277: 1, 997: 1}, {997: 1, 823: 1}, {281: 1, 997: 1}, {827: 1, 997: 1}, {283: 1, 997: 1}, {829: 1, 997: 1}, {293: 1, 997: 1}, {997: 1, 839: 1}, {307: 1, 997: 1}, {853: 1, 997: 1}, {997: 1, 311: 1}, {857: 1, 997: 1}, {313: 1, 997: 1}, {859: 1, 997: 1}, {317: 1, 997: 1}, {997: 1, 863: 1}, {331: 1, 997: 1}, {877: 1, 997: 1}, {337: 1, 997: 1}, {881: 1, 997: 1}, {347: 1, 997: 1}, {883: 1, 997: 1}, {349: 1, 997: 1}, {997: 1, 887: 1}, {353: 1, 997: 1}, {907: 1, 997: 1}, {997: 1, 359: 1}, {997: 1, 911: 1}, {997: 1, 367: 1}, {997: 1, 919: 1}, {373: 1, 997: 1}, {929: 1, 997: 1}, {379: 1, 997: 1}, {937: 1, 997: 1}, {997: 1, 383: 1}, {941: 1, 997: 1}, {389: 1, 997: 1}, {947: 1, 997: 1}, {397: 1, 997: 1}, {953: 1, 997: 1}, {401: 1, 997: 1}, {997: 1, 967: 1}, {409: 1, 997: 1}, {971: 1, 997: 1}, {419: 1, 997: 1}, {977: 1, 997: 1}, {421: 1, 997: 1}, {997: 1, 983: 1}, {997: 1, 431: 1}, {997: 1, 991: 1}, {433: 1, 997: 1}, {1009: 1}, {997: 1}, {641: 1, 619: 1, 797: 1, 773: 1, 929: 1, 577: 1, 521: 1, 523: 1, 653: 1, 941: 1, 911: 1, 823: 1, 947: 1, 643: 1, 739: 1, 661: 1, 953: 1, 857: 1, 883: 1, 541: 1, 673: 1, 977: 1, 547: 1, 811: 1, 677: 1, 809: 1, 647: 1, 557: 1, 827: 1, 743: 1, 683: 1, 563: 1, 821: 1, 919: 1, 439: 1, 631: 1, 569: 1, 607: 1, 571: 1, 769: 1, 701: 1, 1013: 1, 449: 1, 863: 1, 907: 1, 709: 1, 991: 1, 839: 1, 457: 1, 859: 1, 587: 1, 937: 1, 461: 1, 727: 1, 463: 1, 593: 1, 467: 1, 659: 1, 853: 1, 983: 1, 599: 1, 787: 1, 601: 1, 829: 1, 719: 1, 733: 1, 479: 1, 887: 1, 443: 1, 613: 1, 487: 1, 617: 1, 691: 1, 491: 1, 877: 1, 971: 1, 751: 1, 881: 1, 499: 1, 757: 1, 967: 1, 503: 1, 761: 1, 509: 1}, {1013: 1}, {1021: 1}, {2: 76, 1019: 1}, {2: 75, 1019: 1}, {2: 1, 1019: 1}, {3: 70, 1019: 1}, {3: 69, 1019: 1}, {3: 1, 1019: 1}, {1019: 1, 5: 90}, {1019: 1, 5: 89}, {1019: 1, 5: 1}, {1019: 1, 7: 124}, {1019: 1, 7: 123}, {1019: 1, 7: 1}, {11: 41, 1019: 1}, {11: 40, 1019: 1}, {11: 1, 1019: 1}, {1019: 1, 13: 67}, {1019: 1, 13: 66}, {1019: 1, 13: 1}, {17: 122, 1019: 1}, {17: 121, 1019: 1}, {17: 1, 1019: 1}, {19: 33, 1019: 1}, {19: 32, 1019: 1}, {19: 1, 1019: 1}, {1019: 1, 23: 117}, {1019: 1, 23: 116}, {1019: 1, 23: 1}, {1019: 1, 29: 105}, {1019: 1, 29: 104}, {1019: 1, 29: 1}, {1019: 1, 31: 102}, {1019: 1, 31: 101}, {1019: 1, 31: 1}, {1019: 1, 37: 33}, {1019: 1, 37: 32}, {1019: 1, 37: 1}, {41: 120, 1019: 1}, {41: 119, 1019: 1}, {41: 1, 1019: 1}, {43: 98, 1019: 1}, {43: 97, 1019: 1}, {43: 1, 1019: 1}, {1019: 1, 47: 122}, {1019: 1, 47: 121}, {1019: 1, 47: 1}, {1019: 1, 53: 45}, {1019: 1, 53: 44}, {1019: 1, 53: 1}, {59: 33, 1019: 1}, {59: 32, 1019: 1}, {59: 1, 1019: 1}, {1019: 1, 61: 117}, {1019: 1, 61: 116}, {1019: 1, 61: 1}, {67: 105, 1019: 1}, {67: 104, 1019: 1}, {67: 1, 1019: 1}, {1019: 1, 71: 106}, {1019: 1, 71: 105}, {1019: 1, 71: 1}, {73: 116, 1019: 1}, {73: 115, 1019: 1}, {73: 1, 1019: 1}, {1019: 1, 79: 33}, {1019: 1, 79: 32}, {1019: 1, 79: 1}, {83: 100, 1019: 1}, {83: 99, 1019: 1}, {83: 1, 1019: 1}, {89: 105, 1019: 1}, {89: 104, 1019: 1}, {89: 1, 1019: 1}, {97: 98, 1019: 1}, {97: 97, 1019: 1}, {97: 1, 1019: 1}, {1019: 1, 101: 109}, {1019: 1, 101: 108}, {1019: 1, 101: 1}, {1019: 1, 103: 109}, {1019: 1, 103: 108}, {1019: 1, 103: 1}, {107: 102, 1019: 1}, {107: 101, 1019: 1}, {107: 1, 1019: 1}, {1019: 1, 109: 111}, {1019: 1, 109: 110}, {1019: 1, 109: 1}, {113: 104, 1019: 1}, {113: 103, 1019: 1}, {113: 1, 1019: 1}, {1019: 1, 127: 102}, {1019: 1, 127: 101}, {1019: 1, 127: 1}, {131: 33, 1019: 1}, {131: 32, 1019: 1}, {131: 1, 1019: 1}, {137: 120, 1019: 1}, {137: 119, 1019: 1}, {137: 1, 1019: 1}, {139: 112, 1019: 1}, {139: 111, 1019: 1}, {139: 1, 1019: 1}, {1019: 1, 149: 118}, {1019: 1, 149: 117}, {1019: 1, 149: 1}, {1019: 1, 151: 109}, {1019: 1, 151: 108}, {1019: 1, 151: 1}, {1019: 1, 157: 101}, {1019: 1, 157: 100}, {1019: 1, 157: 1}, {163: 33, 1019: 1}, {163: 32, 1019: 1}, {163: 1, 1019: 1}, {1019: 1, 167: 99}, {1019: 1, 167: 98}, {1019: 1, 167: 1}, {1019: 1, 173: 102}, {1019: 1, 173: 101}, {1019: 1, 173: 1}, {179: 33, 1019: 1}, {179: 32, 1019: 1}, {179: 1, 1019: 1}, {1019: 1, 181: 110}, {1019: 1, 181: 109}, {1019: 1, 181: 1}, {1019: 1, 191: 118}, {1019: 1, 191: 117}, {1019: 1, 191: 1}, {193: 100, 1019: 1}, {193: 99, 1019: 1}, {193: 1, 1019: 1}, {1019: 1, 197: 105}, {1019: 1, 197: 104}, {1019: 1, 197: 1}, {1019: 1, 199: 33}, {1019: 1, 199: 32}, {1019: 1, 199: 1}, {211: 102, 1019: 1}, {211: 101, 1019: 1}, {211: 1, 1019: 1}, {1019: 1, 223: 98}, {1019: 1, 223: 97}, {1019: 1, 223: 1}, {227: 116, 1019: 1}, {227: 115, 1019: 1}, {227: 1, 1019: 1}, {1019: 1, 229: 106}, {1019: 1, 229: 105}, {1019: 1, 229: 1}, {233: 102, 1019: 1}, {233: 101, 1019: 1}, {233: 1, 1019: 1}, {1019: 1, 239: 115}, {1019: 1, 239: 114}, {1019: 1, 239: 1}, {241: 33, 1019: 1}, {241: 32, 1019: 1}, {241: 1, 1019: 1}, {251: 120, 1019: 1}, {251: 119, 1019: 1}, {251: 1, 1019: 1}, {257: 106, 1019: 1}, {257: 105, 1019: 1}, {257: 1, 1019: 1}, {1019: 1, 263: 117}, {1019: 1, 263: 116}, {1019: 1, 263: 1}, {1019: 1, 269: 105}, {1019: 1, 269: 104}, {1019: 1, 269: 1}, {1019: 1, 271: 33}, {1019: 1, 271: 32}, {1019: 1, 271: 1}, {1019: 1, 277: 98}, {1019: 1, 277: 97}, {1019: 1, 277: 1}, {281: 33, 1019: 1}, {281: 32, 1019: 1}, {281: 1, 1019: 1}, {283: 100, 1019: 1}, {283: 99, 1019: 1}, {283: 1, 1019: 1}, {1019: 1, 293: 122}, {1019: 1, 293: 121}, {1019: 1, 293: 1}, {307: 99, 1019: 1}, {307: 98, 1019: 1}, {307: 1, 1019: 1}, {1019: 1, 311: 102}, {1019: 1, 311: 101}, {1019: 1, 311: 1}, {313: 115, 1019: 1}, {313: 114, 1019: 1}, {313: 1, 1019: 1}, {1019: 1, 317: 111}, {1019: 1, 317: 110}, {1019: 1, 317: 1}, {331: 102, 1019: 1}, {331: 101, 1019: 1}, {331: 1, 1019: 1}, {337: 117, 1019: 1}, {337: 116, 1019: 1}, {337: 1, 1019: 1}, {347: 106, 1019: 1}, {347: 105, 1019: 1}, {347: 1, 1019: 1}, {1019: 1, 349: 100}, {1019: 1, 349: 99}, {1019: 1, 349: 1}, {353: 33, 1019: 1}, {353: 32, 1019: 1}, {353: 1, 1019: 1}, {1019: 1, 359: 103}, {1019: 1, 359: 102}, {1019: 1, 359: 1}, {1019: 1, 367: 115}, {1019: 1, 367: 114}, {1019: 1, 367: 1}, {1019: 1, 373: 112}, {1019: 1, 373: 111}, {1019: 1, 373: 1}, {379: 104, 1019: 1}, {379: 103, 1019: 1}, {379: 1, 1019: 1}, {1019: 1, 383: 33}, {1019: 1, 383: 32}, {1019: 1, 383: 1}, {1019: 1, 389: 99}, {1019: 1, 389: 98}, {1019: 1, 389: 1}, {1019: 1, 397: 115}, {1019: 1, 397: 114}, {1019: 1, 397: 1}, {401: 98, 1019: 1}, {401: 97, 1019: 1}, {401: 1, 1019: 1}, {409: 106, 1019: 1}, {409: 105, 1019: 1}, {409: 1, 1019: 1}, {419: 111, 1019: 1}, {419: 110, 1019: 1}, {419: 1, 1019: 1}, {1019: 1, 421: 42}, {1019: 1, 421: 41}, {1019: 1, 421: 1}, {1019: 1, 431: 126}, {1019: 1, 431: 125}, {1019: 1, 431: 1}, {433: 1}, {1019: 1}]
```

Before every password is fed to the "program", it is multiplied with 1019, so initial part of v6 won't work on dividing. Lets have a look at fv6[172:]. We see primes in increasing order with exponents in order (k,k-1,1) for some k. This looked like something. So I just collected all the exponents and removed the 1's from fv6[172:].

```python
>>> a=[76,75,70,69,90,89,124,123,41,40,67,66,122,121,33,32,117,116,105,104,102,101,33,32,120,119,98,97,122,121,45,44,33,32,117,116,105,104,106,105,116,115,33,32,100,99,105,104,98,97,109,108,109,108,102,101,111,110,104,103,102,101,33,32,120,119,112,111,118,117,109,108,101,100,33,32,99,98,102,101,33,32,110,109,118,117,100,99,105,104,33,32,102,101,98,97,116,115,106,105,102,101,115,114,33,32,120,119,106,105,117,116,105,104,33,32,98,97,33,32,100,99,122,121,99,98,102,101,115,114,111,110,102,101,117,116,106,105,100,99,33,32,103,102,115,114,112,111,104,103,33,32,99,98,115,114,98,97,106,105,111,110,42,41,126,125]
>>> ''.join(chr(a[(i)]) for i in xrange(len(a)))
'LKFEZY|{)(CBzy! utihfe! xwbazy-,! utihjits! dcihbamlmlfeonhgfe! xwpovumled! cbfe! nmvudcih! febatsjifesr! xwjiutih! ba! dczycbfesronfeutjidc! gfsrpohg! cbsrbajion*)~}'
>>> ''.join(chr(a[1+(i*2)]) for i in xrange(len(a)/2))
'KEY{(By the way, this challenge would be much easier with a cybernetic frog brain)}'
>>>
```

```bash
$ ./05223a3cae8b71d81592d5977fb1c3622bcbf793
KEY{(By the way, this challenge would be much easier with a cybernetic frog brain)}
Congratulations! Treat yourself to some durians!
```

> KEY : KEY{(By the way, this challenge would be much easier with a cybernetic frog brain)}

Original writeup (https://github.com/ByteBandits/writeups/tree/master/bostonkeyparty-2016/reverse/Alewife/sudhackar).