1 5
2 500
3 269940
4 319608038
5 481871809749
6 769126451071174
7 1243368053336112649
8 2015791720035206825303
9 3270193421121063659774745
10 5305976942994216714747844079
11 8609380449975858170849466245738
12 13969529468144922829977896995042050
13 22666915113380049658682512470153770175
14 36779280766530266643460204864752345178835
15 59677976054396593265315189533479830461674865
16 96833348180142700372743997628775711985224442506
17 157121571212644642717628097036725420845867833655001
18 254945105494661051717578706817272017095365358275399751
19 413673350706648350006233868280320363625009813955921491244
20 671225441894798695028706811574035330315043058366538441218569
21 1089128881720492497242706076791729060249642931947355665674499959
22 1767218056652790812790309305036614922978732964442195521700353444726
23 2867484016059044829647330526491897068302398936115629092387572182793299
24 4652773069741704747581936125364118649099351378354972137918271636433384966
25 7549579044652168850393458770996027458937319762299532287261448848807910283891
26 12249929858413600000909075715191211701905129701769430320651999947511574500285320
27 19876708442750936940595707325325983023011414523745222456085265876237460763287507252
28 32251902099404425445638584989880500442914817141679322295608449463902100231886630918308
29 52331863297462848384400292260931314367608077092073374289265850559203324086546158078179411
30 84913562857271341031720598540925601694641013993183314631341251140785869411331399620714269662
31 137780554767010202424880704969733403026977626137489697018764946450530709446423342123469732998837
32 223562416098519640294136051035043297351520346286360864782277453310700558418465105082764825248866593
33 362751870003173658285364482508660135153069466578730155454377325262306807699013612931378876713386672699
34 588600362651344334004325686194042668737753437560299558857917553290230079956546467170634140444536133733315
35 955061615286126648454612090029210548012707126038666667924309529455270705734056043873455594801141356598957618
36 1549680813793943207666577086535943478655700408906420995356029414283424443823326658524108247758612267703976768512
37 2514508578508403532287493448335171214751020555386917226899673171438084606326594876720860024545279480738473211504861
38 4080035924244895042921614719787912061030994509059800388527185298337972047378882414507743632582790955108510178210202547
39 6620257049591633110291358043956100001973031111156712520989524076301523743612685415490531502571132189712580553784941650205
40 10742014094098708954496896551522139816994025899246218447648263278609852574891316289120515156946914813496048937452764923587364
41 17429967738931395195613844638320780429832675747686925172156281197416829081226162352957345727888100066331588336237034588217022099
42 28281826175138654921747280382442951329494025416502991457838485032594494504835895020373788420115417055788320203061315747300670049851
43 45890027094783152068085528590103528334408960155616588690549194338236874509926755751124157744551967606750527818484224937709290814368052
44 74461054025257173212360831729305456683685838966816104197950656742777460160247738326870893392987824297327942129342840302435255481012958735
45 120820337610621476532991858339502109698820649793543500122255579978551287722787003515644739083762743939411913655255450635267229576527187514613
46 196042806154651899086475493172695990719494107527288869187133326458371812235737525524917922437393365978827435644522057455391343219098586657443206
47 318098613238867026378068282866972875688846502823581419845244469786519786445019093049974924743769313448335308359295514127248475547154336294386205591
48 516146089363092138640340812689621793873256983617660067994959339132343443018397191646543307263306270982534675161982010843807887409858057683372139058528
49 837497475554106122929882165751632187062149851591929556344021801176019631008061855887739109314668726014832844101787900739644217169324098746021880553711757
50 1358921506941975233641165680783157049754672685694628347923976505950948122892550632260459385386422250180555575944477988585535109923052909442457303615125942020
51 2204982959271195754265177034156589646175892634565011393766817995527707466188912187138658504580447007888495226233561397623310754341088034979773455355833027570108
52 3577800355531469812993068545499927631091749395501964999545840297913232143355120838783269941675346755785103789224261732189520475928156198014797396549856680146972794
53 5805330753337006058952118598052754029650245959654773569695488533091760421968324787572493835063399930941321319735956026941959414759841877298899011337182017034546016041
54 9419716531565416344087459598402145029827981883672512464412095620000954794926855158787806585398265289987754401043714008627721183061447152452828918889740210940691793563406
55 15284410708906228328985978970432355216523649930587689448361660980621609381399939166482383052994012497291531238587716247738699142281926410827530575466890445592059446965221689
56 24800450197804876314610596204326831429455889140397950771966481330606742412397488160257163482153520846596735975467503526147724358264793090713157208220970372142654832611213744451
57 40241154319113069902796874478234772793433956266410311481803813649536714855447769194128342694324502588312312504811028850343008199916142946876509831559368180551371257196738308247861
58 65295205853884198178298293538604173018360041152290821390532520260400085449369558622109186779948366266202118284471836081631097335422417725701622889941163446948862073104428577136361839
59 105947853127963691112544071201472300068363658653755359125323964942036940002651188070950317116612859013630738932591525295551768136048469377965572665002265448398647654309770990303777702674
60 171910746518564353045467124418580450149255918653048757183629367487623359331608583483715112064030689698940511517584513358042180203673025043879707706252175425283503167303179380007819047876502
61 278941987931323529973310157051061999879268489424032415265393643865039787432609983206267684076855461128876146626846528331070719506567020313253437917908345133409905069550869073188225092641905171
62 452610637826973883659029434502970419138644857938822485433554041129825040751045646058690964226981069776695397580656327722259715895166630832475693809303479019370984748290570803759054345248501162795
63 734404995796389265339652695264071143522553770452053803639215126263124499992708699906950990182207773105114343662604796250448270753302926362084670041010278108886397685647114717971504663196461874001569
64 1191643882786687942570925263304254028950720550077978871835144849159439276209658044303149799274949017838168358923499593677310164665505384794196785219989195878142256424850432914803756402874364271462517782
65 1933558665192722861818970533855597854175869971297916192738423112164713352687518562455178160608308022260661573813876343212448916975723244024678632156573839615403720437928402196031278756826110443018531933093
66 3137387910722910843032363164793516782284655608927386556224901395198711820652241792599864147164450885774202198275116740804613559998962768336925645720698183067414104700627782206827656957565296503612378641586183
67 5090718517903967365227373214810193046411450773778036555304092832081252863931549258648382311296162773937844260107486792998246092052233855487361875011152625866220675513784621331540546394454533244693630961466293844
68 8260188336914636222151275183067014689890336398214033344068196561912556338596051295465431875110810224574596502281609386321571145335841347778658461652251381867376674940961099932164737472364362871488188890132305125421
69 13402962886542316902147188327391900807370435299751532545343767669727101965867936059386546441449866504308165534047126365940790103665511486597263357150216093304308221105637220981364379088029970576217739618782904490008715
70 21747617222627403923500163753414467128761253560399100301195504166096181953043447203059181849265543766245699515758294089419000096444316036970998873270396510608577326890302112796696262922001595921727264300861061009960645166
71 35287634448112206570659609278765709534003803182200385250840426937442287718187319151829043320351641695668255107681250039512955741431578217110223308000292418439399923154995704969607554398198371906168221563215238348721341227571
72 57257635730686101198127705113316858583440750687246677267709884326902795865034522410485921831497938100622693815769028706509204332224073938987336765098289522578220700224240941340638003092495369113127660395238358412297866232392978
73 92906110050778120151166162939493471486438211154251443555438041345440663870265271770112624895559029049165721683378437456208453096101715215328600853386351766283636335063324288373152916347601075044073863407906302758076710988221960703
74 150749243740453444645681797034030983215683941250809418574093187023385761668015364575743407999750069622984856993972791730131017947368258662537372566268018727539731246750299818541258578846942259356008260722486597905169125216844290873304
75 244605381453362331211246581358266320580842139422780754981506974001216223324536535238322135474903116262432075947748873528448002887868891783031080280481391478174797453013089743683725177759839668905184056556536024994011385584927033534365276
76 396896137926621497032348003652018743166462185400488623563218091141179213696458479444759862987878478967503724500390898153941728293854890150966867008385553885299481553310906619063837316966046268436926278111762179732870002359035317873941257832
77 644002774448781059295703582670869066464460560069608385780637528608065243853953940557116916644011815758685954875828046729078103703188943977683306659395395289015274698259151163506858940998668633608607477530343713881830391332609194344305493702039
78 1044957443184808674700165895614473372824601416308230548204949194165100570512639710043197325070402349948766672335339089276710301272764829990816036817055857907111937626399442065445870663968516995311488673668471411719903129471951692428247026513859798
79 1695545580532552034684892753761518223758481357534323185247722583379962791181161956691116593455954971816222268237251040613453936063021599310882712122812095669424298774368136249159760652529297139969701552375362278514110887397843770269945107835344475925
80 2751188418641681862104264147786926297196588510947469707806231175861639315657962003588037785981977683111518102940413404911478117993629730975305031208460501898425736825491483048840427774140492685428147708722025756041357462469284308717344508575787712402749
81 4464072096776523967239625349503856903387770171215995386879269550106677319105318326524437206711056310143593966432638624675820541497459968915337344633989433762548131968654261127928736867632068534451843823531149695348321322190841784638815538409619178121719943
82 7243393273317711779159662909488108283832508276337022143577372473380716440546343957030387800121311822414534529835607385392242776955725037218046022102350209853315843117987178780603686025595682098522422231122063015266505712898371015658004337089852829152725902451
83 11753113519342609855438873724178909851046508005396858766952787020862394702136629162903221285480204399634449043521874023642241301677326697706582028290252208638406133708670101912485398528593383649285696254185486486457694403962849893303766232800071093709936590389642
84 19070575376239837361118013368946575745519841322765983716772542722084393523859593616392670951774069951081756400320817516929490401365393923870629020049917352429327970275768278695561203909751120390942618732812403194987308073069292828107232007939733329055124355413003588
85 30943872411536735593473848696935165519182323138015460188617814668226525277367929030234227746172061477135500688258109043719008412244540533873760467747735262705614676310647872015960026144118301401367926554616764851893978933352922906857298387434053284314227030114654184673
86 50209457288554029657286831123712477879343088811955817012125741014345441833783750689062835231558640453803860152375149846525109140935353228486063528140801529934907067514999604851765813845478122698735627014435891697032824506841209883337075486129427362230153057289848481212091
87 81469751674364983092382504059760566988797224401767282522681582815172645713811382075608237334714597863863069272662402194075051670665988077796120818481434438670812613414572064942404584025393166190133185606124748875368288513863927530174779216960005418991158013678782877739513469
88 132192634541695572968655122058473576225590482977397108078461643000130784509499840137244605642394142587680728417664909201367735722464685119933616231108557557687669385891010477952416401169565981219471572777508880912604404894456006200366365918274902154112446554024472287389270050016
89 214495469397298783123364291607290700896403711174504109841965335525034903279742528536507171261197799030384667952657208054177829400584528626973920138333088171054988303150720400818225072820036555119803528620434853366251694651637529747939002901117323829226850780785163286529161493516943
90 348039862821977553521731622462951511937010302278119423497333430836804519887331730276864921359673488163108925034861611966152574675984488016386458917067594485920831480516708054152813556285792004027034018272796040619452608206106226289387403231835367411415200506798553325334310764467983147
91 564728693121135023571870894105805844387879872499869988438979528244215166670367592599788967452030678807751982746392941697488227018570370999956526804522190882492556482207529872424205444787223032500556360503558448410810998593698189272570364498532132920999268358192272344975501107294680024332
92 916327498374609919689477998849733914712511861657803492165433513959957740705577957591447202522432665129705484465885314566439317550570914477772955824744698859754090593313571982113707478855887752595998621203446148633090744481268620332988829350127408678325072507368796103459648032138878956120035
93 1486830923424256479303822691036253380276503614687766493444103666228024907512014925742612086167436036273409774650891268487199648658720838328056006153426249386286198847766399447061515063832989553732961880229079490480716327024046310437845946920714738153875003304803636342156840806395766101981904569
94 2412528488746574896725545597820831240849465471354829362605314895976618889550815022133241896259847903036173931016679570397957520754813611247720193911572303338725828037282480304760597226217287516386953518424011511557223542685655637302764534788697013680250685263732656976069724099750288584960991192814
95 3914563261577425324197753332776609533642670003858321546628856469788778447650309717392666686601601360099802696483222995022683346314913215302129911445482739197609521477917952594694246813056418252656158272311021735989594924938667050496946750823563620496981220709479056638995753341143110901984179554453671
96 6351761481935140725717918588908263243626774298387622341896425730430705731006893440956220471018643589680583814547872557206629461087494284854006314549460065585191502188892156455251605253611241717778930180804446068675275745122174009286190407060858766806423559669912225156652701641866651147597662782249391260
97 10306353794149028918414038823952109571242853642587822908820107298722684777593252878161684792038194721975290430989590508650251641294321265674193613401040556423150309710917772103966896212473749272277246506541370053088267664679970873592280343095465811190047972417057372466839717281625570601283128262416287425353
98 16723066322982990421258783191501372204684543700794942820984234745364185303784107174700890151023426141010916405763864673940863498452519660411966671524484558853474707390448035335536574553557034266686531988731057394329925336419191960820506268138001330090197723378171599816578803610047391429972705678334395756456836
99 27134809538719000857272796025257711152357703600791654374880813079643530949643405605558560320895088200410115812290190811471142289197474124544077310885707852995496107502214372870582886534423896043442050683343338675992817093291404180555637694250736149717787852537445465496691461100524439900170332442897513262023759764
100 44028880498466978949250164137176858215751857646214189646640935547719743456786256186578110746924587935944375400161166277475144168304340981980140732955009699241528930710012481377478244622539775277988529827519640244493011233739447716654439912711009411057505864890318158967073218908500726793604947027888024302370042325486
101 71441161773483445489284979339832690127499272068294458454554485269895428940948645155014918768374876329865691485045398602034962044279931397177155988574290036601321077113326777790817687144130551057951091291712127898944944788774092191202126549208400917338112124534605928098636389365948641979817816034464385946979931285393437
102 115920267282806350897320544555044523703590341426013887596577869085528426761932812110962908091478256503920257046488457924091667663438895123730136283010776065463897291211334909125753619430085797313301935873927791619164813458221123627925325242328138626367222097070820188496230788333209608387263775087283737396395040144769626806
103 188091963139166296203944289377070829932279624594715371318468707409930262231440018823232024960444056017947683550215595295136595629736388970256132908985798685857665371821216394776274614632948645076838658449644954800574042985872209030539526858519934865451065883196586879947347148957959677699527353750033391181357704729174961258697
104 305197593370222956858518050748175827382082895786798464961915189023303118710626816964207908281140055882786528419857763465266181504794520520601335441659886010911429700021808639332650570716825935305604893276319231015276806697849939804931082174222262332652089951757971630616191196671667512394490710745468682368802222905832269066005647
105 495212923744429267933960683796437741599181154834982177840332872247537052715634889117493751895399363055158329507058232725731014713114872237913078440753400957758913161208751065240375845629804150463056387132468225087749387019505121206066345435225693290907329040054773617531032856293512251860127812913538157461473466607334398225205769393
106 803531368433892458269360193502735579296871362327841378712333678171863462975700031929953923463872812507149035333181240466896073523895509595842454539284704617644675857321028630303994686433590174465620041321235494276734545770447373463143667895618421724944559190597499657125150857865936013179590843631115883302303802572466311413058535264847
107 1303808178460340497791986013351903850172294721550611670753797087417801012946768758734822327385216952362097838330476953209101945091719858192839169145661498038490631498242963802174656681155352860591437322001411881254868898051335519607229027940983616992921276949199573216982319124884033540961481013061717806963025162893132021666238518990227994
108 2115556197305974017093268370095604659759157382235964957008832438617857349476185294776104048211154176949563260235096978035396199958224230055612074657003218093362738041328473245577217608047427947661870277332118748701241644318927666592879196079045081738268731029281120027058551925881703718162916198376090828071423368632856489082704120421444048010
109 3432696694114081527199574536698941603145460365503518807554790700034105370759657842949358760286154714259075202232904524706891264051711310989081794570152740838883532641729196390985304567175278344861817220910894219573624156100331604791163850677684926310880947251239424755555970292726242167950445005951128253164939618643907088589249528831375273010631
110 5569885880974072673517923432884861779136197748575128098910870338223056936595340409693045472999469289583610871895319503396503316868556135743858919276791227466289475654729224824239364941351805586758599803292638757752820158537802242980380054114764405993578831140670681241871867699620835038834777680209591584777300080315729549981218994535993948947518435
111 9037684214940805616076823688480245553396548165257152825070694283273165872642625392187137619058263228820022640902917967870617692562317316619587871114766142309231694895654013036024388627075836243260896120762391251849408219904998878976737612410303419349580778761908306642234373615417458871612813390361740800971363205404923839403873388458768965993546092849
112 14664525937236238660790764439987977187053840735534684078751971900531550920333750080264293134677560674510528153545706115698667267507992362030599711069678296201812538653657033338330012793127450981327205924029657101795356660051635589534721528148645609230738243149096902360760513142979742968662020662388968123538628249108068007245970380938044931318806901220610
113 23794626571302800511336823600214724398105725833218631575552225157299442528283404848571104033867906956319998530888327074071779191643446671745176172626186390132220617716232740481322622858007172460675290731944076723995873376342812077271397334522557560408349848193379204048515856669803301726080696156639214198534337518698827622063709321130822169088069686154960849
114 38609107180893678857958803852485863691479012628052685707228413367648164187810823070293979057446989924184923098814956220517904457820085335800431237853790461510337149857592208947594137496939792274715441823107874944618368309164982762424063610190058069448034573499846079791331177200426832072132396762707488313417639304154025337717371214351517663548063199190874916135
115 62647049863918886852579193836851288658774461053955947624043423875984460340794060511005115846563620388455085620262687764941828632446929350230510387988485659289222159564094733820498931559834372375776679903571581267441186327701325222663973089990567353974363565843748095188474255898371743735947612774127086488907529445458897074923026986073060652171435013143181764279772
116 101650961216593874750753867323982927476314163099821306962156419756388903342899782361727423191676573555164480038168054114393442815201664624627103528707651527690964859184250161917556202283373751405508807583302134335080770993008258058409220398754735790759696148263713586208722826079902873734842777241450490747164655355784888519609401356501547296258124070339446437716929713
117 164938619435432362911595846592650252866308571706825201648024036704710190775384300482950073816808456903560324903150651373200915840163632454155719084509868632805618983050831402291806551521675732904022485091769274007304128194633642647861731007759976527711760791547094798554760056044868330795247910459521315886415414168945711536654016267119095637273176574908090551341023400959
118 267629030317771198743307249366386560562759719107211842309334384811375421017302825622045298896609045924361437188539315623460874098943583444189304480353159209858931179268376802479020716680869460369658051561360387816601971080360677347331310948994144494944668043893747135554297310528658380964889171016947659726140844065662536736449758089187789739920236262560420668164095346096454
119 434254258426537072031055334158567350422936085519610707563687380008391783622536865693417137846631034778210252051040910068563791314454235403707142358741419655038667814236935677932595142279235410563427660266684745264974826610185634748923977597106505535253970375597768999372716729462881092506593065878962637923652682403515224330381171323961700950663401005604060866758858617341876083
120 704619976157570459185758398816473667924226886569338075671727873218853797227717082591256616684520531626857380648215696701463334653875517813038749071178454191845665210281293590247402015272996011643191153701429999250155788943136554127708488296375391456439289521099099676174934004258428888713649662860023720686263405128221008842662314073314270917096719169686347257547484061046681580414
121 1143314777382399379512493108375740810100944988064946369945321987387632682935645944410981293072906406530378653734942633305685084817340462189856382470308308322705781355991454085154080052111036003998497291510652331595810518379705221082880466927281636362806062836046737538618964977611951223886177968289459494637030990547662395396687157157848760481471266272578930173630875383500442116155627
122 1855139968226859062427998366329993283697943571262773421633859595274441596042197713485061928709989688917799372341695694615540018493310574145851543844075954896890196290041273986883289707472482449859304950437695986322033684868648876478062690308047612268838655510960827230451473978056810347120856963440567887425806454954496356307737621013093814100519703766156927992469068005695523376330629000
123 3010145910640734877169136137124158246714750168327569126263635335104752035274622388328344514193149439410365906387423024755877637501328501333766612653886791660711794897178043576437788754644233450324463409924662518625860266643326373553489535852080339657993364660635602122800942803154200387270118777781593956849589837559160788223363439047441464906222432826412934136948542259040479660955235708388