题目描述

小 Z 是一个活泼好动的孩子。有一天，她站在数轴上 $b$ 的位置，并准备开始沿着数轴的正半轴移动。小 Z 每移动一步，就会立刻沿着数轴的正半轴前进 $a$ 个单位。奇妙的是，$a,b$ 都是正整数，所以小 Z 任意时刻所处的位置也都是正整数。

小 Z 的幸运数字是一个正整数 $c$。小 Z 认为如果她移动到的位置恰好与 $c$ 互质，那么她认为这个位置是一个幸运位置。请你帮小 Z 计算她是否可以移动到幸运位置；如果可以，请计算出能移动到幸运位置的任意一个移动步数 $n$。

简洁题意：给定三个正整数 $a,b,c$，判断是否存在非负整数 $n$ 使 $(an+b, c)=1$，若存在求任意一个解，其中 $(\cdot, \cdot)$ 表示最大公因数。

输入格式

第一行为一个正整数 $T$，表示数据组数。接下来依次输入每组数据。

对于每组数据，输入为一行三个正整数 $a,b,c$，含义见题目描述。

对于所有的输入数据，都有 $1\le T\le 10$，$1\le a,b,c < 10^{2000}$，所有输入数据均按照十进制给出。

输出格式

对于每组数据输出一行一个整数。如果找不到合法的移动步数 $n$ 输出 -1，否则输出一个非负整数表示一个合法的移动步数 $n$。

所有输出应按照十进制输出，每行输出的长度不得超过 $2000$，测试数据将保证存在输出长度限制内的解。另外，请不要输出多余的空格及任何多余字符，并保证文末有换行符，否则可能将影响评测程序对结果的判定。

3
1 2 3
1 3 6
2 2 2

0
2
-1

10
852473158087426181 40698107377421 34573878586
581501852629475409 3507820691986234 325392124094986
983001573592419694 12758046154806915 391181873366625
523432507089908187 22235351323484 99720444415644
547133061299817509 6492909838101120 234547940354112
315440975649541747 11555829815904864 467063676334080
439602165995515631 4284196383788100 23950691236800
8041598789940150 37468471223945472 3903034663348992
6871678354485379 19849006524667320 441009815372280
332133101579862271 12172161650895405 171736644454695

62
8653
209
9153
11
515
391
-1
109
23

10
12783455250264173814286920561815033129455292749111618918427759878900279810751984733300641240295647645498994599162724672629047892495532138517304022796851646558771922984858980119262334693601019798098147528413114685574056503715436537549292522354971173131279934494296523856354172666493759578559235721409803839003282397252589124075035701330994071273489705237262616797742375568061616753874936817653732331053918236491719070433469272496053789879577293093136499356430366004876174347137875860926532055047193332536966232985234902943131367685839673058435700772348235953215944653853083095646817090284623088732200913621558545052386885042144165328321547940688685206283677824239012495336775290807495043909817845678605221553727459510132354991460204987208647245314559868770002161766721560065585437486661777527998592610144754342130391951953419017996795637883263220168976979322596122704959150231743451325634540339716294155725269960803221336542937571792081037139459330357824733566717243006876271409335003836078762849002147189955692085715248990876391981766255248969629842537112053108152500087637823362918408326282337474710378962500600610349693653993027550952316316670853506306449406813119139788643083838328211821035371108143341935600097829865434811530599524028359788523071541453847264583333710123798328108566001918896610874808288975227629962146563973302514985616457681694941096019675649638734197123802474002128602378887819093164289307336054709619640526458697226534314914555408935927007541621264931926037372185067494993786587959784478212898791101939208908593012681830298437720655297000446578120709407231943461962332188295524845355039581215838303320770764898539181428691049707794809167418051510339852221874475513290850113263684417176656727864613919612116766407162187109690857320432723321345280123657010476175722098557540458136644293946857141877052604661078603646541069981640502793371518767316335666923800759018243396579180815135128964451989008345328070525364016754509674392674714149756548873402632728838590166371254746489441 44924584934298356258235247139515550277657144458132498920711701319209046837005601491725325650104446122603984225820428968942657142821237106326448598486364447934821424060473757046276786629098102167527673538036553991151541273947919892025604291204237290090107405121447367158704606912774391763259262891780036252203471524703366851604160103580747787054352898175420368862462141358161847230152789331018843086484212593329912348222277059280691902695892264715387133615653190723569903496603187488405999349317653662737078745787648567769844869079173449207207336861979579973618425342144127230835761987073422043679970470242803266680165591525343971536842802558791640600538155258124140299021534839210512287020369411255622076001574169024425018843663426370052763964519938206410908872864827508775245746148576446182132439091342389634159768379083582026347741997321884886737792957927430751871598993475295804545197485174215520946553554142369982004403301347822655088593311670803072067266836118377714175090223734357674032248208701205930266597361715787857546714454088116120186313378149957771238446809076734604509819777562794256682442798983992784805977674130798914112259542030082316812430332480137894887849353465816771517001487228826702481634158900000584884037245812401362420480513482406397747444923413014074744388374838428558981078412305694751828874536036424472521362350582327431095920954542444127350875313899455937053196754578226522615043097434617433872338162475543334536129590832318833885540797192698239197981846583995050379640905098742128786110292101587674488125232154270321372909033370681160671649283314323722096925350863808047856477440056435018490894338429353427141589876219024477179729631938051306076244246416874565368361240044590878306774259720122597553009341153034167032076164949807496735558195231891853274727424580590078545571228143320752605915739557205466685170808940973239406905759020140456486166288311181816084506195325571257785796456436314342322618444284460747087145534327694182582707201155919191443563283517335157400 38747494824482070352922587971841345158134903677937706957299078554979000613898400264161213696959780419626514843489882827363931833471571900799931389264885796060680852268380296956177808630532157537935843414998992446032247552157856432000542891503851657893782948827980727230427161405080959377685702832315987666462402218640129981671726165110123051269395991433442860368246889219321001435529202399441366581263889438274134699557132587877406202775593903912529009623542096112776930341884977271842416447501670853385639008908426571573611610786536213660289361256408832905404380583822900591210687791655768439671982694504173896423808038977485392820385621746604581835443903380115272605039828735814660821401711818639601856352838495166380090763345033751522719782678336797837843387051795142062674360832974985033387100640784846312740830468788910911396917042527059380518083709058020615301150521123821323958109313333631721204038674221023981991827354563263711070097215189823416971262460611188672079513977060016319191797286488531698281804309204994470892812968854344033573756107485666854351856329837880277206713967616917550502997590445436574061195849736842645211019046341821326776069645496417998633259355910660181224522116143322468134463772412359215924855604823837491968146789346969393924055883849300817457585642868360420670518949271943333467146814232203433930153429306269394554111755357753530856669497047739361691204973068008613760398045416010523150593286591673737667040288388747625774199973413789428573616832754510756063591544685139679254476429198760166173451813848111809372183614212698870570076468560163433343251353255684575425592093737878527625867970840551591992779555508493839981183028778838611310183372308931445734131618463296085126401128983294049031977185777097631053960342390543188211057297084934649118633078456216996692272841959873668728567294856722649798481835479581811687649444560833091325867704687545605943939826508498459439328451675261432043076070965791891222942159677083629301343061534654612554575659485714015900
81332009164280198104243050654578313400260551479800084981524084381560176473453703114640913028814355267566577529249914014147363702153785145757490568951334307043555860487273931271290443431529953483184104096911570791495128099333034121552409684546396555569656533603319539702056218234482100743397712302035879860825225443287114760788526905645241667375749372110483782524638434244979662294230290338407174220856698902138988360815356669332705152797831173662441969150409842411086337282138124779808769828805550815440031823416805936999849185662128161867619975205037914735829949696585394145819812050032847538811573638228682342657769993163722030953487008513448492703254323756486607765011844468240468568440937488775844389577360223225823034762613287041147993797380751937733867318890767079850781128012374504286850190809205004917770282086228825226577049603469762339221055659316340485625132953555942461139813318207602394712115271414444287962751581723198828452476455146508258661556761872667324128473284926030223067861873702023772355926887037681481790097251425579152310033555969417483209174032713097323354489509881481911965163388666851423922448585330045109501273849319797114843825308736852231314916548350526442453572343436336288547942035727663634821702367894536801519804727887749062667619027610401930957784447886329284834946943925934865156145248273763419986704670511735519684685560467655386148155124542591321254399749929798358551271860407448843950184525918813741048140714880108190294254013916949814572060925250279625747646689810535371298277457301835158012219729403955929204033946526988124434214700249855894178020011112358864948265333903603790999947102841540472306398893957078459294257562347672585703505242007284808333446332800017534838042660862672840050192995501853950272373270133704502250482638588846820750792837805008197474706881074163776404110206156808610458933057993946656037474685736941894421761737203125566591259684233704220077772726085183139556134626048425941614787054616966100538878214136815505145940609158859253727 67189780654249916596872549796808271354801419943278404837046414451153903246475394545718365630145246993175503713305427127068002457734677406859239536496173722455185479704801478542678624034927166517549956573877631021797649984151680107854452990076088975142455672829738983704626492361044522043961941131197397231806860046515780296989842104538831365443682251010853311952532732591299710955383977132309618347583593402995414783354996067316741339822015791599606888311629951715433119695655333509335552208901522380604417964256333909964399656261262877089298095276424202566604428801890639413787270131630617949793299221207839952368099865805828675029242931942293566440773796611801440260880793820114575865930364645437513204868079835959229088688955572576876913353636589131001183003105505217391926041259856308850680676620238420314003506882749874028303148585786525114460361669367101414647725090633113214817753652259062270027732766784793390157949249796952943443569469523595982553165648292080957552997629325958998391345666017069511164985904795577546277787244237167161784232399154087879976611401283343427037741290820927604478753188496198456061171810374757709263860305056210843254380895805909460895461813449445292226811602489612097432189044742660686474284199410408525913090325798574593480120864632089894843204371072872624702022539695137926270328854830664232452507284897370310551213474196366924297134304904860177468655275204281377047232738671779686294390905206794132292002603893107670923235091605193908617473024369852454248776474614537299154768507480296719262177616782097487657347026914488533177377739493120554458418659883483565594749540843442148322813432471854031400600540986833679775938919096356401142899955131349940431860415531666330976231641373041578168784003591035041934081121955735560439389436213784031272267416188903784625848762642635842813021135679916490330139655597128011225331182724819419307888128040161781018847150388810878439688548948649815928703141203170144979220128083604905772683899619046336037846906011443647200 56185112692214153591737642320891492869466117671430498312224782898555308033049401873334781445152649047455316782951885261832955960223050908137202186907211810218374603767716317708773685797165339384829324237330931092868163766331808376943251153876254941023930386586751266187940398767591232663510121592956769648908167169198669494352941440910147521421753129166267606036698639785530759526471838535489372628448926184806275681591347735039991460287619076556388777705898683995041427115387708043465217931786789942882919538584014962097852127176121044577525042300675541534224845720718297540182966449630731591166799936783233741731572354169069048960309685029165473971411202629034298501500865132789040973219740668347911181884703202526751980656473309357075485334688942822829905363956465346101301608166097910402580864128848618185341590653322684230099427241994330928576165692296371474570555698426861465067488655426142448642887149147531712706444281092677176635699890313683102514275397951246902281827537468751179553680310326811042425853072974831941247403223645643209286520339730763962407422352850666596404468284127508008936960356469562423925425032253396710024077385850692948826218489398170312625251655287964953803231952416697058743601166605772257161904025010727984357400324663421672964827052978684703502591418209965350356544684096845776535078370713658242946382674379487194724655684382035371941336300208252129801362123962609477508461139254559412334378048359448259487020504819182890880752456250267765704938530681089530735425679234812570237854510837827151065925458565690767266863912463924464087193859583398311859462535001928331416586560856720513300498601203156409026935037379586181002559084419446436220139034346521821015007809471443603559288327197760945172830985729585190206485431115110506893108329459123375340185270519651472645699020956825358988288608628508476913451376461165723893902031309917726228775542885166539890253552623140728271489418657249834243504146288350321297840493130193915761417974032179804766411779973020842496
84350987575450133568399904563649208221152856678091798660751936486316891720557914337422753845536624805754980801202659143640614641354053793205787213637775068895302437434001301004972408419310113378895015736004762599410927500529311563957081773968385636981954463571700513673000199519125443004427479355955006576685150380492360113392042315628972391820331462562908764479160032820774981431541025495452086886902574258771766623974706346169132650825396092929509366446252213394238131817380583339661286529727415379123300439731595744248455058640711207498698592248868995883798357110156439065468781073953084414045417887816101866149011407894795064260697596969313448012773967088792585140611376566624251464889716869798884028035689746040528885789848554574565731682729611420080070074313628390075311801071578873891710431004692355066582668959342787345179737701965136055860058227812657596833810394766494910090896462619074624139875870305928343657047248270385569367262762283167702552525550695169963634186449787087851105807293393610277361789742825167816353323952966113746830052125016568061300009426028935149554547199744909222993238936879652982443760298705870959854327257698024543534685721831986546039063315078786518447747409383399973071917691006080030114268295189542605141460275625820850740228404777627975453410896270887540515654399080011628994836912452341648418754181362109352227900858934599200169827963426808829471680469159206996915344878009111231170398652514280054577040803880575525713890554741195698863747847939230511445618981182246341781079758012484570875092406888539033151735448702685604563582660724100418840466994174941224316239281184471726054839899313816759283722899506495258465038559560800671175041766307962711487173857907842777846085584243655488636581792242878798146076772507392641089349530451977173712799927582324724940322196067635337158631271755022993780950532346642931767786635924330892053831167299785816724564773735921938531577802941724403258222844563555306565982792646897596956963034584443407343691163881708340401 1224230609186083090871344528234742852938978730719265421270178816295630103245961447145593187918332077258814659724590053806893902102661318997171246964657624787758566467687244105952321044294007308047421705570960162476549947228529530187087604866776023169073636478501762258330054060063724792161196516384218105293700945094615995150783659487910277872518586584061687757736700457220659137267186628195622696808259780352755800581564604191251088189465652691997167725510272817275063042266001397867863601991296653822697521447734079993651803161126041646061076458143298857926175753920129461236566443626415712158544374801987224758014471511357676839963382207732840712767003195267708380738760783857633410654273756886229176045025944959601319684884235364255743789395343479711914342417534810167249083707295213237295270098108195922614023911460854497980564221378415845669727832925548181664130381896060414235887281003371727297720977505427075966249986036558189618131953877287296676080672447814404378737249637832043691616733383664127992481284411919679118554754898361546678806480414858821344339495629710521840861344838612536096167606280717655717140396689414785583901585882866720759802370514548829196035086197893864344506359157998757905276913908242969156973100044126791940830641643449209404601207378467766615550153133648953275712201833524381336808433885533055348627837369596502806760236465834564845452866997889850841034685023820368072152458637047501689898664853127397068762099107721486425206371709793512455710930304561981510634671013319195747894489546866475381638629477950625360508130484047594087194682319481220041506105484500253033973770507474964041614114601663102027820784741604410713216181571950294507875605383658690100336139030496664607135201681663550410369957079581150627279499977257709199078528142811714360098312915089368371886244967628214032466490298434289966489193366400860611245729820850563504992802227600421756144009528987608523461558698724177036508876396116289454347654568681252229540745368978161659397437368680851114 2275026600958275730031591933966807888903475875662361454307548759543844186809238332661342101725523118441719594954261734417160477825311961755520452599891630793953453155781459587212293216318654166133993615246671173474896093348445058604635516568835969685325140212486632895083453401567304009631671079797146775036509103193044823358175978381921651660716917071055116943067312144853210171181667114018014524004461803401659345029754568214976517829601275333415017657965027566730209099001991570204952099725631339868759629742008016191476022647103525473582575137904122933547509408130255739814848330747776251288317155328055957232166289850271482944201091236330300697078941015755262045114670819187652724377941806230094172380160428740272794777162356026943419944294215783530411859954498109483552197039651673653321531451167744467110192470320407680876797348492593944968643766259727779033641766907531810684428324859807937945921271323473408412036124770154571725334052299645962920883262826020237043043095266923978852557164729241396736043340267919136278950471687239853401213359112329894781389541379593595583746592448369616102995763873265831201095911154086526926767207965082823934478154605930374103427382251599370603342305014856415816070335995785793457305437924136525372428514537946025686376149284809785390806268757086530491808142321221549621624390003128624686736819921285811159880479895357592392406625220752087812517873648214531075542528839106772292684861982207710474543155068040802055804114477814688245560892848042272963067624063996620918507115144056416296632159885738918257708233832357871548632215036410303562450938058624454082168388345239474731086566018905658507771824609272356765040195643784672196551219894545416080284488834938420390457302539683767582803847391999776747830524662391490890159206714043282955583542183703928032459331728048322631919147140994656029262451828475372511174176169141378604983706620902473162340688952656076730553708938187023375175337964949808512941048856134940237882172800856002383391098183871042544
96775284796852884391411415668604858087504637893768817031348743933802911426188253949257197208308408628852124924949933331821512664211690573382964497337746938491971080208194652439855412924204747257241698093481231296506425566464567909151164277087402737220694838916284865456352543884982239710005770084587066275895920189010393343252286855956453196011847419082807472195242180854041227722239250321601110385065403176563469251065969164615182283683984006872929794126686167219497099652195311795864282870334017969621081755941658037697761106067815673867138896248987480665039470857450598576239274416493223493171295319060495417707886734314784794164294449588059373485929796757125950257057565145025166277150247232453218328842406558624431443339287371877070418875514586196921357661927915178820018859115589286655509654510421410301396972484467720146887744746924177620276635130620799568328844280319481402122079959450476931918190291446896878420117661167396284487124202833213193079227440720610886585724503649174699302062701405069547843814437398787217572370093605867953718830180496247966710963048933693807126458991682399088761039811192867301882631130921432709113992004416284420757285746311770182159089741745748970468400992408763219073070304765581467910188116286827129674553558951295383066670352121321235185488479110151955509067852304651949501432531592557213500725108607655375819965806027916995500065250854159012313679030131207152961091165360114374949036091748765850654070594240249392807275655083568742704449377253416871090747704434802036960772714827462639505635237101216444512914498045922568305542286170467446146647209377686736178365249328686321715937116036402511852533030976093494618494123090786360380349914238970027505436728530280248274722980268522015977848072489556807006326095826626032883724175812819915080453304772539588420861178233444248956249774243057955382812622781411585228496535147627563693052796141691998632084520439125351938739935582093484517131421587853507029801561884247024669192517509341894058117939269153163122 6412614028741753895851812914100282131747759843095904563948949057593094375697786064406758418681547754808055876022106992839263857039352376442674865659671155463383424262532534450904330889849237372603070931573829127772051056223869551732119046995123776575742450901271320543871539347619289468625190270701092360984487313635658250422572364781741592563077687217845189836872581160033890324329961060071569260597573956657305459091700395159517119878889453966504156139926946242387685698635384099747638905724061849329519674559657633848052949456052516756122985928643264625038170997887787545776812962888340846335819712631017471547840278300002983088304212430269270729462364614469354190907693075412268997589993936501595704297425027606259072141586230695990220224492294901884658479608322050543394835654135734366982768491066490987995633336093796604414450132111347045209445252667050929308447321995542626859422960017657323481888501697033945582065885163924183996765086671365521868435402007172764322026773466404980546923419150924277730726736062830562256435514666041204537551054765112689236304174595199703453156427467899122190545076537322094942117143597436123221772446996481295466638544988194435668652442900037683086636097010364594953931112520967380487814455269612509781078938747636327165458978340441497145785255721240788843989625333479878596332644795465931450117746676888678193268195995810234436595466499833965395617927860275061012343539394032784660888024104814954953740722129248566897671270128182006910548351484290806910574428163408147719913264693556140375583874104290619562249155574142992668992888816601248676610893555979163558830953938610215919101287706718947682462640060617267863394179757552193102534097736733147715463060216220619479053276387962485266444905629945779730223932965604334886120923675069149310240103543049225539874223900921978567890026395701240629742194084509746144891272933740557357787478127592437983254156775239720696371811513485060748736387725411290142534771625341159841581784660549279757836579178954572258 7416484118673843516727845676634962714548111071662976507136467192537896455457448881887938845292726237417623019550630048768269797446213749781707099965218640393652520713633750790692403312155399217307399692037474818478549177695957741629531786074472486755754631892813065543924186090264717450207848312598663342595215460145112915976409483087111659759182944095447840364234122403004576146644341683177206196492368132971587238142376943230581458388386990526885997334420447658729059732829145484262066987222287191452603669871891507916075911877596834582886751944031141693169151513041978992108128515342058354000969017461350968304661094087646427980535321297178366843411482778971584524479485355274281773216654064334527020933135804643776964245703977673167757861691029403375838535517526699964583572427720295417854592925565691568207034949524983090976830338564585535489894010528839652349173327495032064720643888267140412900068991709346560266822119526324338631663658896914977199240923306273810371076916839943421383505398649575411844354627425899965232921752509071808664508270399291511141436177230832198613341213447342084336053980067288592203403824739080065251598264758732848223424154911956748210808760478079563343223520171277865182439714329657890551829781174378465076523651788522446943493686904303710113444652419677406065739161768779563039012636405469937324251155371747435844426590644408222011559146485825449562142231370915686101500316702197008591693703579636843741018573253966228001350626289914637849827047411502711557410091141541436777388577967903294145574358247334138999826441675684709164837638899395395698341036941888666468129298674808328696944279368692279428541741994536732769841010458077510590514055375750813939363334253757446416226584692159524052825055366809731599237055621949808371726357919550278092912759645147809696979956498414348196145350779787239774473479906559219393950723697800524158714778406211764533305306069885038398113623176977875822539604313784173522205959854783419124969305409515179825009531317625735124
6158659356485648366052085482060205090663818370502227399330647623634187689790570651826136840672096700669743101341667492011690361829907252705326633228528266149737889075916278517986355137207084194864778793206462408793830624078070988071894762591160712068826908694831147590094897419256616795418996974979227339662663071423626395383417592177334271206140564479843631912095305684816117712945774408911040577564379519477320390548334524726608768255743238155894054281468170587396736345991250145924282869464972350820570373139876841309110371451196091237349335100025060248325378103997849172446464968599525299425443016593161468466439924150071407579930271852733166247497615006811664960170509296175820218675045703596909323434554858771572049193638699156203934019039821469033755683719566739087305111375038673991213820806521403918400227188936690242168308872721338646816157730961722552744139184776914739920492777378822450086499942946621705025769668280326949751283355885613444262036923234420909228417199302590042740848819744238613970099598496906384993588646860747410469610177085588343099682072433861716748521728761397383310596311398611873304235565003846627246103756255876066131253753824857390635550222169387648891129209058898854397007778333684451324238776081247857007384839077357013790615335688937586569462860801233591211109337024266872987786147610499548179276959948600440957343182480022349206950656620723620716548433199561393526777412486534651076779880021693589204197615811460738040751957052401763637797669638084575582599856410730017318691756616010375546333987162129839236780574228687334183072667145747533950011747528115860259818642393576524932578138447313527096622250093486470001032883876079403207033529786765199063164279344912692057085804014509251364230872891160471443409575958033979127178354971498727100054391568864637909784474283766385940025983495216662971264322517790275066666135105309597397395510963570626005526454254716318054279702140238873694910205782203085658489612028768871332905380398423614322865669908726160639 21102177223164868795722447331153786297407154237009273207995817107023370803639341210247408834931175441495811560064704246011124767619270561982633685305682140990346235928968485705353863397068381897224132326068530689819841672522242114880802377812229876795681047433252325975010794153659818022398674413682966964660417928854010944837250664607555888291292207140335958782125650117331306673041936265543422038046876946014611763156528900427522231361452158063940896401556527195477455049055230236995218390994179605389537285615307945060136466080719458519395693061981240084692411215465832890460394002023066435946134577582222453191490844209054557378784667280862490154660222755577844802517725496367808233151770642510988746863842350502633156049785970017024248624460229780380118031911781168976659826489320846190567681524610865317984359263350447946503657524057585330216290015171199129345848476791519218024694036380913467591061857410810819419166145865266866079242241004574687956657008844236700410853039159385821015985768716005454397616235835104487125358432748336833197208547043809715676413952138242359024655364676361699302756490990851142952002759604124442384335247090709219313818971092661894250745643315727730680720433666754570788017839507001794536791930518670148616147784514430754588269979574048470797923048621002919605351820758448191869222539637366190289690926880665173779213972590586136047115647061303795694514915461990924616728141396417120315765171300064516952397635950918144351009466904826588181102931616550759201622457211537389517797219424152722236077274510905998741133824392482159277503865733676664020018213266911440950989497202214493690462134256726529184461297830537827126329387454089257140359369993835450354428857849426693840889473982566597512832624718015607822551722783548719709932214007133858585296640605688907390488007615522622310187524716360440537246222293844759051593194408569878604483065163350149375173602431517507688487949741012044065486792749870508490766952174921721290876686832304766470611182938539790828 805987277784173363235419260062224908526588772720678090006394478285154504876630189665064141083959913496680863552131752436777382060201460892535170601073777827138593591470805404208074724609561672615254998075555479178549458228370742412973843438554956996971865802959081916506756788529643597529315075842006157495137343909915819461004517193481950048403052734717664795445877247828297669361270965150126208650639286468031337438215547689711963366436222863813777453592731070769750260229404472622835611279513673913421059438031111375322543447548139539941134278256116196306802535171122339465489634779811079470846831189512593652365588302413446547970294373286010675461254384169660863295217042153778914148837839426023282903527290241700080061650047120487312653604117625473570478209408973307976763755518753389306375166012900636366489576778375099503205821093726608966602779627915467784829936762756109193206022423769296738837960339413248119264958957930159469959831960281531791791500719121342457212560968842424589563240415139304223901324826606493472461245168356988350910733960278069558260875818599953493480257007576373021001496567056458961248102583973519372964923522404943626307823893541963565393241921661988137705426787753277920787246327239505915553328217387211981338858920416482521559708272593792228130149461660379944683393452864326411103909283626743845648680274502559853903382881450294826258413707301992471828012762031525959549976892693772472332001184490768441123366052247248133286474506908071568950171201437496484272045558651652775618198097458139758205087952996418783532190564498441815482461910936035433970453322353074935059888195531095934924049013998908360464541223571445763083644684454553725668541089328673414046269092440753744533904613427329552962684846542139239443844809238030297099837655364247463960963745975879929164422299383579897168942354316265089805981985074576382613161528354208239194375159210793989617424394269125671060005298015657260022569449637177528545119057106950200394514340449921040649783758563311216
33406707748543891057069392011094583625341657022134142656399818930288691256894827039008477180073571565608059337375573718533291142348053797559832983419619067070125902967660636333378209815574837363101608037263619690716580073348476294384835814008293663925414807221973468207305943873348561422781056595979443119910313349935845848495709426691302464288631985207270117037384066401574062785105342261831640536535918534716353330406848121071158196650583320327596624096636229350779188157644286884384444926729678073199341676978012076979904265250280566619050576387935624271621984671840461743465632680243516980899076076762609382511636028553048483481249876560193053416530717995813535481216889672838860700650001692258645415619726969769477737190256899774105583327461318494458659628781345735471704608842821713311897601548176553792796214681283765581283934854635162195426639064207064413662689572465901648286356578985127625516136733480761512303918381185017757072886644792311906782249051760599464933648158240092315830631975895317296672483323648688705808828076642494613363002259348655338243036359631277400145098994304034281787679132050617327219692138912576618525701304854978187558279561681135013706645745781778698716598211856613189298019946696520526420222745766335473675116199922402935902022547502861910403887394662025322697245330851565463281993860950994405652769244354061647569534505123742746913812202944153646153237087582441084910965302426938882261186209710899155408226054041767180638239055177964390933957014483167879241401459010817221634511439612433793857226129524284777151773880733390080311618071418183788206637523523044190750096637133987859180024897528503781014804716548008787131039976728098271294083898497953363184292434778822031298698705249830976149117198611137254682978383243690134529767095005732265644343192647527920257704772189059414128244654189500318466495901894368262138402461831113048231880088448888119916530009563771328108164072117056945723439728317268784606904928015041969330035672968722205519220053202095523411 212505986337520393451226680556238605811774909765688339947390162465692433729115611137181520687962445807583747974460157318378911039418101450356803245195261004394755111457434659324362163429681780870457115783876966457885247990828198098286557187294779642704320431068920240312604046192158396779762345500121203343634769246189704655458117563843180808185647687203065210768017861785469711843788735342982716558058448945339724932684749152240154709915140376765987726363197041783447102165729534737598269370704388627458485037446069832175243647686177327832538309326916129947050544730354199534974310984098983774986254313330926427184272499650954113973478610334000092314197647192333627697001776553024558540290084098798128344237266793549515902616192917718272601313502894423941445949190098971568626672160846530851680041299782589473750550488559806158512450518677835303222185238257400830697889197105491354018056097983974231049487131906925062445090740016527377010730165630449280222307963895631230113281720241964159801857053975437289449251570812647482117449536909540523490304774269986458882027166684802820903226725126899698314838249056812347007614793698815223572323221109129119778544015522959467365265365774580892642061504384883624345580824640075294009304070434545085928275201316114716557247051328765987901683303903786407117276912404934944268558720281968030948878183379959873734078615528454575494345248295223787241127286452233451035544945230888635192993148426610275756271991260115447279597135438570867030225910909765311464035964369095685779840824055740278018009021986388851703969306956980262242839940376085102531945239476505974109945168238001426660563627016860639940279884937896978897783369149256726161135901696793608878946192270105975872387938839516776557780724905469408815579437719285759546512212121634927570178109202105315767795101751353656331333327887596900336201866902727841570220829655619306435414158707811770908915092982726059215003901242692632077182525968513934863067034494847580962268429354264333795821427003537900 25758784573266142419782163811428399568169803000092875527221111572985243284731829228312077637894996117086109435066846350613576593416823423337930630829232291970764954453245409120718556138863901998130126552757905476673940162071974303429224736667100157256003524644944191534277782601163620598912237588152444874730350572561366923837425681589932714279279205472504062039649958982008097988026219875161343472200053466067319243376172575073531603320293823567398088334040895612526885903823999297067492264986376437375645669805173457846442129881683983955215797501976661104565027073534694710753627563909249842589404577606859788425160249929846757862464483366922364947549650552758585829351783598401812732919474197172860162542150411645612889800103127432743945860057444719172010807670288869923991890441259266405963213195070766475489025151326698299367922424715531200271189258821423528067039677098381366329688308370067326966789335436190051696902214802256076423419995774958522328565368962256775325513529283106304269197463280611073430762286129468823230730011241116615618949013093448937920275312418847389324454283801001151027737732150795341247772589312219832755312491229226213285673150999434317742848097438029024778348298584225511226733259418128471385182830469614645053005079204515149912754959148461733381577575439857321454407143326126528026491957668965638919760757029110618632527240757498963769444271593692966386743389975556537986467507624260953108452140706406606201947825481910922090700134754680036697780691485326198196932697847395469347081201734025328551767885172208268817017152197283741823230064475868773438698880691820518497065734041175925831983739413474130426360348702803734636433376776495134020403813542314586955404525007061970850987209343171655175887138016345512131807103990206036653519891975290770469512256238368547093733340143279589174261015746117570619000973590399260558044070581410054817525692081543058465108526459575368717678197006673216963346824599407250771516682771793325313672576623473364336734968684818703300
46211008232645482723168432341933624196342917963346614387825255673339518064948566785658753162011224263323538372064154735806061810497408697363336605893842074469829156710876196477409276656349990815356079114745022529048719552376561310604679527873777320249506809230137367627225654371379190430661681674380533106208429647152483212873599333135901553735868477365512429190114177337007047163362565385343629504218467115642154545589228542436866701896847486020832466753398501710629987032288881412362800177657959059498046638993041672290555030655132401214220159171372278157167196115674130583317903412655166006848347136313130447432662149698858302401459088112612440981411845221766848136153805695362983967961469319627002444810388701073893023706375631690724935379200368445849345935128295179152191520659235637940059989195364273167686757953143037550373232788343826353643977035575701965390929019431805110760276907175312675836152550088477309131306203809426893259582769271168693999135873174872862822999695912286149011552274723489491484350632057310436243610004282599229326864460742999356435995382844104498173941491641713202106579670960374402595756318433853020144324588048399847519325838204999016644429285695719988766854543816708512453830879625486194879793955235401871890684125077911157673523822446005439689515647493926129540433211419179497209240404684623227356053175650231073821475295573814155042728538809555277679154225409079928235130945513800736895746675341782247574486195413310728019587982875956576064756775638528420783865614989287281884355234030782927618917952840159710121692500222692046512877117786435565847959515227117026446744929052686453258962281355876807593158594023970608214756419095654995660080164141599701263712589439115672695392568872228134301339674975479439514655177960517406746919018057439539367915281941066030005756477322456671171045884084984515575648735009345393756039061223222476677811394470091097410164160377480041597602194678125707642167644982340212973678749733080959786296683229328234271983912568648892287 23535144785223664820795054118209360451083439023597655195754608967916851170447960799203368959710357908528514805241357623059718364777662053250971925657246802043284276385940865096330824024227098580833334889121326560506787118938300843456561606820784234502753490623336398155163711305724696370549522501466036841639689715915016923017386667653880991816643003049061089427514871561443938919875029002760992612009672620806956608409344058304446991543126748113631922783876626327014764202379591114449306687282476010310569782172084496348321828034478754708904165372392291408916310908869842096687620135864925911181577016475435408486214744646507424293080864071969791461714305303697634974996135100971301285813600457528753562546146848535360978083558352271843770440278335734804587042772643583268108226055536360774879790675217240338087287428261607584015939122816630447439568192124585154727073010619109987525136196564048578530726012381939791622236362947615369417190366076246203185938701621512123329819530906964522909789036505336244724429654400682684706925655275698265257622978386163547628848800463427300877515313630999337389827674363788219962050190044069823776479723659138200471629377053993741110302549225614159857499011009363994014046104663331091094100834930874190016851177152713577516281103529771661929387180962737523845760678581541505280187868364124960322668231458530637202642194838976482458608174095615048250368519255080755003001417018987385641059139678058777313274458437804088557306391111956972152968732027175855837983505827358286122557325673575921610645190651960832976208388337352488671509581895043304344024680507240899622456722222215876098778794631498430219560952462342117949074673327552528137845340453102544623761159816229795000731492768623127092115789451713609369624779008526563546529074884948316330020699062600468711134639115168015067610841518582160032817537182445896357200104736279812110546815328681477486856855112568819547746351537287104556355495225605395528936137515929303172619128907928720732758729438199381988 12440405276747938918908727579012811228514747029681601386369016297866017809667021040529732765137242270130494775713939683742734878983447691629323118459915804140254573244782962988434052572379949350497496328043249855766946198902353307889662377712624223578317166886437183169659628250053905784806273820767145632884308283247174327550824384247550297826258706202494042462427379477159484473650139963395733263185065708509772489322252326693401957370716560265893330669053404792575614562022671918122978485163771052253421728163230947533008710438378432752025100449882402579347115496622747218296157061743120071212314247059983654274062267326853201436599834736516980386750415838623871041410187744713390807943005858287203465594881736805444081992010896579905583230314041171570166918155112430087389695928885334057840875916836742709624249760637827889620081185326721930349430070907557901238490311036315244668138031336650254396934630720365267132276734825114796838725606400731846909024056699675798332393139964309084451953627926876036913724395924863714556565463433162182791992789073406427546554031809766445368480872854671831245969244442553557661349056077816306566277071357276076729649999164611154032647464298887297836507957151919628917090124834024263148406606217183910882579759081079288419242129199960166337982909960165737353526014825503310035146361790085712483326943165593206626124284329249484526185744886520114326827473993132265767268190395431820149443832122219960770084743167948067768836954703359992616898671215798548613528159967303979121487358381457662936593818074213764467083673684724282041177262528885028069142520097167063740237445005283860441621164722646888192510544863643192645067484739092156394690646470686368702632865216701428904696584117338546535824997175871454253935160246276380309442749048616432151198415271175500256854453672960305259263243721999994367587528159417716117635836015968654057633191661646262098700908521566923967071909771999204041213621690001346803948247225191487731283889490517955037103122520697662288
80726067561942906197800970673828607803786462298310998667700633882116120100477197813831733405144552345844008252555665630506634178745226853503406548582070328059130417010725532021013775551199177730031871176635075446117279605951301406100336516959477381844527653082342954274257416150618324756559356723041117701162923001528292987583784316001797166134349275594899116979538286892388149912005721723731473009518839348772405562151948985050600629103993560488621363628953963769622272347553023185740432596328697343062475483120896873330021061868869275437528693886048815042878514946808507329053566444439330201525090987276640022548615399910779655338395802239675542771119035531143382022223199354730992506623993898554525141678274288390860017396109229673997917117169380513003317323937799434005744661835999261004376229919345515741599418079215462657726487802504962157952650078467822556790533188915089384413940968875952163945044045978858086372831319990417834063709167678511724317389163607555049050892847637370348484065190521311323151453465976172203982463685099699360507978107045672657962098698270737777816134829766754615058866751239818228000565388589930561845918255627118656882387890626493172707502407375134168512954843825470316429655872959394882066238329123030323988858933720248707379310275499100772416488340907498610268258155732264421888515415381437156647758986894581377556339718320818487369740297746605980985765053466815044244470841983248877772871653592250045664203265179208271924856616645707673952157545558992697524822372699397679245969520694466643317558459234400651888665547490319309821511928306348951320989974271230884067343143746337531202341400667838803831523342169174924381481267224147362377637470605250147696717720961947982933587692289637476659899655273141820932277400181214008089215755893131338031758899486122805831637230620904575985853407930425368257637395746496952551247307197069011834354529040103220766587497402490914795011076282026950137083131811085334781336628862463682088843730735430095588910336648839877313 5861364899073818060455360512027362558247959720930673379036386415925468346259865453512757023443146652332017600613848235605875711831034865533543143770350794459553341482454981838089761160931576909387176972156836137178493500099044051419477965038643533150534833929182505924123528074523423703700363670678698365202658220148728043284969016585802586371203451288107250421995831486626220092606933680252081582853527850960374040889083639988030294440104723174307219812003707462624798283525110330984076221724798979689481424024747329119680381257964456543234980003193109419287098556896761803489881225043866431384305862094183010429205660731455273439149201858790660539656434633941813910086558524028714848367676425863797087058535969581588921292590030710390571286517634845215742859343174139268027734598625546344442696817519070067410953970361474411615877282731410965472517150734452922195760744328385386099524021352943697900782817705170432884711849778407291925972463793249698445536957317811516729262855334808267243898948296972438946355671610030941666408680675407099154376463444452581212601885048305253263791436451510052804303841146278354211176099397573803267244920980909580343598664114391000762188056470280891424891443346250666642732529274797028587924190650253523702199688634672619963675368450632195068107735002761810416063707995579829277809323345851435089099111971875139519544148253786394546807582373692275478841686532757058644599385502306144706314024772866827434429183539609535184756719535527916158005034255699974328736554086426194095430357236288024221206428714197042996156010415778117277071423294217084996300488091171109002908957017357173361921268426986380092214949650608843036196206469925522522942280996783913528551406089610996699246313831243736926120267065045848150227202441258060499674626853089969751141639971110402943468364408422412732156605359660740210821803087638385423068775876260436257758870241723649413963049589933016409458799708378847594640842290503695450474977931690455272247306747359293467446158604735906432 1894434909569636718934633713058256315173187272055977152569734796997418097954947467507424756534256339875208487943303409543034447155802467407885897981131250587341228085534126148530095774632860962043631922441325343502395672257417583013414144653679300843643250099817321587533060257230901128984167395763323854199035054227871853566615073528336936561594793979434651653037716218548034483849097312055178611047302216364879261182591320280667225628763114500219830788906115379221276500570031909362138884385138831435053313231032911234624300688697701879265903840260342191325680846084294170853274070925262918136271941717936057702611353590760264910350908007461017608796615346523540058988167449992518487024446859004438882310531542085285036043152592883575449195583910362791172856839852162570373269478544283277633524498598158305553851613453865194495053729302962901703553229444381103595252984790145070858562104457975534730047732365605755937444048769744485827845061817037628182186427770204522469068624647472264064569426544680972157758691121658688990513514036509414627806006329894255649821410175487287365779725218517487681111748974451116437946344069566733818242576313643547732475420065982731858086107426767274910152670040803409732941266245035496247259723152640225748590782885836636990775192021897875026371129040762952654189122074070134240045230662052660896033323152221926198019921578524846978515200779832596652515468167612680596167499678760514280449094234901145700313185777950818739079118012447925069095762787925518663887118214015577714550891665097290312340698807209997250481868050937340630034271759662964717073521541874669379476802623614329821363657639259910909996822625515675741374093205599131494309759229198242434227027018104916686303413694540708849131961812185067490927492680945475899099672119232379463799164124178119767218025267135831445335836952336835847867567919673598311703759921807390284869606013973972780270242057156727634000117251115561588514179075718273724185093936202637039566232682192230435814158659533007660
9022350465366174997283847919398349945633938016104425583860172324176263489361275975009667593038004932687667364874105163892462496885314014908643263326856000372859576083332702726365803964965612459510217293945742324165460877668241497276551342282668646943574832458113160585492183415883647501781717889558978865392772224541065392167546673474741614500160191418704984200050694178212870182632344324620453956363326887681039920226446997083272316385388521326434541090517952433950525433228949943207791117617336586597055185835636143165579863319669227381265651295860327700836191420851833096352355364158455759936349295324840755532195834786495480749596555898829057263924800464318647317952410319136211113196702055469248878152343235293998428488219981553746620981330409457732609587036046817990777041527282479214574080206817435928277059939288849600459911021713775937897892405355254315126569107158564247999317316718483427722955425855482016244411019914948488735880721210735665656305032527979084088502142907014707379774982155237461271110239643442182704616997425509588170510879119957191445286648203735778500178463935047229793523710938940856892769255975677373946536876820289525221586274769960397963148312478510933866595260166008038569943390972312367027678277018588806705436630234745017725533598917717696661761449981454029132906017277890180578422965195412928393259881214603112162460466262100899824011347518062666252858555941834289631186666429499627092672893054716300985128012323278130308495384439455957536346032612317933114304839933084600855909538890414149728987486776084216057289261871588036905157527996581095566604827725585895684627520610720098597049758606548020143513068135008827983614484292230055034970426323155692818336187550647113038707593592987411380313998875932511436736623239997851326877111264915889575138246573980849287148083870425370090874853968611767112024269808843297017204512317422795496511790069287123620934712807235016574232281446632747065243918688321172769768658035768847021747500202496722098981212122723426191 1058699994567456386051988099789906882282897056928675755897254621570366716449454996510283857083638192071817008530465247043578186434946918889294028568301273439962763818506148971675827938163894743053955607916598088803436520189938566781998950556796212499308212484403252622244410854944843773844980312966376343035622063664095184066333372673908829539425847847206454811981326317035401090156833262316513361800521426521383595068854784432026040111597545873126659983942386459273309399974438683726439761945113432389174952261210527484801478796707480533295702234777525452119176262505758000228932395859429139171755900855071518192355754722709499778279693842086613937782438036359676996800592750727234184052949718377088872899573216353728562388287307027850207917859490190081507157679337228065576520106615049007029460254789103989366854896829904728977024077299283132011778098938254310701807712024600935370235989779568324535443330251228660632530337167126327167912382026646507946716969152055758403581590759923975869874087571459658748959086489064871939742478982007277060690969983202505547220593809031772514573276417779804628787991237258838355748174562331235599037687611604915645017218355720699759416558858588985701341050750427674194123540281510484826183918089145486307559577717585044119195043067814506514474786200819408641903796159506347022266070908808297970362892218690867230134703308210585876923845041275614783063315239645775161182566313752305923434347670359998750065723006373705860782512535436814574474916656191776450075760117559564015284594489869981194881114382637138897114031534838077775401813552085067025360920160057552244831151970638692864423056108291008227979430237708815473134005273435451176611310212116248360141662693085865512927552718250808087969470342138952876789139143434474670501618870770400636743385571856286514152985116257532012850617197129445628408472091102178936374730408150742184376561351372601819061860584012814517350674350028052326401079723189881610955613598594550278154987155449961930333156849417263850 90291778555653550716493489542237092648376821343798066802396897320460083119408035125492774024615043460383542670677842854482720262234910465211522006855178566450306801553545149409367071043366034468190885139742859118664420300214443797916430078105503270756280470328263948869263628832479836714863450254567147551271091848613597295161427210316689678422338676771168867022949759981033926294153106622753829408728375980226896095079451901665967219962815675542238174816566644168754300066032630267719430542526513296155344107610505357310272044998227163107602477626814962864721885126262509683187862901808919508311763657336634522653548788245491512003117918076084793361550686098426584796821463542209737852661794754725450661638101737144533890630719128116166022033987180830784663532448695424837519682575788580641992175491112019952780415124223753556516014129256436602247328153727225076752804162498634047964081458669545437057156523163544840185411186996833128555354855257353453509644619678610825845149317482672436540525725916754095931545261993786086245740912590651063958878198048186776177585955323087390626661758696600467288998427845007776090373208635964455924721808169796255326531528474320908057724474007272029423689869138010576148743138517158964539044652950682900907114535359200803856270595331575177719023985693615634599353953547497517828427555951982457134348280741098108778513306873950292762724992282424481810778898240414609079188685467032694027139207991169681691089307681827757093331790950778147228110693442952443348767327939497054118087236782343905763684171896427338823079523838936953603935676502049900624123670462843014651117999508751852193500562573635554259610600582586095461030961795432841724225498060925298912635795202587530522522877561469815756657208161699603814540000180968487882246505488910918137135036046842825020083849435984261455192124801811574873036423197033315924382761958950762329982789532467565514400279651575019202638122056269706846436324142958722187158801617988013399462193181028632790588614321674250
42034625645597317079759786587567597620818135981519245116964305703195585958588137015319643208245432495445385228776918868137278793634039559082988064708878845215760464045435638349276604395244516982648968811193870005073490149079749988896567680372252938535440043711885833247299877739281291945721732219548220032031361897433419552731756188491608326088200563733880701894506679097474652849163815735196431967789681086040936911921259759140949151028601293289531220073210871108161977945133946335633911965723537384129641123185144281108735611315874021499737099153455246366735472569884441236762624268813540966600366572845616962438136560377549611751529168951940843130701211441910032966428554877803642477806895439169839498006165622838076122086892663854008685851048975354096526669750089694798655644849811524468234431980953265011647901904607257484260299377279025716663748286465855327746591416567251338358030334965777613873995033560755074094018961728450653388971685618835605349524415220665996064057644276171179883318244148681424281495607004028836111527303639653542646499001391727251684600256798372206030464612151222381648282338056353779638751829472031597084040184284856450132453699705265626187668901617408812678209890631896542839806230749056471150280344691655112588170467225917434916720983195909005227353991431589051370836357198884276999781624617864755660032200090322660887634120840547002704663072688612325248736893516235951979665246219640176473804111847803055996402592598901957659786987402990527359813292276370341857756399112068520078347241912655854243544103036343280733288656531684215269564624026269009850991140630471356262178237024658348271863517588987526515341583602432034531157650806000598353956255264515095785459727103878142305598828598013631276999877805049611197369783793459410118823597772491040504676767558953022390840253609096489921574511147593494514798226210630688817315826047329610735034953240721838195466860963172133519087929050342121960466161718074272809726634064842934722244243233313371232626401688761869203 14318694548450178955732351939004055266562398661702795582425519810966507508854578807695360148251306221959608022229782583473972069368827803090486843176421946300758304055804640646350451574217622333462637333695107471842536420426307571744050340977886833263243402211201718040174887618334950559341064884177183626659551835243802122974095175062667601895966119822102014089697200954709670703122405808224060542246226380066742721963281039913720136183196909018640046660036828149751015464724416362123027922215667451098805881549847617518967353533276586076219206989092983976735291322426266496178572094944079562926758576758995851321052043660453029305185123174434137405231656099859171807410123225286587442443698805523052163194439851740402619473556113431874499707430440328967435073617760408980909690113551697122565359752661044695205174417214058952639858037928539771569689381771011930748458443203910314170400449759775142177259696608615960672520283038705347325258932766329386266007063224434367170242322297324510238400739648039102932191663551030780817913512008465216433104478646835232909034121830606598804331066677002015096590150806609968008188901879526887996402914511695431164804438067898396652670162587135304605368494894011155311574290644272131809434693932838650350545645541411492266863451082436733594122144246826208121855480203014748912125205336468257370385198878125276766090949423005507565767450097409145392650842132779705398036118330873918471908594709300830522117006970393459722846209838558355747425205287117867871710030279448100684435606811188471296325847574723832379715963751177784455176172284683363980454246986142817712297387131169677294828557137362786594662141014231730670327101372124317917223429276711271944805939461614344495928850457673121752822775772826973312002865692332622120290552734056511165792619412996081476985203765802430125716713507892299022963452891946713297536100753376939290767181104499742765323346488336921953739729936390013452688584309139846950933889077360963752270188632984752144816994603199233100 4571197952220902642199822260426493649174810582709202279035389490325773583696103638593361743562743193231240756081956826958411672562481519294584659826182348040731696539364525821109014958123599098074636455488258018399601145233714028974829597636751851506383165461260945491930881077206718227733809267062263893043331978843529490079522814978320169067785856719003158410021831780988623287289746342834259072800282262374878844964426430939689378224698917053865591830977977335164752606209112101990896596068473347520334218852346920594155205772675878912672532597016053201206400176298024294489656125349812623291181821859253110854540672818604642666783187884037001940338411786929111179925015039680202133532451634817597245820709721142010637750091163778221348936594714731062601416058910756823859846509466385937452069699191666042909860547578174127751627988561968921554572409169567872909314025796042870249840392080634810080294767283114828391755042573541855747541329726309111084701233673963662274839780266337938654555897865710637879352946582495222470955558041080165095018998173173159846782186843305288131059363326556540086679910935167560819550476491039849469228262876401839146953378291886160450076613263875094854180279611008895691314320837275588147552657315990677501507166948521124343525115740662851885560364182407962911286638750325126729606979660946803787756078220784506691812096267182601073864824582018953124723298409658282240551932951095510878096999399781099349182393606838852883232721982562559603741171502918412089894118997685230632518536793384656581578444262189481829840774492154923474661940666906688030248811541197285916358878784030362021788057670200721228914618579994312933588153960283591269950692938445607566561080156280559559315393298039082228289490343747716749870005173203032748275295004067530267950701091570860738672847122281103852689139506733255009158105467859238497297821097803409517169521962285291268852157160744181660479847051968748480614600415494828230176101789441913305487597506279154665132704288880974940

78299676090881850562479442596885275232341121074278284851478038310345605992517416134561135341691055886772955171566391029800095806748004727326149614594477633642501025027105267183304810244258038228176248773230874083637980620093474929422222851518823355752827203418869069433751519250333873153097071840500699588916542538447569700689930504513184464145079269997987022553668233664350370195968477428116268848290669358107858811522148619871920710981672188608584950983636266602738161753861068645022137817119400093
33097265104199847767189488302651072543382318177434155466448252805425338433107915048908262248908210605754161313401514020013238362579336071970484568247433877586812519908303621039304597746898538004923923337546359645832338136260806672116305031259289676295245048442077286436335999136942798650764900279884341078712268507817476698605715392827762653005304862900768755495669034237632813800483492727251821394658766505741199857751899054637489537901717408616749876825713942503519167615678504972110465590743589443
9039633520156376052571730787353957079218872301970532684737975064714828387766080658480879047539494337793677137312234019438325177991546539704031533877323308344149474402822810987150317424359078551265796314678815105692150911475701567040681691802567308571921285556799768816593159863834666015001095780223873524280253058765456143028713605830375063004586136882448530457457981532186293023299682526217377981044598900399179325983760427538804107941558612293290577811036690795649204510230495180413191241919591931
-1
345842586075250271329088769074411195793511356766356527703943320748214365271138843316516258596305375028542576680157444882243643142248317696230661057511516236952699650936240331966032021713048567887768062203966070478934410111722160861271229518949484333123957284295154581562705552499868735559991458433681077989986062463722907020587333763822524960016511895616189022380422921068900128254086668985976564414809727660790260268758659004391480796809495625540323266397876403734146514134074566238130439903612537
15348719271514799433842321797859554467814730772066621589799846025233366813265861892039310804110788794332439462342882640669701285931800527775380896000511733356643764536626810975968978888178770741349966923101948427120897671615356056325256321575097927871563213098334622325814777811944516732961149712727202431023929504767869151198954481749841131119057890374377884205448114125940593167670330502015253855127269096179100009294709341966737209579540246593117860314357986022108349627814476930358381574273419139
28728904028390938914156967079088017722688187091773547521319035516456899488083810007314403608864620463310961904307727019313270206486805654570695060662937057757479961855520191690824360362753701494066750891955731378582661279403074738173298502477708455101416811455414291738449695238597379444936341998284262838648724405952400496704034403625221144556679983883479964945931860876387183116230403891183965239047830442433724986111814129974935985568911642062675252992624546378365710213787090670646521825174304831
32454982476168113503128623934856095908542906720926673867332114372725430950168035868658685349991750495139364137274536490156026645338311791401186669165593337157285046496651954352095827455003764047049976002481015890242989430394538551670322689517626782880896242177870592325552815582417040884548255771629553492966719603684419526132318653162420620189935135940293661201457332826717103854473442219366012490280459301445038705063145194278882808329858541143564361692598343873304008549795689036557193665879213995
59649030133765641301536952303827256284404117457008067900601727216701103277257124326268774170481334749522093819176526413201600969156420065141885345899376919941993501075267014556750707900827638877492792093513765617385074209138498984801423840159419298856581191434292450620727995643185026734134960512998148170269282601724877080394092620068805582357663445183114233556687765320240174791814384848769967716788415919739456599503140656755246564285380626812361070394135603887532529416448483300351439067115491629
72579315571073433647251940755485905519831002112522565153699016653688657019846088445799095126084773051551178401160027429648878285287660551880804223309566823084169969860459355489791651437849537256359630534034267594249201733810572183765420029170840233463255233381114571837650234144211281743417503112511743626923284974539750788245158006833580300672567927831235726684880957261018123067990357928900821615738184219991803888329354150620144054935516045495832489018163428138154428998737456807348422412222387917

提示

【样例解释】

对于第一组数据，$a=1,b=2,c=3$，此时 $b,c$ 已经互质，$n=0$ 是一个解；

对于第二组数据，$a=1,b=3,c=6$，取 $n=2$ 时有 $an+b=5$，与 $6$ 互质，因此是一个解；

对于第三组数据，$a=2,b=2,c=2$，于是 $an+b=2n+2$，对于任意 $n$ 都有 $(an+b,c)=2$，因此不存在这样的 $n$，故输出 -1。

【题目来源】

来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）。

题解等资源可在 https://github.com/yylidiw/thupc_2/tree/master 查看。