Define \(F_0=0\), \(F_1=1\), and \(F_n=F_{n-1}+F_{n-2}\) for \(n>=2\). Answer the given queries exactly.

Input

The first line contains \(T\) followed by \(T\) values of \(n\), separated by whitespace.

The input satisfies:

• \(1 \le T \le 100\)
• \(0 \le n \le 10000\)

Output

For each query, print \(F_n\) on its own line.

Example

Input

9
6319 6207 4938 152 5551 1856 8450 6260 1217

Output

1751514501816964425119544362149028485394105895234064019554972433831277808315045040270863170784994246347655271745396928276001306196464149565444492708630475545910105738431247894585444617958640728257728590359668208086401211116347334427536559098505794808296701056079675965909020563722198146855942293685805470551996389356991099019647160562416788374297507983290386171634426420110477407193328911928332449352623501914565512967245402116148712655939911054647619313195691809022984401434611033010118485972532814606165162632033948134999241915411820517366004490686504299616820035921734838892092907500034303910250556988022798054218150039017459644983190517237856572861655438131340044266914576830251162446590016409976752222072100915113325209612800306057341955688040760994418587934001242174164034546871069691186445340158309958828946164565894677198850360966383669822096770975438435400149739421066864727937272191842950796089534740489099750468002964639462893072763994055594741882196660211234617698050246995849375477646873122719422222323618496437608973452938488387099688152820010136053273617541509064090708188541844572316835880224764135686361073868561573294687517119898718473605416602857278301004818780212910570306166285961909824468213935072396378064302132197696479750629884474289466289806766761025335831217500229210899715737796319215959048381
6867489901149861664787734138328155842944694196478474412322715433619740451902764815997211713687891424821432029159306198745746565925305186712508667681050277980952699774588446509336776186453452141111534838111326292546351543840911042516249251365793669603247666443874754152475096894588160510228476793514603167061422189862079047737151195080832376708653383203949862474494566046773834981130195405901659301726444485328056704440496348744513180701039668008214069698818409094840514360303737375546063786531388852540864640297483294676101188638602889964050544774490083487793139657725883691585522702941665051038944134405654870593066453518900110449466000931206125739447012784375384506906678555682529518773687195217897915554077013554411574239672414617652028655964882951292827932690686259177515455959729892766622429582000607772653020686884349992127039934124963383195865711905020494658240907188120221824750249870082131149331884849285698624819059792422620713810696846466866222277080150231145560043106596288898723945727865670953519712856962847409869413291343836291530229048468484334470626342014332252451641883258043930596043213588512757958396938076415018106751337416322985416841117381166863088967338302713251883622561476340227918518606878355666348241149309854023012586322734642614365293856006510893933461060280577139938
428038222812840990470887260462610714151405617652858186516735497295422779230452721828593746756673631140392905558511664044264546999870336820714881352540644225250347879372921438042688598832094811876247577622026840182054122541408868649948182373688475673897737631803280422992399675177136942807562422647498316867044442860946484535072491619866942210194864272279678570762630284589748846902260097434128708261289603517974505875974638200095675992913474284010381839827143816793745900639081292436860099267954037725224139260008492978727104689375110398958777876183131682890503397419317649796074992287078269865890054472273260783039443522195515504110858077380932144108272121746084659264937538659569809150177498906700312638765277664379814474600602568092927650655746030109496044840161998509985173122413579909012370586503491824795540697529478403283850383665605393923263359752073307954518198651084443542261574247077108365811809095697499262148368737774178452358928899974144180133913844197704150369523192231460545147557329036864813850309732025370191842744
26099748102093884802012313146549
55068852312539441790105261623463935743448111440525636852751265843871794456704686859347223590240241864713562165194505995647142274486968899560168150089922698410199331695360738971280789982608153954011762266866299156645657954205240768978169330668620925811713916886039825906382022652779742367830237325731098903755505135089611199712952011682584955783887427247961678248078187197943297537861889144778573605425334901556270580893821190675049572794822448809574792816251136664119507678322109536734488390407329488307875738821722964096939112208999810055624943753442232781487802812495342312537778548195158002614105041031842392469331928862472317504360689923969960096431206121228696699328576910929439820095686082289649722055090176608076603440509069113010936237628033099842105600015645974204707254458407232575130736614643165541525335893426551024407969404007404568622527960230722767203241104828092920126839471514921462723823647670894589634211112996029972474230310502090882765833413278650526090086215493487932968692294441755861411258684901450980868096146287465345029253096756942513173866117391641286941096925767879387013542956694412737912943018780640586403443025259810347186869949
3400754659642372651157043742341884916029566542129556671569787694081898756868585566340704002920553407861924412280003106680546173892124260197948938075010887446691540326048225407848368318806662825095647452354842708984314215497107209526451160706810886147491106787187567196808444259662104621702266928520979745217669748539864833391725380348943609726850855975559567342026530037674334062656885317
39452552838584936580229964469411091801546466012315110900952063151165301005761874061615460451650539467014520701306125902355739957834984181217730369327091671563733930126515820368151139582847080795980927470623414785544447272521946905653523688768382266908802541374356541443420172805597858711908536030058909979777705415372658882162062148906455152578377986178408740551011122122011462326702896217766818196063462311945899304612934912105507937296715321308616452017270054499368540540470284621773606190690161178591578894777769657547530401163592595559784628858412407197953803725845462482979152551292251250511102676259949616822639335334473615209870144117253324627092508641201881581414098578704602534217341993306842535054443307219151567187522912890006316842833002684790549446462195561372005293825606382533102131205760917508121308575743195221301091522205291253908848409348357880137869931316514624593654309346974938268762407065454694116533179879353945318736173486036849418623370876816672634724110879989395780012665560664198125723638350342118458693329886185722261557781791452079463623647660823504388461927737195474457632604539269654658892222373675297601262514644553604565324278366154866996953983429748109394696102353248193836714693966103974231116617878157780490050157183604431653081886464500640607586279096138578109911821227338516759127561409250592649453456623367763390685125946438003028402141007699457314895400135070793339345689860959587322198685453517347917395783418228128946552177077952350830357448014117005202203553073830174044388873605653147208942845343748388331207376443158402945305491746313749258132661319551804030600274064647159308668962098460595473095467736906639933633966032237258245013965736373797929300382020747935409505003332383654686739240570756436586749255231076340225
818734257817028839811597104561489367001515643107919403473922431232085431744253466776931480378322247041053527766622748475306126250010072037343964884249396137251706806710884118351950927052724263419871452499266442819420312021136917713917526396290810077978295143460228410269974763767207710611487169838655386260968457207666865026307134340912453638671323904441647123751070903068681265983190879687229597521407896833923604760592520795299070966576696286690561003908390575693643270347294165036069659490019481983155589316457854407689697643548090180440313577389793786457570465437411410925046981616131080908389004714852360593030048077811600014695670107469977491412319600168442077618277876956045252052621819450898179692788004870124619216329030754212146653830837913056934540620159040756562117758066416898443926423036996798236639920338560345561519303699726033644758806928047989576363924807386094238472557104755588097885401558107034896412250466518000662218427173719818565129734949310273792428444436912037484257647784288468375978635061806432761488808334046725057585873475725108879198458266183726564237746952164250210766297853145226089560187678691609321272980898114824338609537490468469194919454963547997232589344431369724610828788687306194311341016719191710571118521272661955004199168903507493783520394492118416589419604262445
97380765026739217487047684853744233028979621934209946160634673235401499499333377654049187877329534812428730244986940529968812071743142538634743966362264458764580948739641218298809107433282440735031876012977618636910574686835147900854781013457747251504797