0 1
1 1
2 2
3 3
4 4
5 6
6 8
7 10
8 14
9 17
10 22
11 27
12 33
13 41
14 49
15 59
16 71
17 83
18 99
19 115
20 134
21 157
22 180
23 208
24 239
25 272
26 312
27 353
28 400
29 453
30 509
31 573
32 642
33 717
34 803
35 892
36 993
37 1102
38 1219
39 1350
40 1489
41 1640
42 1808
43 1983
44 2178
45 2386
46 2609
47 2854
48 3113
49 3393
50 3697
51 4017
52 4367
53 4737
54 5134
55 5564
56 6016
57 6504
58 7025
59 7575
60 8171
61 8797
62 9466
63 10183
64 10936
65 11744
66 12599
67 13502
68 14471
69 15486
70 16568
71 17715
72 18921
73 20207
74 21559
75 22987
76 24506
77 26094
78 27782
79 29558
80 31425
81 33405
82 35478
83 37664
84 39973
85 42386
86 44939
87 47613
88 50421
89 53384
90 56478
91 59735
92 63154
93 66727
94 70492
95 74422
96 78543
97 82871
98 87383
99 92122
100 97075
101 102247
102 107677
103 113331
104 119251
105 125442
106 131890
107 138644
108 145681
109 153022
110 160703
111 168686
112 177031
113 185727
114 194777
115 204232
116 214059
117 224299
118 234978
119 246065
120 257632
121 269652
122 282150
123 295175
124 308687
125 322751
126 337374
127 352543
128 368337
129 384715
130 401727
131 419413
132 437736
133 456781
134 476535
135 497011
136 518287
137 540313
138 563168
139 586873
140 611409
141 636872
142 663231
143 690531
144 718844
145 748115
146 778455
147 809859
148 842337
149 875991
150 910775
151 946767
152 984026
153 1022508
154 1062346
155 1103511
156 1146051
157 1190063
158 1235495
159 1282464
160 1331000
161 1381090
162 1432880
163 1486318
164 1541498
165 1598504
166 1657286
167 1718000
168 1780644
169 1845247
170 1911959
171 1980713
172 2051650
173 2124830
174 2200230
175 2278027
176 2358192
177 2440808
178 2526015
179 2613743
180 2704186
181 2797362
182 2893299
183 2992185
184 3093967
185 3198788
186 3306767
187 3417850
188 3532274
189 3650019
190 3771174
191 3895924
192 4024208
193 4156230
194 4292072
195 4431728
196 4575455
197 4723204
198 4875138
199 5031422
200 5192004
201 5357150
202 5526893
203 5701298
204 5880631
205 6064820
206 6254106
207 6448622
208 6648354
209 6853610
210 7064384
211 7280822
212 7503182
213 7731392
214 7965771
215 8206400
216 8453340
217 8706918
218 8967099
219 9234124
220 9508221
221 9789345
222 10077886
223 10373869
224 10677452
225 10988964
226 11308356
227 11635967
228 11971979
229 12316413
230 12669701
231 13031827
232 13403059
233 13783708
234 14173739
235 14573586
236 14983367
237 15403209
238 15833562
239 16274383
240 16726060
241 17188861
242 17662808
243 18148409
244 18645723
245 19155005
246 19676699
247 20210762
248 20757705
249 21317730
250 21890964
251 22477955
252 23078724
253 23693667
254 24323197
255 24967310
256 25626626
257 26301275
258 26991528
259 27697943
260 28420527
261 29159823
262 29916186
263 30689709
264 31481085
265 32290387
266 33118051
267 33964619
268 34830120
269 35715243
270 36620262
271 37545419
272 38491447
273 39458387
274 40446850
275 41457333
276 42489942
277 43545484
278 44624160
279 45726396
280 46852928
281 48003803
282 49179812
283 50381374
284 51608743
285 52862798
286 54143689
287 55452051
288 56788592
289 58153410
290 59547468
291 60971092
292 62424737
293 63909319
294 65424970
295 66972538
296 68552671
297 70165596
298 71812399
299 73493335
300 75209095
301 76960586
302 78747978
303 80572334
304 82434203
305 84334022
306 86272950
307 88251201
308 90269726
309 92329385
310 94430450
311 96574173
312 98761009
313 100991654
314 103267296
315 105588159
316 107955451
317 110369952
318 112832132
319 115343364
320 117904046
321 120515167
322 123177895
323 125892534
324 128660542
325 131482586
326 134359418
327 137292483
328 140282160
329 143329748
330 146436355
331 149602451
332 152829698
333 156118675
334 159470459
335 162886515
336 166367275
337 169914342
338 173528725
339 177211171
340 180963468
341 184786154
342 188680669
343 192648441
344 196690042
345 200807358
346 205001282
347 209272922
348 213624137
349 218055478
350 222568757
351 227165322
352 231846000
353 236612887
354 241466805
355 246409265
356 251442136
357 256566078
358 261783260
359 267094911
360 272502234
361 278007452
362 283611378
363 289315958
364 295123007
365 301033410
366 307049645
367 313172834
368 319404633
369 325747326
370 332201797
371 338770427
372 345454934
373 352256563
374 359178008
375 366220349
376 373385735
377 380676448
378 388093557
379 395639849
380 403316921
381 411126499
382 419071411
383 427152771
384 435373242
385 443735039
386 452239564
387 460889933
388 469687661
389 478635027
390 487734916
391 496988585
392 506399207
393 515968880
394 525699492
395 535594386
396 545655074
397 555884430
398 566285323
399 576859296
400 587609977
401 598539353
402 609649916
403 620945142
404 632426645
405 644097903
406 655961701
407 668020053
408 680276931
409 692734277
410 705395258
411 718263397
412 731340550
413 744630779
414 758136745
415 771861093
416 785808034
417 799979566
418 814379560
419 829011509
420 843877694
421 858982668
422 874329015
423 889920118
424 905760319
425 921851816
426 938199180
427 954805807
428 971674612
429 988810507
430 1006216090
431 1023895552
432 1041853275
433 1060091825
434 1078616430
435 1097430377
436 1116537371
437 1135942577
438 1155648733
439 1175660850
440 1195983276
441 1216619169
442 1237574283
443 1258851879
444 1280456554
445 1302393605
446 1324666094
447 1347279838
448 1370239082
449 1393547804
450 1417212144
451 1441235450
452 1465623278
453 1490380956
454 1515512081
455 1541023195
456 1566918472
457 1593202860
458 1619882761
459 1646961781
460 1674446430
461 1702341992
462 1730652866
463 1759386148
464 1788546062
465 1818138625
466 1848170372
467 1878645391
468 1909571107
469 1940952714
470 1972795646
471 2005107409
472 2037892423
473 2071157820
474 2104910167
475 2139154298
476 2173898422
477 2209147729
478 2244908824
479 2281189484
480 2317994548
481 2355332242
482 2393209092
483 2431630973
484 2470606686
485 2510141572
486 2550243502
487 2590920387
488 2632177754
489 2674024845
490 2716468147
491 2759514801
492 2803174048
493 2847451569
494 2892356525
495 2937896864
496 2984079118
497 3030913365
498 3078406188
499 3126566123
500 3175402700
501 3224922215
502 3275135076
503 3326049209
504 3377672461
505 3430015548
506 3483085339
507 3536891847
508 3591444747
509 3646751280
510 3702822969
511 3759667782
512 3817295095
513 3875716088
514 3934938168
515 3994972827
516 4055829791
517 4117517609
518 4180048699
519 4243431254
520 4307676304
521 4372795333
522 4438796615
523 4505693039
524 4573494367
525 4642210766
526 4711855343
527 4782436757
528 4853967743
529 4926459951
530 4999922920
531 5074370740
532 5149813342
533 5226262711
534 5303732451
535 5382232008
536 5461775800
537 5542375559
538 5624042481
539 5706791618
540 5790633300
541 5875581442
542 5961649980
543 6048849540
544 6137196084
545 6226701483
546 6317378887
547 6409244087
548 6502308121
549 6596586855
550 6692094427
551 6788843104
552 6886850138
553 6986127737
554 7086691195
555 7188556841
556 7291736807
557 7396248853
558 7502107270
559 7609326369
560 7717924446
561 7827914330
562 7939313544
563 8052138791
564 8166403770
565 8282127923
566 8399325836
567 8518014143
568 8638211938
569 8759933064
570 8883197265
571 9008021497
572 9134421538
573 9262418217
574 9392026676
575 9523266053
576 9656156030
577 9790711924
578 9926955585
579 10064904245
580 10204576156
581 10345993276
582 10489171661
583 10634132998
584 10780897406
585 10929482232
586 11079911141
587 11232201873
588 11386375415
589 11542454591
590 11700456853
591 11860406389
592 12022323664
593 12186228593
594 12352146344
595 12520095492
596 12690099915
597 12862183093
598 13036364422
599 13212670397
600 13391121953
601 13571741946
602 13754556768
603 13939586282
604 14126857261
605 14316393709
606 14508217589
607 14702357351
608 14898834716
609 15097675727
610 15298907733
611 15502552448
612 15708639441
613 15917193212
614 16128238833
615 16341806390
616 16557918793
617 16776605387
618 16997894280
619 17221809684
620 17448383680
621 17677641496
622 17909611665
623 18144325606
624 18381807979
625 18622091397
626 18865204614
627 19111175018
628 19360036810
629 19611816345
630 19866545844
631 20124257785
632 20384979243
633 20648745916
634 20915587284
635 21185534438
636 21458623358
637 21734882037
638 22014346447
639 22297049949
640 22583022778
641 22872303340
642 23164922189
643 23460914445
644 23760317555
645 24063161819
646 24369486867
647 24679326891
648 24992715983
649 25309694851
650 25630295614
651 25954557604
652 26282519473
653 26614214607
654 26949686008
655 27288968914
656 27632101767
657 27979127215
658 28330079578
659 28685002412
660 29043935429
661 29406915918
662 29773989815
663 30145193858
664 30520571144
665 30900165948
666 31284015566
667 31672167610
668 32064662903
669 32461543326
670 32862857334
671 33268643763
672 33678950492
673 34093823187
674 34513303019
675 34937441261
676 35366280199
677 35799866773
678 36238251574
679 36681476307
680 37129593591
681 37582650380
682 38040692589
683 38503774680
684 38971940964
685 39445243711
686 39923735336
687 40407461322
688 40896478748
689 41390836057
690 41890584571
691 42395781496
692 42906473915
693 43422719488
694 43944572255
695 44472082484
696 45005311217
697 45544308884
698 46089132648
699 46639842075
700 47196487923
701 47759133118
702 48327833324
703 48902644472
704 49483631083
705 50070846261
706 50664353214
707 51264213588
708 51870482864
709 52483228827
710 53102509139
711 53728386012
712 54360926984
713 55000188738
714 55646240525
715 56299145919
716 56958966207
717 57625773479
718 58299628026
719 58980598743
720 59668755806
721 60364160518
722 61066887945
723 61777003740
724 62494575854
725 63219680182
726 63952380481
727 64692752462
728 65440868700
729 66196796308
730 66960615631
731 67732394949
732 68512209461
733 69300138392
734 70096250035
735 70900626836
736 71713343699
737 72534474675
738 73364104805
739 74202305771
740 75049160365
741 75904750780
742 76769151056
743 77642450002
744 78524725202
745 79416058460
746 80316538984
747 81226242886
748 82145260602
749 83073677112
750 84011573507
751 84959044320
752 85916170543
753 86883042275
754 87859752425
755 88846382766
756 89843031188
757 90849785543
758 91866735095
759 92893979508
760 93931604122
761 94979707587
762 96038386206
763 97107728792
764 98187840164
765 99278811613
766 100380741339
767 101493733595
768 102617879294
769 103753285608
770 104900052128
771 106058276087
772 107228068545
773 108409525127
774 109602753461
775 110807861940
776 112024948461
777 113254128387
778 114495504895
779 115749184725
780 117015284561
781 118293905506
782 119585164783
783 120889174680
784 122206041617
785 123535888480
786 124878822815
787 126234961588
788 127604426566
789 128987325753
790 130383785829
791 131793923009
792 133217853649
793 134655707446
794 136107597400
795 137573651108
796 139053995014
797 140548745642
798 142058038620
799 143581994644
800 145120741033
801 146674413654
802 148243132345
803 149827035401
804 151426253784
805 153040914196
806 154671160446
807 156317118714
808 157978927945
809 159656729656
810 161350652148
811 163060844130
812 164787441337
813 166530582037
814 168290417497
815 170067080685
816 171860722466
817 173671489683
818 175499520916
819 177344974602
820 179207992069
821 181088724116
822 182987328826
823 184903947578
824 186838743116
825 188791867574
826 190763471537
827 192753722364
828 194762768194
829 196790772942
830 198837901026
831 200904304090
832 202990156290
833 205095615589
834 207220845911
835 209366022787
836 211531302737
837 213716862975
838 215922874023
839 218149499777
840 220396924971
841 222665314483
842 224954846483
843 227265704053
844 229598053953
845 231952086511
846 234327978528
847 236725907892
848 239146069092
849 241588635384
850 244053799650
851 246541752119
852 249052671892
853 251586761733
854 254144205578
855 256725196567
856 259329938180
857 261958613914
858 264611431426
859 267288587984
860 269990277138
861 272716713165
862 275468088491
863 278244612337
864 281046496592
865 283873937108
866 286727155939
867 289606357875
868 292511752609
869 295443565091
870 298401997991
871 301387276940
872 304399621947
873 307439243545
874 310506377308
875 313601236731
876 316724048833
877 319875048493
878 323054450773
879 326262497631
880 329499417286
881 332765437111
882 336060805252
883 339385745539
884 342740503031
885 346125322028
886 349540432378
887 352986091762
888 356462537455
889 359970015285
890 363508785111
891 367079083184
892 370681172798
893 374315307520
894 377981734487
895 381680726083
896 385412530145
897 389177412064
898 392975642710
899 396807473190
900 400673184761
901 404573040648
902 408507307426
903 412476271221
904 416480192377
905 420519356410
906 424594044813
907 428704526229
908 432851099032
909 437034037340
910 441253628692
911 445510172100
912 449803942854
913 454135246637
914 458504375596
915 462911618526
916 467357289825
917 471841676341
918 476365087575
919 480927834792
920 485530210980
921 490172541473
922 494855129868
923 499578287190
924 504342342881
925 509147598838
926 513994386920
927 518883030418
928 523813842941
929 528787168418
930 533803323529
931 538862642958
932 543965470386
933 549112125535
934 554302962472
935 559538316840
936 564818525513
937 570143949909
938 575514921979
939 580931800904
940 586394944095
941 591904692182
942 597461420656
943 603065478759
944 608717228604
945 614417048118
946 620165287245
947 625962329899
948 631808547185
949 637704303741
950 643649995298
951 649645986720
952 655692666687
953 661790428901
954 667939644426
955 674140721515
956 680394045705
957 686700008248
958 693059023998
959 699471476032
960 705937780251
961 712458345793
962 719033568248
963 725663879155
964 732349680202
965 739091391120
966 745889444939
967 752744246088
968 759656237725
969 766625844667
970 773653490224
971 780739627984
972 787884678221
973 795089090317
974 802353314861
975 809677781145
976 817062958891
977 824509289849
978 832017227551
979 839587246510
980 847219788640
981 854915333430
982 862674348912
983 870497292897
984 878384660415
985 886336912344
986 894354534183
987 902438020514
988 910587838424
989 918804497304
990 927088483285
991 935440285887
992 943860424215
993 952349381148
994 960907675119
995 969535820348
996 978234312989
997 987003691335
998 995844461418
999 1004757146845
1000 1013742289697