P14033 [HackerEarth] Harry and Ron are late for their first ever class at Hogwarts.
普及
题目描述

Harry and Ron are late for their first ever class at Hogwarts.
It is the tranfiguration class. Professor McGonagall is furious
at both of them for being late. She now asks them to perform a
transfiguration spell successfully if they want to attend the class.
The spell involves long palindromic numbers.

Palindromes are the numbers that reads the same backward as forward. The spell must be able to reduce a palindromic number to another palindrome which will satisfy the following properties :

1.The new palindrome on multiplying with some number should give
back the original palindrome.

2.The length of the old and new palindrome must be same.

Since Harry and Ron have not studied any Transfiguration spell
before the class, they turn to you for help. Program the
spell that will help them out.

Constraints

1 ≤ T ≤ 10000

1 ≤ Length of Palindrome ≤ 10000

Neither the input nor the output shall have leading zeroes

Input

First line contains T no. of test cases.
The next T lines contain a palindromic number each.

Output

Output the new palindrome of each testcase in a new line.

Problem Setter: Vinay Kumar

UPDATE
The output should not be transfigurable any furthur

SAMPLE INPUT
2
6666
6336

SAMPLE OUTPUT
1111
2112

Explanation

For the first test case, 11116=6666. Also no of digits(6666)==no of digits(1111), therefore 1111 is the answer.
For the second test case, 21123=6336. Also no of digits(2112)== no of digits(6336), therefore 2112 is the answer.

输入格式

见题面

输出格式

见题面

样例输入
104 6000000000000000000000000000000006 6753562912709360626187920237592289736129319478450361063206155476569374525474430786886870344745254739656745516023601630548749139216379822957320297816260639072192653576 4314920689266495048717272261061594909177115977673656394812939088509638561159848103044447444403018489511658369058809392184936563767795117719094951601622727178405946629860294134 3175962178574185975388318964333860488897764303092540594664950452903034677988840683334698138835795814758712695713 22477548128936802105110850646258628472406299081311034039196933805664046650833969193043011318099260427482685264605801150120863982184577422 462675698728299602761321599149107587048042961042220552902838040919625449936050294351743146641347153492050639944526919040838209255022240169240840785701941995123167206992827896576264 422641288928886838333804768906879033373265265879604104870868078401406978562562373330978609867408333838688829882146224 4774 39283017891549257499459357081997825349020196212073119056774064748582606646289607010137726452029099499092025462773101070698264660628584746047765091137021269102094352879918075395499475294519871038293 10378860467609759785338379378741909885843713809799324377342399790831734858890914787397383358795790676406887301 2202175174171117040851662196480846912661580407111714715712022 102297564637974917719479736465792201 8 608539415415549838522270346363344397258902476571333175674209852793443363643072225838945514514935806 85108763508041135934150835659907637615065081226910427403280370034927425244252472943007308230472401962218056051673670995653805143953114080536780158 38608922318342245175716981333798670484816852199606499099460699125861848407689733318961757154224381322980683 931489677371221509040137411303217565422172416578592736479722163021565003466025520664300565120361227974637295875614271224565712303114731040905122173776984139 9506083782105855073823077769677703283705585012873806059 66 1908988037069217797627158845656848838752450573272134941957412216202297447922026122147591494312723750542578388486565488517267977129607308898091 5614031277981076010251971312068749244591289606409454663995213099134585733375854319903125993664549046069821954429478602131791520106701897721304165 9553860336187051103004542499949816393346156172292812478637723725376813640358509980249012006390838778380936002109420899058530463186735273277368742182922716516433936189499942454003011507816330683559 10050318017910359484692903033794991942065956114372733924449938329543949557390727290504179362126397140509272709375594934592383994442933727341165956024919949733030929648495301971081305001 53918870527919636846677664863691972507881935 741006443734721795689552159916210532197682064336904851297380923187416385501264856252691331525133196252658462105583614781329083792158409633460286791235012619951255986597127437344600147 94460743790022699622009734706449 35587170604130296093543643191094562591774119138749313879388400868238505926852836787266297079266278763825862950583286800488397831394783191147719526549019134634539069203140607178553 7235178941643548733501457078993946455560626992965538668355692996260655546493998707541053378453461498715327 360269308765240068549468323622470496546425161373161524645694074226323864945860042567803962063 121089013485822063610574200339043342453811315813397544967210137763910411864347707453072270354707743468114019367731012769445793318513118354243340933002475016360228584310980121 9339 9302799520835965630207473016757889078031036732215122376301308709887576103747020365695380259972039 3828580869337437139642029574649123181389245100133000220003310015429831813219464759202469317347339680858283 2479854786006437581093026438670819816485015970628950598260795105846189180768346203901857346006874589742 7281779798898052024373001580004753142013004822024584084254275775724524804854202284003102413574000851003734202508988979771827 228660091269482827867709454223965747569322454907768728284962190066822 9440602284311190002576919876511485766914367697609076666709067967634196675841156789196752000911134822060449 776653767356677 72640754012801520711702510821045704627 4953511007081641498622523273901506979289989363604496641980490550160288498344438948820610550940891466944063639899829796051093723252268941461807001153594 175762425505297768120328746380497975137809521327332386160919150949682286949051919061683233723125908731579794083647823021867792505524267571 6534356 471404833461554669675643002538505667340808153511401185785160912490144325132606968086754457680869606231523441094219061587581104115351808043766505835200346576966455164338404174 60553915049674309660458285406690347694051935506 6853401771043586 8089783879808 72502480626566341713082901081678821389354122779140478768086145259388435059346255264395053488395254168086787404197722145398312887618010928031714366562608420527 20009809672144849844196809363895017198267593997973504194143642276185113064475382735374800164546100847353728357446031158167224634149140537979939576289171059836390869144894844127690890002 3122955463120651944681081298868202498118942028688921801864491560213645592213 646863574240272016194996942023689282986320249699491610272042475368646 73535959799052102063694840844824277993984080590918287684898370719630148666611666684103691707389848678281909508048939977242844804849636020125099795953537 82965943782887604912224602320642221940678828734956928 86869726889881680484429645547057643537328308669711796680382373534675074554692448408618898862796868 371235702607371847689639697560527663243604363749429382454323454283924947363406342366725065796936986748173706207532173 4774 1616161 704969516022227361007231074801873471344246498425524894642443174378108470132700163722220615969407 274405600403208699235481072499236677469609951730854394623862707674312475580777085574213476707268326493458037159906964776632994270184532996802304006504472 77932078207146112887101079076933649846997801435943855283182705261178867744776887116250728138255834953410879964894633967097010178821164170287023977 20271620482233272454168048835247475657697032380525151158933678625100082887015080715133948236090702020709063284933151708051078828000152687633985115152508323079675657474253884086145427233228402617202 34081199399126479328756046968968598707855870789586986964065782397462199399118043 78052857257917396998773652840649665962887570229138137614920186342059449199341214399194495024368102941673183192207578826956694604825637789969371975275825087 7260141535773320747681893727064702992074607273981867470233775351410627 638285920347716554681051891810973912626656626219379018198150186455617743029582836 543345 9 7768732543575659583319961714025801697007961085204171699133859565753452378677 13299960643054145034606999231 58511585 96790597668189295462767171868078669618596617556302598238616613409682628690431661683289520365571669581696687086817176726459298186679509769 230507280235430718874221122478817034532082705032 172636088708998426878598364715949517463895878624899807880636271 2000081719909339099171800002 7317137 2531212992121352 646969940951072332871619121460736522439646746299678752674711808117476257876992647646934225637064121916178233270159049969646 660905870466006265241420103404062272751900620249995037049489008225522800984940730599942026009157272260404301024142562600664078509066 2181307721411363866352372656802232482385728877353908165522125658899347011018101107439988565212255618093537788275832842322086562732536683631141277031812 53066182854396851852907600732707133763969598175380773465558939664150766816825373551817682477333777733377428671815537352861866705146693985556437708357189596936733170723700670925815869345828166035 96464542097754465656445779024546469 149527170061025520160071725941 6320319266741314911102125735015867190239803157770980314890513019920073976493380371512213122151730833946793700299103150984130890777513089320917685105375212011194131476629130236 7459649041790556610415243575627557265753425140166550971409469547 453863471398174292471893174368354 55220715632108856492327228266282272329465880123651702255 1608928855489897645357695115590662776751329200087514504037787743130717861083002965692003801687170313477877304054157800029231576772660955115967535467989845588298061 37050728425738911997096628816579374557491994905117828680584151100115148508682871150949919475547397561882669079911983752482705073 56642551600973062450275239070067844019181491797144284939836054048440304484045063893948244179719418191044876007093257205426037900615524665 3749838754493888791698092939997963066833572073872133953248359267563179528928205410025362397514282882824157932635200145028298259713657629538423593312783702753386603697999392908961978883944578389473 9991985735498493249489332973255364764237007066381341431836607007324674635523792339849423948945375891999 86877868 1938394259418417794087540928003116266683754617389999863689999837164573866626113008290457804977148149524938391 86688211838608073655693504493771569380786558357913474944688644947431975385568708396517739440539655637080683811288668 98523119136913498179303265923784736369272084548027296363748732956230397189431963191132589 5542594040535023406232112326043205350404952455 14990645110626769414567165419700111376187371940801477395859377410804917378167311100791456176541496762601154609941 87289691189478749909903488430990994787498119698278 79066850976067905866097 3994872442784993 1480636654772569676474463962693644746769652774566360841 316618545111193672441915501665976739685327658135389692242519226622915242296983531856723586937679566105519144276391111545816613 21082636593306856925160431553365493858607957633247874233675970685839456335513406152965860339563628012 309634189044994499440981436903 8165015860107170398651451090056064606500901541568930717010685105618
样例输出
1 1 1 1 1 1 1 1 1 11 11 210012 111 43334 1111111111111111111111111111111111111 36444463 64556486200268465546 231564613545316465132 1234567890987654321 12345678900987654321