5 1
6 0
7 1
8 1
9 2
10 3
11 5
12 5
13 9
14 11
15 17
16 21
17 31
18 37
19 53
20 67
21 90
22 113
23 151
24 186
25 246
26 305
27 392
28 486
29 620
30 762
31 962
32 1181
33 1473
34 1802
35 2235
36 2716
37 3345
38 4056
39 4956
40 5990
41 7283
42 8759
43 10598
44 12709
45 15297
46 18283
47 21917
48 26099
49 31165
50 37009
51 44014
52 52113
53 61776
54 72918
55 86166
56 101443
57 119490
58 140314
59 164819
60 193040
61 226147
62 264250
63 308757
64 359957
65 419588
66 488059
67 567605
68 658860
69 764531
70 885654
71 1025569
72 1185686
73 1370261
74 1581244
75 1823851
76 2100872
77 2418774
78 2781248
79 3196456
80 3669328
81 4209896
82 4824849
83 5526637
84 6323929
85 7232366
86 8263224
87 9435801
88 10764926
89 12274509
90 13983536
91 15921867
92 18113840
93 20596314
94 23400614
95 26572364
96 30151223
97 34193931
98 38750723
99 43891545
100 49680168
101 56202936
102 63539913
103 71798020
104 81077693
105 91510516
106 103222574
107 116375879
108 131127573
109 147677405
110 166221008
111 187003549
112 210268570
113 236316994
114 265450354
115 298038226
116 334453498
117 375148498
118 420584157
119 471313812
120 527904961
121 591034513
122 661400275
123 739828152
124 827175497
125 924449314
126 1032699739
127 1153154151
128 1287097258
129 1436021751
130 1601497851
131 1785339432
132 1989460980
133 2216065439
134 2467484127
135 2746387635
136 3055612073
137 3398392058
138 3778170891
139 4198863491
140 4664645392
141 5180247461
142 5750728035
143 6381798784
144 7079577007
145 7850952996
146 8703316291
147 9644967535
148 10684824198
149 11832876588
150 13099870076
151 14497818485
152 16039655744
153 17739811217
154 19613837705
155 21679049770
156 23954124834
157 26459821777
158 29218547329
159 32255161680
160 35596519704
161 39272366190
162 43314849136
163 47759527395
164 52644847545
165 58013274590
166 63910745085
167 70387926702
168 77499646047
169 85306306976
170 93873285415
171 103272522295
172 113581903120
173 124887036262
174 137280617992
175 150864436861
176 165748718038
177 182054377895
178 199912372962
179 219466223062
180 240871370957
181 264298028944
182 289930547543
183 317970622197
184 348636707227
185 382167613843
186 418821983885
187 458882354991
188 502654701049
189 550473019365
190 602698991915
191 659727144807
192 721984659827
193 789937211800
194 864088952271
195 944989108521
196 1033232219438
197 1129465576460
198 1234389765742
199 1348767099398
200 1473422512555
201 1609253110662
202 1757229542030
203 1918406787543
204 2093926101767
205 2285027256945
206 2493051143955
207 2719453660690
208 2965809155003
209 3233826153090
210 3525351801079
211 3842389737125
212 4187105692433
213 4561847793310
214 4969153596788
215 5411773125382
216 5892677591671
217 6415085605095
218 6982473856072
219 7598606924712
220 8267550342472
221 8993704465168
222 9781820319074
223 10637038177491
224 11564906631948
225 12571426518618
226 13663073846740
227 14846849778833
228 16130308056974
229 17521611969502
230 19029566980261
231 20663685649248
232 22434226420456
233 24352267561525
234 26429753105878
235 28679577179480
236 31115638203683
237 33752935055199
238 36607630970530
239 39697163142375
240 43040317860500
241 46657355551495
242 50570098871993
243 54802075348219
244 59378620586148
245 64327040916145
246 69676734062820
247 75459374744026
248 81709055432642
249 88462498115394
250 95759218391419
251 103641766982073
252 112155920717823
253 121350958132321
254 131279881338770
255 141999730464721
256 153571841261225
257 166062203721096
258 179541760769651
259 194086817429002
260 209779386630112
261 226707655956629
262 244966387784823
263 264657451526923
264 285890286105651
265 308782507032515
266 333460440269783
267 360059814518786
268 388726377153097
269 419616683413478
270 452898806339366
271 488753236543981
272 527373699636587
273 568968181836606
274 613759870667917
275 661988323633685
276 713910549858321
277 769802341816512
278 829959517926289
279 894699439708661
280 964362438565849
281 1039313543638636
282 1119944118850950
283 1206673830640529
284 1299952524781835
285 1400262466714034
286 1508120492225995
287 1624080557339252
288 1748736201176804
289 1882723447878095
290 2026723625006650
291 2181466665211956
292 2347734330010891
293 2526363965083475
294 2718252185512043
295 2924359146416701
296 3145712753075770
297 3383413516278440
298 3638639359952047
299 3912651139563624
300 4206798129034222
301 4522524291602564
302 4861374538457007
303 5225001852652052
304 5615174424954181
305 6033783744344380
306 6482852729899984
307 6964544917129139
308 7481173720103884
309 8035212859061547
310 8629306905563176
311 9266283115432443
312 9949163429003748
313 10681177895748485
314 11465778323831011
315 12306653506123611
316 13207744739627820
317 14173263089312153
318 15207707025757540
319 16315881994818765
320 17502920453628911
321 18774304047617932
322 20135886362354491
323 21593918047689635
324 23155072642801996
325 24826475031923912
326 26615730745375146
327 28530958179299308
328 30580821828355305
329 32774568756393938
330 35122066273497909
331 37633843207715795
332 40321132603848777
333 43195918414748128
334 46270983874018908
335 49559964302866340
336 53077401890106068
337 56838805399747930
338 60860712183622101
339 65160755672064868
340 69757735550023875
341 74671694023031946
342 79923995202959403
343 85537411267203637
344 91536212230444006
345 97946263252642147
346 104795126121891679
347 112112169122070295
348 119928681715076819
349 128277998555895769
350 137195629046411464
351 146719397280113091
352 156889588348860879
353 167749106218352967
354 179343638899530670
355 191721836504421254
356 204935497652938332
357 219039770232653299
358 234093361705391895
359 250158765402339395
360 267302497718975373
361 285595353125261261
362 305112671601494615
363 325934625928224658
364 348146523126979563
365 371839128026475199
366 397109002927161818
367 424058871927664086
368 452798003542388832
369 483442620811551407
370 516116332176251011
371 550950592999991279
372 588085190642681751
373 627668763702118225
374 669859347941965277
375 714824960315830172
376 762744213206821511
377 813806971141074280
378 868215041686298125
379 926182913710043085
380 987938534280254596
381 1053724138375497699
382 1123797122248080222
383 1198430975669747388
384 1277916263457882410
385 1362561672659325266
386 1452695115326090116
387 1548664904503887736
388 1650840992896880535
389 1759616293162857517
390 1875408068830510112
391 1998659416234339877
392 2129840825972989555
393 2269451845849768681
394 2418022833314618113
395 2576116821044929367
396 2744331483205349486
397 2923301227840404921
398 3113699402454559823
399 3316240640204845660
400 3531683333285258103
401 3760832263048552249
402 4004541372989843855
403 4263716716434445298
404 4539319564606056530
405 4832369709412233251
406 5143948946201781380
407 5475204773518983566
408 5827354294728470544
409 6201688361450131484
410 6599575943323906663
411 7022468767211660655
412 7471906210054138209
413 7949520491909590008
414 8457042153160547516
415 8996305866126854219
416 9569256564897579387
417 10177955947657429126
418 10824589335235846275
419 11511472944519905782
420 12241061560488318025
421 13015956670251167403
422 13838915042985136411
423 14712857824313406294
424 15640880129295864710
425 16626261208172065230
426 17672475169473969911
427 18783202340735075312
428 19962341252033820472
429 21214021329227801140
430 22542616282958277107
431 23952758287472898206
432 25449352936451221565
433 27037595077711710748
434 28722985515353947674
435 30511348689755312250
436 32408851325674868239
437 34422022168161301317
438 36557772798603739725
439 38823419660734927840
440 41226707291409504835
441 43775832897005235371
442 46479472273236731920
443 49346807221237037629
444 52387554461222794960
445 55611996209699235724
446 59031012425631943963
447 62656114905853196593
448 66499483239936614118
449 70574002820395919017
450 74893304924046478628
451 79471809077407945829
452 84324767728436889958
453 89468313456077181391
454 94919508747356707552
455 100696398593811108525
456 106818065945529669122
457 113304690296782801273
458 120177609451297276663
459 127459384765401600205
460 135173869928272123693
461 143346283603987962455
462 152003286007367282161
463 161173059767261568481
464 170885395163719971910
465 181171780124410862862
466 192065495083097985517
467 203601713120206369990
468 215817605506853041185
469 228752453110298914046
470 242447763803145888506
471 256947396375768866691
472 272297691117953837116
473 288547607614649850878
474 305748869948481263433
475 323956119903665768899
476 343227078393947578782
477 363622715763692734019
478 385207431218437831969
479 408049242093680705693
480 432219983256046455836
481 457795517410963712426
482 484855956653356621767
483 513485896107121507521
484 543774660037365117557
485 575816561359610785682
486 609711174983109505952
487 645563625998438172686
488 683484893205889834108
489 723592129089118402870
490 766008996796870910503
491 810866025340555771299
492 858300983644555103947
493 908459274770280703425
494 961494351033423846476
495 1017568151459621509374
496 1076851562389993479836
497 1139524902817917505487
498 1205778435371011487727
499 1275812904669009348380
500 1349840104085515495407
501 1428083472808142988986
502 1510778724351853386565
503 1598174508599600726823
504 1690533108666142692744
505 1788131174856137530713
506 1891260497169000307868
507 2000228818837813857120
508 2115360692528683631840
509 2236998381924887280665
510 2365502810515283345774
511 2501254560571411280444
512 2644654924346818950331
513 2796127010768448911725
514 2956116909890987069121
515 3125094918697020514885
516 3303556830777033075687
517 3492025293815530771803
518 3691051237708688899620
519 3901215377616702826719
520 4123129795098872777542
521 4357439602048005386955
522 4604824690929340291953
523 4866001576494183868052
524 5141725332868510794729
525 5432791631684478132673
526 5740038885592048641310
527 6064350503364673558428
528 6406657261419373179795
529 6767939798564248375165
530 7149231239327575279734
531 7551619953338888102778
532 7976252456705976897831
533 8424336463579281360415
534 8897144094499057777757
535 9396015250507918165000
536 9922361160343206637081
537 10477668110559819167955
538 11063501366691627422522
539 11681509296254181855840
540 12333427702572705404076
541 13021084381282489947191
542 13746403909451646929054
543 14511412680319120407081
544 15318244194663120967023
545 16169144623049526264270
546 17066478651149834490644
547 18012735623756577834059
548 19010536000979962141042
549 20062638143765522959647
550 21171945443642569197187
551 22341513815501121768371
552 23574559569878059366666
553 24874467685368381773082
554 26244800499372123652632
555 27689306839786788072071
556 29211931617760398886880
557 30816825906301238753195
558 32508357526955930655257
559 34291122171749019570150
560 36169955084902685901587
561 38149943334157997792971
562 40236438698754550588742
563 42435071206770990911817
564 44751763351675392540873
565 47192745023946312153157
566 49764569190683802890976
567 52474128362533317556791
568 55328671884217595539084
569 58335824091793812828829
570 61503603376642144363947
571 64840442203461504220508
572 68355208126356872135518
573 72057225854851300486065
574 75956300418388253662423
575 80062741486150881776711
576 84387388895687076111356
577 88941639452638255428641
578 93737475060467870767246
579 98787492248482114188038
580 104104933162976724935481
581 109703718096369000559292
582 115598479625668586468574
583 121804598442339231511426
584 128338240952061611719664
585 135216398734328155597276
586 142456929948234552229070
587 150078602783027238741149
588 158101141048390868157749
589 166545272012483938517742
590 175432776592162764708856
591 184786542013748606765367
592 194630617059151090322217
593 204990270027030650898261
594 215892049535189956015917
595 227363848306278622447866
596 239434970075476165645277
597 252136199775813387915325
598 265499877153474523058353
599 279559973983599521706557
600 294352175053922172943293
601 309913963103026173535530
602 326284707896987345242849
603 343505759648981402472444
604 361620546983632909158622
605 380674679670158698917555
606 400716056345811778401074
607 421794977474985851691235
608 443964263787100364597083
609 467279380461936460643146
610 491798567329217880484064
611 517582975376605686218824
612 544696809858827854306591
613 573207480330002585868782
614 603185757920265353266788
615 634705940209261383694829
616 667846024048694344686379
617 702687886719848987178369
618 739317475812301441977518
619 777825008246208031834107
620 818305178861623351394180
621 860857379037116041424934
622 905585925801882659667419
623 952600301947222189281169
624 1002015407646159015946326
625 1053951824134729789492263
626 1108536090012500472603937
627 1165900990767913345044292
628 1226185862139387018353016
629 1289536907974689923171676
630 1356107533257867187669478
631 1426058693028441831090378
632 1499559257925985533364555
633 1576786397152743019848436
634 1657925979657181034136482
635 1743172994405396358754812
636 1832731990619536557100538
637 1926817538931279665569708
638 2025654714412910260823545
639 2129479602522636260978455
640 2238539829017818512856158
641 2353095114969521187361918
642 2473417858031648124487761
643 2599793741203744781588158
644 2732522370349551547339830
645 2871917941825775872134410
646 3018309941602057640486119
647 3172043877352577497549664
648 3333482045030154275666748
649 3503004331540817281892619
650 3681009055171548920115623
651 3867913845539317318731721
652 4064156564869007437456512
653 4270196272532236753292250
654 4486514234823822723264365
655 4713614982086725486291807
656 4952027415346922219129419
657 5202305964764192418322075
658 5465031802261892203998486
659 5740814110854635556300588
660 6030291413257040220063780
661 6334132962524774868013865
662 6653040197551260806189918
663 6987748266424701038238822
664 7339027620730909420894717
665 7707685684083054568378750
666 8094568598249801371753658
667 8500563050464470300692439
668 8926598185598735512903749
669 9373647607112289391661672
670 9842731470802390070842523
671 10334918675623260943245174
672 10851329155970544882304802
673 11393136280091706894884598
674 11961569359422517326552376
675 12557916273936698103782736
676 13183526218750434923571517
677 13839812577533420274785103
678 14528255928449602153213359
679 15250407188685686991207554
680 16007890903815486217047076
681 16802408688610043937715930
682 17635742826113847717812894
683 18509760032198477766670901
684 19426415393037697708954070
685 20387756483370667690360776
686 21395927673677024800272469
687 22453174634844503140974198
688 23561849049193574029989165
689 24724413537217604332483167
690 25943446809710124916087193
691 27221649055484988649001243
692 28561847575240342689915000
693 29967002672695039239519231
694 31440213814506320951752706
695 32984726071102445064656778
696 34603936850982479030585808
697 36301402941711377642913859
698 38080847871298955100159412
699 39946169604382546052339427
700 41901448588139486336416136
701 43950956163646632209078287
702 46099163358960556738094791
703 48350750081048048875218813
704 50710614724307664122479536
705 53183884214349375556812516
706 55775924506370231710794496
707 58492351558466401195582454
708 61339042800958056221571371
709 64322149123888546746356442
710 67448107405666559380515154
711 70723653606994370531782096
712 74155836455110196497997687
713 77752031744643932479366619
714 81519957282355171223531662
715 85467688504398638575489149
716 89603674795824151366014470
717 93936756543508171754844814
718 98476182954876704605192945
719 103231630676392463774660425
720 108213223247051677267440706
721 113431551423882573688768844
722 118897694417829654936417952
723 124623242080299172838719039
724 130620318082163611613300004
725 136901604129070998593402557
726 143480365258569208421848570
727 150370476266773229746076681
728 157586449314122297757734627
729 165143462762175554867570406
730 173057391295382152535605642
731 181344837384362762961272355
732 190023164149409950468095584
733 199110529685731825232380265
734 208625922914333298535883738
735 218589201025480158898926416
736 229021128584278076058551448
737 239943418371202963062893721
738 251378774033242094148297175
739 263350934624884239739818162
740 275884721121276835677693505
741 289006084989744486050449368
742 302742158909222121149718336
743 317121309731354596304171869
744 332173193780677207279977495
745 347928814595839062344821229
746 364420583217824072260299141
747 381682381136049832408810678
748 399749626007576336221082865
749 418659340269991459320975607
750 438450222773281818035168578
751 459162723561776134756703324
752 480839121942413683529765327
753 503523607981849310760862214
754 527262367580532376968731840
755 552103671278676172731698624
756 578097966955160356615836240
757 605297976587751642977006034
758 633758797249697169464745750
759 663538006525697885188593632
760 694695772537528396988507000
761 727294968778183446697659864
762 761401293961330800976687372
763 797083397102179655361929742
764 834413008054468618221369445
765 873465073738381520204106937
766 914317900303549050350494080
767 957053301482237387388200963
768 1001756753397993957075691946
769 1048517556106871996773611044
770 1097429002159413548877672382
771 1148588552484405538457806175
772 1202098019907446097107849581
773 1258063760631258047675760370
774 1316596874017755427671284028
775 1377813411026921291617716542
776 1441834591681759125282658916
777 1508787031944880272132166548
778 1578802980407725027729450706
779 1652020565211065676623651490
780 1728584051632210167851267256
781 1808644110793437544601830696
782 1892358099964414416417798925
783 1979890354952036323616398530
784 2071412495090925657795623338
785 2167103741370224633118770679
786 2267151248253811220572325114
787 2371750449775325787429169897
788 2481105420512730014482866418
789 2595429252073384689975016859
790 2714944445745965786097990749
791 2839883322003972990588142748
792 2970488447573083930648534610
793 3107013080805389745649716701
794 3249721636133393968578157738
795 3398890168409979114476681770
796 3554806877972934733547692005
797 3717772637308711076742369490
798 3888101540225206799181708251
799 4066121474482442246924710001
800 4252174718868098217993536985
801 4446618565747158924161468583
802 4649825970156258153968228246
803 4862186226559064785431061711
804 5084105674423904088042297779
805 5316008433834310523727017177
806 5558337172391857950037131356
807 5811553904724181250846794774
808 6076140825963856980481696518
809 6352601180621779001841460086
810 6641460168335860973096614175
811 6943265888038624320277312439
812 7258590322149234926457653494
813 7588030362463423888933736170
814 7932208879481937105941378891
815 8291775836991593927293936879
816 8667409453785877503528260193
817 9059817414491429878709334124
818 9469738131545763002229820489
819 9897942060457450020069018834
820 10345233070565595165561403593
821 10812449873608363422395833512
822 11300467512503021367561052906
823 11810198912840522206881082113
824 12342596499698058451282228482
825 12898653882481800670286389188
826 13479407610620782293192941493
827 14085939003050562501916862000
828 14719376054543073502515911234
829 15380895422066324313553108793
830 16071724494485176420097044107
831 16793143549052040151358410046
832 17546487998274448093202208122
833 18333150730895298505660169882
834 19154584550871092382334820465
835 20012304718394429598892964196
836 20907891597168911083365116275
837 21842993412318614663181416484
838 22819329123489546247650147804
839 23838691417888618703882342616
840 24902949828195378951752387132
841 26014053980485118969219450161
842 27174036977507276513302323210
843 28385018922882935467364460263
844 29649210592007368525925730208
845 30968917255681279377510822133
846 32346542662734758044500358950
847 33784593188164913808031686058
848 35285682153568199378699448144
849 36852534326926165803627321367
850 38487990609084715144834836779
851 40195012914567079055310285726
852 41976689254665068488442381346
853 43836239031077527325314426126
854 45777018548694076010291536516
855 47802526756472777710559486613
856 49916411225716341655470383684
857 52122474375430268128262563958
858 54424679954831300603444325396
859 56827159793483832235331750798
860 59334220829958173390150534369
861 61950352430346785776338899073
862 64680234008424649060665571180
863 67528742959717657460109984573
864 70500962922229504378095058292
865 73602192377093598248027540608
866 76837953602942525144517288757
867 80214001998345054135634535813
868 83736335787229205835330516933
869 87411206122812060208345615977
870 91245127606171442956416011617
871 95244889236244996958197032803
872 99417565808706199352610563656
873 103770529781869276258754557585
874 108311463628492550067031248277
875 113048372693108280106080054606
876 117989598575282415272843341025
877 123143833060026768259287201925
878 128520132617423831275188914469
879 134127933494408885300255680613
880 139977067422559052547669048757
881 146077777966693862530762767086
882 152440737540069506835290400220
883 159077065112979914684313727079
884 165998344642633727015486361000
885 173216644253289218703860300093
886 180744536196769685059107828117
887 188595117624683238031344977722
888 196782032204902605192197523034
889 205319492616157353147963729234
890 214222303955920963034135849421
891 223505888098174893184144485324
892 233186309039067862266932207857
893 243280299269999230626397406849
894 253805287219205881044892035610
895 264779425804562262587142783897
896 276221622141977187834453125238
897 288151568455530205660223744472
898 300589774237297373512582618482
899 313557599706714527113734373271
900 327077290621276641536566040904
901 341172014492420042675854260818
902 355865898262539441244834956811
903 371184067501301502008380657461
904 387152687181688678992912909605
905 403799004098590946570268226095
906 421151390995214897928392407872
907 439239392465151290213029838639
908 458093772700587800751019666074
909 477746565159927665549522241385
910 498231124230929497163069083937
911 519582178968475494140005340210
912 541835888989155077212571890246
913 565029902608077823926863401194
914 589203417306652096203102167453
915 614397242623545721160069334769
916 640653865564629151879218791030
917 668017518631454230197736550812
918 696534250571687569498683003539
919 726251999958964098299299894387
920 757220671713795867705489928171
921 789492216681534284457195159638
922 823120714387880664758389646425
923 858162459097144038540453974208
924 894676049303294336963686205911
925 932722480788930408226870836163
926 972365243392511206432651917156
927 1013670421629665392426504514951
928 1056706799320032482066747544511
929 1101545968376981609684664487823
930 1148262441923632397548079187440
931 1196933771904954162600337086023
932 1247640671372272567232064700962
933 1300467141623358626801422171947
934 1355500604388338816543064291890
935 1412832039259042822559909377815
936 1472556126567019537058765597070
937 1534771395923402500205192844500
938 1599580380642012519009781788739
939 1667089778275652488437129125731
940 1737410617504393886144290685459
941 1810658431623885610609259901740
942 1886953438891247079938615718870
943 1966420729996053388007472613018
944 2049190462934190940162791028082
945 2135398065573077160883551994592
946 2225184446207804415290710976781
947 2318696212419311474497542285254
948 2416085898557609138871776028727
949 2517512202185520990372642619899
950 2623140229831245656096891475819
951 2733141752411440395165938636012
952 2847695470700363673683713549278
953 2966987291235039904691662331451
954 3091210613061315427047293374126
955 3220566625741210885268588873892
956 3355264619058030396448593385596
957 3495522304872418939165130491192
958 3641566151599851334217700491119
959 3793631731798052908205463182695
960 3951964083371474513494286851503
961 4116818084919344478590326114165
962 4288458845773874267168219802190
963 4467162111296082508378612413006
964 4653214684018296418757490886171
965 4846914861244878145105092415375
966 5048572889745974716520925304926
967 5258511438203300482896938354901
968 5477066088091994238848445533881
969 5704585843708655191721074488226
970 5941433662082612135254560694895
971 6187987003535533711120827207898
972 6444638403683499488955562807565
973 6711796067705846881603727250097
974 6989884487736337954630074313709
975 7279345084264688624989961023469
976 7580636872470116105766434079166
977 7894237154443535424100382649779
978 8220642238291213074472147421680
979 8560368185150323640068353989337
980 8913951585185789215113148889284
981 9281950363678282123864897473074
982 9664944618355169406196197734884
983 10063537489159756024672708571387
984 10478356061699268270788109698909
985 10910052305658906009468018530055
986 11359304049517802535762100259418
987 11826815992953174598729558353401
988 12313320758371137652801446119528
989 12819579983056928077400243023254
990 13346385453493424727138457433945
991 13894560283455237709999664797733
992 14464960137546037146667591822421
993 15058474501909586119367612227834
994 15676028003909919084346706038278
995 16318581782643644110641016024417
996 16987134912217238009413792292073
997 17682725879794840149936209222281
998 18406434120497221677522391965947
999 19159381611310723297720830956459
1000 19942734526245799495023800115887