1 1
2 2
3 3
4 5
5 9
6 15
7 23
8 45
9 69
10 113
11 225
12 345
13 521
14 1041
15 1733
16 3465
17 4905
18 7497
19 11529
20 18009
21 29097
22 47817
23 71577
24 114777
25 184761
26 307881
27 482841
28 804573
29 1212813
30 1854333
31 2993517
32 4953069
33 7752429
34 12826269
35 21376953
36 34207353
37 55027593
38 91712493
39 152705493
40 254509101
41 382100301
42 613676061
43 1022400765
44 1566479997
45 2606465277
46 4073516541
47 6788319021
48 10902451581
49 17130431421
50 28242061965
51 42057152397
52 66352085901
53 110586809817
54 177609053457
55 278378143857
56 434489749617
57 650385248337
58 1044438908337
59 1633272533937
60 2623079021697
61 4334591574585
62 6639749721657
63 10699724062521
64 17284169639385
65 24633131936985
66 35657750394585
67 52916457840345
68 78572476395225
69 120420155620665
70 184644238618329
71 290062653881721
72 447031931101881
73 742070053429881
74 1187356614141881
75 2374712609805881
76 4749211877348381
77 9497754541181453
78 18420045354265101
79 29704966947675405
80 45211087210846221
81 70412516969030541
82 116786861700213645
83 178052100624902925
84 271610412511327245
85 411903063907386381
86 661516948709408781
87 1062436019036954301
88 1729778809564749501
89 2796863482305069021
90 4480407278303872221
91 7443231899674308381
92 11691792179434635741
93 18677905729239104541
94 30397375990722463965
95 44359805584937703645
96 68016906985574282301
97 113361511025731155453
98 177893168996004211197
99 279540925803244793277
100 465901409034671578749
101 738403102897914058749
102 1220134212933565704093
103 1959377105521554856893
104 3079021165819586203365
105 4698225686517275797605
106 6831762233632672223205
107 10462587575060036394981
108 17437479841314709206021
109 29050434071312558550021
110 48395295186664078100421
111 80637748160327957963205
112 123643198623181341363525
113 176198863999508030643525
114 267937017442018375875525
115 405547346661781047517125
116 609382662261419633797125
117 917151885597598530949125
118 1314354464045370991678725
119 2015339695777391998141125
120 3090187513249203805913925
121 4720269889144586313843525
122 6964717041706506870233925
123 10559321704558272816598725
124 15678992834041071757882725
125 23189262998205443755796325
126 35217403296618530080196325
127 54000018388148412789624645
128 82800028195160899610757141
129 138000044347925395858381341
130 207064843686587409759181341
131 329496187147170413280704541
132 515384894435430821395904541
133 783117307129161118224936141
134 1305195511881935197041560073
135 2173873214837302195183823745
136 3167642889215751984605793729
137 4912966611608652384960033729
138 7717354092417567025920033729
139 12385987779703580649708126849
140 20538789858067037586224736897
141 33316396406369471591544726657
142 55527327330852685213147800897
143 91993034831711165054617132449
144 152408325332687541433443464049
145 252422603017018631631498390129
146 419677320157599053551948544241
147 658463680124644989601071091377
148 1063670684209307010749676993201
149 1670401491728598325657388023281
150 2617630254596500800541395772401
151 4113418971508786972279335977577
152 6501584591718807483992775810537
153 10500478893477344425743088770537
154 16925287738372607165973173634537
155 27198169243251251856415517735145
156 41701772767964241409267124426985
157 63860038149504596695876091531241
158 100481068952748275790093680804841
159 167468448253867099378506575563401
160 279076852803182107478264521725465
161 427670185410533645569852858115865
162 655760901288855642166916714650905
163 1005499985663915437685724725613849
164 1601480427857658609528237629908761
165 2644304561866183141757979681049881
166 4407174269776971902929966135070013
167 6862827945341267755665770006423613
168 11409334272301305737816213561276733
169 18951240791901755679887150304420573
170 30831902332171814954683892276880093
171 51386398738622709770965661303165469
172 80601000894901965867595505622112797
173 124234623345931476490117684502535069
174 202442833193786279141533362737928477
175 336902945594861535209576431576425117
176 560856367304975332227225216735634077
177 932988323660481582542191959268458717
178 1554980460285775886448701699685416157
179 2421868495108446198573071673881480157
180 3889628434436205398502943077686385597
181 6246899738108062299474819001781743197
182 9864958879085135386863888954590968413
183 16263842939451243431849515666385718621
184 27106404899085398226365143507134961821
185 45177338953312906477649358580557133725
186 67854591447524875219371389554314391965
187 104043706855472284831120409929824689565
188 157092459245572935457130920625690417565
189 237952660939108901930624617192728697245
190 354907332196138754077645972020481104285
191 529630941892699371469717835169025018077
192 882535384445059042430033879317530086157
193 1450565174357852672993445386903433209229
194 2404361453387673608660368381031715224781
195 3744460267798834429575419385091225548621
196 5780856788430660019390991493419287654221
197 8963011226734252378826808697424791654221
198 13600904167404392727664787451214554459981
199 21338453588859494310948145021953061556301
200 31931816456502388781375463456576842997837
201 49489083367904090904738768796641580493901
202 76807185132127360562596142902465523958861
203 120697005207628709455508224561017251226765
204 174726011260665888259651654523873576346765
205 252024147158179732872148578908825359895565
206 367208283446299596973596658522000427147661
207 612013341748134575119997827872663122532789
208 1007025845443420249517305051175755344628149
209 1678376409072367082528841751959592240928817
210 2796977310434817971451088439751330320628273
211 4658751572429273619889363012515966985406577
212 7678887322323502619410165263530232118873713
213 12798145535469458704050524738421112135963713
214 21330206782273865492745764145035416523001153
215 35445776002651116746567068518393688891886913
216 58268419090241602313931829252663149914944833
217 91313549349417968813390445567599624833984833
218 138722278002248007623832776056861823431207233
219 224457934320542641052404045915759083397004865
220 320747079129112605654622061422322336633536065
221 481749534535095653871764871215695676073955905
222 714936421614131348947585356560533566687715905
223 1094888498683973592345878069022386031040861281
224 1810922923859036179759328412420551777395490913
225 3018204834956715714936362977828096105423717185
226 4593875994395596894658862415793751247615818561
227 7649899435504870622857338275409177241452080961
228 12749827140860307100982557584449761009593307161
229 20749718680223637046697103519790787525263503705
230 31580777508894747550499814748048972096144009305
231 48411088839783204844062344159306444299748282457
232 74996414326360517260433327121333083155356372057
233 116414617601132227389367111578036072637483860057
234 186852696836900083172763852739583054535649634457
235 308051229238817380590781463167476337034000332953
236 512726984631767952316272329135984725181307899865
237 786181376435312517122197374752107848639266770905
238 1201760799206517993557081746886205748622012534745
239 1837842318657798611261112197786552030715966675417
240 3063070531096331018768520329644253384526607937049
241 5055311526931342711374886253511173023958714570649
242 8330783466721844285760491379362076452569877297049
243 13884632967271302468704146292419399022760061987449
244 21818621851647905017333607115430802125088970787449
245 34286405461623779360969505002329374628133408914809
246 57125740445769292383785680634579285750808804584649
247 95094510031146519986649945900087326274517692896649
248 154982109773277098702416824814091952201583168597737
249 258303516288795164504028041356819920335971947308601
250 430311712892073301777319619725962365920274214404153
251 717105582789875952560494865792527803856429540438233
252 1194366540572804105718903466656094289655036003885273
253 1910762539755902159216726440871554952471398382560473
254 3049735676386946126464817218622831241109383964538073
255 5081527342589666447118342188988075425918321578934745
256 7767248294953834451840161411020339181886874591330777
257 12639458387651892584729000568700619353156394457063897
258 21065763979419820974548334281167698921927324094988397
259 35015352654829814282079222306280985008930652796358125
260 52689558778813436662954918562314025434411300522438125
261 77927500245571748719614855520146740415705124522438125
262 116106455509777214145979572154298457049581296883142125
263 178029898447758913099475030332674456076038647621062125
264 259414993389604699185563452350914564431455321101254125
265 397769653452456959574851531938717855533389285665678125
266 609753366384647936627650815975872098700266357969678125
267 913878358780697760877719334261963398536319647838478125
268 1372609456521596147377163058968723843038643608849678125
269 2104666353653618811269038806162357004508932889924878125
270 3157015588018962215672818477376259005165825850692878125
271 4840725651122084271202441320775077806632133743417678125
272 7411172110407727532087471250428768325375063164712238125
273 10791617064513547398802331131459097441159800746177838125
274 16514992349477010623054650765206773956959196055369038125
275 25322988269198082955350464506650386734004100617701084125
276 38753965472750282020742960219648790506989567625083564125
277 58823681934153255407682177660246548481112924358296568925
278 90196187027985044669769707813540888856695223286246520925
279 128447869706351860769595513634329867330554946880815347805
280 187165482269917087176489632840173427248256113236267251805
281 272343162349667441917156658312770804504321245123688913373
282 445641506928861558955876927268118699440425199225016915933
283 742735844881435931593128212113531165734041998708361172261
284 1185967029055764168801327558573282034113518706883247239461
285 1964754243818068732179150176684403896458099890142518826341
286 3274590406363447886965250294474006494096833150237531022941
287 5145784810327166899175757347119638821798212569824895234141
288 8537754583222114231695175488055212424689030553508957601885
289 13026407514806121581708894684536392377158724017769079455325
290 19960859879369751025696924578919808101325120602703705375325
291 30471859750139896726965560753701969977546927014801000428125
292 46723517988062632500574184767589394651701216976270022108125
293 70782320920272147963247543996131460054185387450754339036125
294 108192391948995864493056856227458932174812160406819587036125
295 165895000988460135397743602257806453580900559187840340072125
296 251321181964334033074280195583584881532509289172176428648125
297 385349613458282661058377854647632708283499092021792098328125
298 589508347574110682545468472260107235265848025059153698328125
299 902243671358559707223715462362631164492929514211771866328125
300 1383414190911708142210058216599427383445097633996998106328125
301 2121194706234935739787714397068786306214671213903667448328125
302 3245006463587663458736503407394840656422543088951907908328125
303 4727488003616630128932598691798490674032120801677078391528125
304 7164751901654830132750165795379542925759578024111244556328125
305 10985952900241330662892011883257650603914928261669053956328125
306 16844780734532207695044443629797186730335934276338112446328125
307 25828663792949385132401480232355686319848432557051750274328125
308 35736268537207930561049383313948595872564698877004902274328125
309 50816188447414354006591101107966464900108483897627001510728125
310 72402637546603751919060776676256917748007782226150945625928125
311 109630241370173598206752399575727041279271657775447066027848125
312 166075212454127313819868877914112801014438341918034885708168125
313 244975360420977959466304180582085826738536693513342665588168125
314 370418853270207179267749376188766622467191453524541315609096125
315 552778350696592128569115923312128022690133616686104071407572925
316 804919288014629011233161867589186328253871628531157400318932925
317 1153515911995447905413840125446001764914755849130649972263636925
318 1626724796089089754752651334387595109970448573641595677257428925
319 2365436634547530421002695999880699111536911877932104715503726525
320 3433750873627172387390144244921483013201775349135864218553019005
321 5260092169180054070429235445886792986057377575377672980909130365
322 7941762421893306769794873663230411881517996006103566338535703165
323 11932618858749347377662813964373402479043071735279190906946680445
324 18296682250082332645676435323494868332767486095955427046998052029
325 30494470416803882873204484716921796917662697731347343182882511869
326 50824117361336123230790826143108084785806005223563875955507338509
327 83233699446748746977124038636150352560608608959227323952237388301
328 138722832411247907210635584136998616856725162797531235370950075581
329 231044440116480483239897393798393339619517575718367166038349952701
330 384998152801291529735876337324971848818920120011729614767146629501
331 641663588002152549559793895541619748031533533352882691278574527189
332 971174894242075838215141544082251331449308759183452648358126849749
333 1515647524006342643831302699892966201387030782384274553608734772949
334 2336086953623604905476311572299064809856094829431144046865813674197
335 3602352406752956383538036754751978539902507604973797370182975885525
336 5503800096067670863826840895347098679946257042229682088470436647125
337 8435926084194695543052955596859933023408193227287690631754456893525
338 12934955017536442709540603630909510930623827793492447916742914493525
339 19730632877495887237538055089322227413842338872397406942523039255125
340 30219223453822129990325788261022489617926011966332411276551612439125
341 46325214252633713983935766724022479794378976053988603266425556759125
342 71031995187371382220664476327832712044394941623114952519777711229525
343 108915477567009358598798976206338391819678117993182056992024654548725
344 167003663853009221410031937270141556429337660101267332173672435607285
345 253899323258186545686030839324764608886487176689270078193561160178165
346 387648271744086797047404894494839526808469083493147758017146741648245
347 573434702308641020594583571916611654848517414937835734157604329155445
348 816525452200322603455023108123921701690683639142138258566018041047925
349 1212355090373574511490287184746941447833007532221255633852470883815925
350 1836272838398192854499009096678896493509532575148779853383186770715125
351 2815615217572666764901009077507457693276744504681051251146748577310325
352 4201623607662866222499719589938818815390940459267252538823134184734325
353 6238774367996751190013030186280406669036083906591087234864505554667125
354 9566120697595018491353312952252404849385793248655630246939490129515125
355 13937766079968795537951969811909914420487297967504080354173702224491125
356 21287719128881179102534881233321584646721798169094247072778907635819125
357 32641152457755612783539651590472461868916536778124819391182953483191925
358 48516956458632650972378386948427792083644990496588927454570321173636725
359 69335486510022699024948782145610867226293356309083936788055754359060085
360 99152286966964632734534254517156410687207569230391818505681432991139445
361 151987800586805317131001316726738145741800197807370863463531453420195445
362 230842205550611128557687160332008678197991170315419238004006274393858165
363 348308010088522891134374274161331989420428155854736624865413728357818485
364 525708495590576153006091416197758518910556721792723997462034772708794485
365 786580402149456941668865543155423214525323583347094111991064649208311925
366 1206089311456118292988551427449074501043689672858831259394954557610368885
367 1840277089837698162357498156054516352188385940171639274956563298494034805
368 2821758204417803848948163839283591740022191774929846888266730390679812933
369 4429550983103864233954711597123447002895635867081481997793929532755706693
370 7374788606572550155030054997424956980016535058650043775278888137201688389
371 12002106542727985961455107284772231417650916570010355661584036415942270789
372 18860453138572549353654414269911253720526166171465612017877802520076694709
373 31177583385612557734510656278289569974065485565503700237746950302112260789
374 48657198868649032221866843980116590599703304728804506383507829122586994421
375 81095330981764603385413440608786347292910742843001490030093867488044995333
376 120204549448153261533729470674808637961211578543184454138485314957718672133
377 178544472335022386136373651392513365378771285041593374389467931070437704453
378 269985303895672766285617237548688970673657459627109842562181425952131723653
379 420499758750622251511545207854918339736558092567628330215379843130250117253
380 660785335179549252375285326628937846551158196857870392116683452633225523013
381 1003698826403462568890917624219219173593000863513796295432799797950104883013
382 1572055220260835725077549652209299192835456731583350146568571406725590271813
383 2470234632550809304845040243857803105129497187646442339513898276171067615045
384 3599484750288322129917058641049941667474410187713387409005966059557356939813
385 5953859084789969140879017500382859933877626926242583317497776139159293549093
386 9923097092363601488508003576610266549462189373078346285305698874517975169093
387 16476669003793368908946174018648086894987187939013022418761746723552423872453
388 26970732758791069666855015456146065238314302995582244273850518271333143442853
389 44915844363554217848523473539146286394368372061869294336737614944115328281253
390 72941964118619119790785425322175110424343846157811043460572642844880421620133
391 118455529554713738607610319752752351171049201021023514459433442181565047122885
392 181573489248951450973649098624421293842356949268417895187777989033679114212805
393 277048751201449652199724696251797459016893605307966675404420100419891265343045
394 424272938429950918129470616719958325899688465411374455662146443474773714849349
395 707007782974499578514035014153279844495637715174775409250066803664108447650949
396 1178346304957499290690716534046858022773708498444154450074951090737054877560069
397 1963910508262498817817860890078096704622847497406924083458251817895089138077181
398 3270090550225548878012186500569334574265104498585865145222385182271255647796733
399 5030273857289484228423738762199078933074178755875526981923986041017143264022013
400 7811992119385051543520300213470327009788771199626908063729241206880117626197053
401 12393805583041407731772027098361031836395117698525332183814069379601555406549053
402 19475980201922160321730591178347249297273847649603407678419451751865823692754493
403 30570963154757748165703054039549601250428639267467749566658187233347696270577213
404 48040084889178544496256754021856350541720378448678914482548076421623171881594429
405 75225042773762242352668342982906823525107222286488896603046849209447344457595613
406 125334002077100536974555799618114608479935821011910257941171562443449739721493213
407 202352756533933797535581704554450782196920748641203942818389512672390096171387613
408 334959891246025474200383442074835276016301233476859636152379998794368819638971613
409 551063046888622554329663082123116099252624609913543272379721933500413149670362053
410 918436913075746897291327992695058367770984572261938413832061772302018794486664133
411 1436934860557716596721410400608187432645789742691889239924587041461103635612813253
412 2252498704503662028583026252935246576974494513609537408210785488290844957793306565
413 3430506318926962346591055924745208948491208537292552679021517503172686175249352645
414 5249533946997675328826230136022964849162208748508801056022747407950058688868403141
415 8749223244996014253600457234574435136562534243625355195150638215410035630626806501
416 14424729631528047197663854022303251823465422476458026174975842005073871451797609317
417 23293539365725582173267661522552774114028258990781126251172907395598117431635672037
418 38402858508053579541529848820906278385380376777298245098288705888576668754253338597
419 63309461084219773425142092484445297468282612190339261761082051881568343658698389477
420 105501187564626847231506023454901536258147878571998762017059107885620273610829772773
421 175679796570637843170453540023703320190317491191229543090439891326880508134207947749
422 292799660951063068971668347253297121543628181940384542614141925553699363405175217349
423 476515791506832124522565943201399472236131500267762362771197285903302625139695697093
424 775186014440166227149984703611984657634335037247924419891124788761547187094718135493
425 1291976689550488011792763222086264762706508657726123200803839630360411126543085175173
426 2153294482133644977421780525671446217517331197510045747799510258149310480482016442693
427 3588739853971165373924110437197614915493834262951227067130685919567031600635375519045
428 5501930579550702039682297283942196114475409173398720547946780730022650199331425418565
429 8436293555128863957220615901978655620336078484150669024394912596789956973769787729541
430 14060223200754293300380341335406088886791312164076256335706604494306850534717669917301
431 22845715602647388846255195866296164658750961793448286539400195766174561933044679197301
432 38061808837823410240946971354027124202571619933046179673328999542824071220557630646901
433 63436348063039017068244952256711873670952699888410299455548332571373452033697858671873
434 105696268002707635342629024845200460446073662108151200747781420574381349556828818172673
435 176155302173941422481060658257863355302340235140359657365610839969710103325206779038465
436 257776582455744236467869570939374952220667343333890743171618839511874906643008721939201
437 403819997680245874459403948500278643713620651598395583350965804409086764690084247596801
438 659999143223068303382554742957393178191807014963152802107224701698804376415916439596801
439 1059995679625011862791447041407849255583681078303348927013895910128550950104960715001601
440 1720669922968409579535186011509803172261779808975715738158012323344440189641395284217601
441 2865228294823748623362791089762786423427688912225447114457472339382515654597478704148225
442 4388436472794247035846019049899353014467035477505423766821661696775714823056542604948225
443 6516149608037347613385258063532591143595406916808146597234582612858882961220381617428225
444 9672846636777934674638208537759286777629832716069314136213643986639338306738190360967425
445 14751271876242244541800140233554702263567263370589461538681844595836190613502707129121025
446 22618616875051254348724385916527791337781027306152596869506212650480437886357459940001025
447 34263760051605570710394350279720948461397334932539416253173439995582164524140398692001025
448 52537765382169201466142920435026813490614099389955876111462751633546117211021003154871425
449 77852197621227979111989109357943164027950492904134573671979053829784201787127833547281025
450 119333782174746223581859016218765167839052266477999051071305307448632264726130518323519105
451 177721480634531101360602558779646897207765433135822827126337276950642684443481037438281345
452 272506264438298844346433090094151190483081529154769277901125593379417744870975676211099265
453 413154658987098247880075975159186477921730883925078670907174413442031286844813875764411265
454 633502001147439377732281432211013029151131015946355720439607203526288403387849301247256449
455 1032047791419912338657345400466917731166306721199362024828474424278807365482423003705780097
456 1716369783003243851501433679158206777226358051557559799899746119420136454662454276721542017
457 2724311871997427544439534823295486541115760290016010088203967548186968494564320625095354497
458 4406625124144703728923398086018267809565840214399225286037655011515208749208868150215354497
459 6740889357770792919431431168281725509802371246298929387843624006854886382293510906345924737
460 10592826133639817444792117753599282965078195634681602881829459991487279351583882241912682625
461 16158012400865512579966196324886053304149922933272751902677066542774684420547196078928497025
462 24731077213914799099617153202463653006124198181801045125697470799442084922832868646431005825
463 36934700825486980456583319840326772383659447102554488881502731896956216649835260574249783425
464 56631643618792148832195090606101901889417920132450861155033856539669279523621718589987767425
465 86835186882147961504133722381180840009239642608150729514084594680467582691204439478766779905
466 133146192505718630519539556180932858925628897197239612167057067484853540841364987437387522305
467 202395712337865575663279819204320090477675660229513315929926039216734453014501653961938020865
468 288283318814942131019333900291469870171032242479700379793755102115698880156728446765269584385
469 432986412503084305292876871837476180056718873652547420146119598469525949002239101318842448385
470 660465841161421134342267450252648685766442076216158883121663188787580391832502669633561306561
471 1100612899913213292272535833875590738677445193414389714996495073195287607649614135644179725761
472 1713785510490751382735719190240716879251595665327928365953541917792377880315010230755419277761
473 2686606046247090862055900376753895807871233696734510219853376497428543186075654793006437809361
474 4477390106254971826777450695973201817248201244924676865788621773693997377983295397778719421905
475 6864038620562334073342618980256302952012773093378316960747873896169677958783712561747199329745
476 10524859217931951106242000183974945317621579853961481463294713725848490187801588533775020468945
477 16018686440909196506333815906067969797474158630375273685033427446078805027160014051236103497425
478 24561985876060728336107614752106042758795700545649407430611454538449042983624794659642666038225
479 36653999287085640191709550271716495524766334956078288351978231261527028314528128047424924982225
480 54699042361293237673529451607264000080561778922386760790043074542301968041205670217658224796625
481 83871496391544891154531551761589337475006941061212209129250094316090082617043245603286994780625
482 128580033678614760396018224322083890566655939189603793516906018877170617656284241244543226780625
483 197047373323645758007844093374730779996761161959345274692310808643778109783877217846010124280625
484 302139305752811994317822421388106380248961910522960127012843547781144713354197465337772975780625
485 461010554009446346219198795167024666973317501431091249137516249734371607801152381741044700580625
486 706876216490506347831195913086887385835232067196240183909726953886071841333714182897124060580625
487 1080659598675457961161207503269279156024589538024151600686131078416830106613383980901750881700625
488 1612660161921917313550949271791597512454207806047898410992635369398661065049561109095718152100625
489 2458455288400616396772109067834295262477558693689485153122750988180010355163603113339810066340625
490 3767899373318883941261560027082363756309727340050912383953785596415387072735548094602884098020625
491 5777445662430903036554875701396358508219584397989577712136364442596841486346300958592352556180625
492 8857501005307852345704648565351652954850670414771596275168312948184913917884059964517533922980625
493 13145347187615440271769429919416846801484482542359313536445126509094391584567352614074089033380625
494 20156092858545834414401171594677546582187918729165643078894834686627585674435557766787008482980625
495 30886138594703321126688470664451821818099149737810216752619767876107030788181357749367354127780625
496 47157765296878650273574327623181607502586417725949191160509302561681454867868177667273654512196625
497 72307825831535730149567556223105577680040628834234609400387751488882812604044634996037894879156625
498 110871674963828498859687424388510818441201155904996779832567749709678759613718414365534891131316625
499 161555865231606672719889361451788042452673363060057384751320903273764583391538895591732699256987025
500 235408407528689983549594020832370648008390618144145154267513491201897754306173934650962323733806225