0 1
1 1
2 2
3 3
4 4
5 6
6 6
7 9
8 11
9 14
10 16
11 20
12 23
13 27
14 31
15 35
16 43
17 47
18 55
19 61
20 70
21 78
22 88
23 98
24 111
25 123
26 136
27 152
28 168
29 187
30 204
31 225
32 248
33 271
34 296
35 325
36 356
37 387
38 418
39 455
40 495
41 537
42 581
43 629
44 678
45 732
46 787
47 851
48 918
49 986
50 1056
51 1133
52 1217
53 1307
54 1399
55 1498
56 1600
57 1708
58 1823
59 1950
60 2083
61 2218
62 2356
63 2506
64 2671
65 2842
66 3025
67 3211
68 3409
69 3610
70 3830
71 4067
72 4316
73 4568
74 4829
75 5105
76 5406
77 5722
78 6051
79 6393
80 6746
81 7112
82 7506
83 7928
84 8372
85 8821
86 9282
87 9770
88 10293
89 10845
90 11423
91 12013
92 12621
93 13255
94 13930
95 14653
96 15410
97 16176
98 16960
99 17785
100 18663
101 19591
102 20553
103 21545
104 22560
105 23616
106 24734
107 25933
108 27174
109 28439
110 29728
111 31076
112 32509
113 34026
114 35595
115 37204
116 38850
117 40557
118 42366
119 44282
120 46270
121 48301
122 50360
123 52517
124 54796
125 57199
126 59689
127 62243
128 64838
129 67535
130 70375
131 73378
132 76499
133 79669
134 82896
135 86259
136 89808
137 93544
138 97408
139 101346
140 105371
141 109528
142 113898
143 118515
144 123298
145 128161
146 133123
147 138260
148 143662
149 149346
150 155217
151 161203
152 167304
153 173602
154 180223
155 187188
156 194394
157 201727
158 209179
159 216887
160 225004
161 233478
162 242246
163 251189
164 260296
165 269680
166 279534
167 289857
168 300546
169 311405
170 322443
171 333839
172 345784
173 358285
174 371203
175 384343
176 397730
177 411531
178 425953
179 441059
180 456667
181 472506
182 488623
183 505255
184 522633
185 540796
186 559541
187 578622
188 598040
189 618004
190 638849
191 660655
192 683132
193 706001
194 729237
195 753154
196 778157
197 804249
198 831083
199 858442
200 886231
201 914803
202 944588
203 975676
204 1007714
205 1040309
206 1073406
207 1107489
208 1142976
209 1179941
210 1218033
211 1256772
212 1296102
213 1336565
214 1378646
215 1422511
216 1467723
217 1513662
218 1560288
219 1608264
220 1658153
221 1710050
222 1763441
223 1817764
224 1872970
225 1929640
226 1988528
227 2049843
228 2112903
229 2177002
230 2242117
231 2308930
232 2378345
233 2450550
234 2524753
235 2600227
236 2676925
237 2755570
238 2837222
239 2922075
240 3009300
241 3097939
242 3187910
243 3280268
244 3376122
245 3475560
246 3577799
247 3681810
248 3787349
249 3895580
250 4007781
251 4124158
252 4243812
253 4365410
254 4488795
255 4615345
256 4746534
257 4882547
258 5022247
259 5164208
260 5308385
261 5456077
262 5608963
263 5767544
264 5930385
265 6095779
266 6263781
267 6435911
268 6613993
269 6798505
270 6987901
271 7180330
272 7375721
273 7575773
274 7782710
275 7997065
276 8217094
277 8440659
278 8667488
279 8899739
280 9140016
281 9388512
282 9643384
283 9902531
284 10165513
285 10434616
286 10712858
287 11000633
288 11295797
289 11595731
290 11900036
291 12211421
292 12533095
293 12865645
294 13206691
295 13553187
296 13904850
297 14264665
298 14636001
299 15019870
300 15413510
301 15813151
302 16218675
303 16633663
304 17061853
305 17504131
306 17957511
307 18418083
308 18885444
309 19363284
310 19856106
311 20365018
312 20886445
313 21416170
314 21953633
315 22502996
316 23069688
317 23654627
318 24253578
319 24862140
320 25479632
321 26110444
322 26760714
323 27431758
324 28118910
325 28816859
326 29524995
327 30248724
328 30994342
329 31763154
330 32550426
331 33350018
332 34161082
333 34989834
334 35843243
335 36722969
336 37623961
337 38538864
338 39466642
339 40414595
340 41390540
341 42395999
342 43425108
343 44470326
344 45530615
345 46613390
346 47727748
347 48875865
348 50050571
349 51243342
350 52453405
351 53688691
352 54959424
353 56268254
354 57607048
355 58966572
356 60345981
357 61753831
358 63201526
359 64692137
360 66216763
361 67764588
362 69334382
363 70936798
364 72584395
365 74279577
366 76013285
367 77773910
368 79559305
369 81381225
370 83253875
371 85179845
372 87149249
373 89149075
374 91176899
375 93245998
376 95372229
377 97558561
378 99793501
379 102062615
380 104363895
381 106711118
382 109121778
383 111600554
384 114134202
385 116705815
386 119314243
387 121974988
388 124706573
389 127514054
390 130383070
391 133295058
392 136248424
393 139260259
394 142351499
395 145527797
396 148773538
397 152068169
398 155408850
399 158815052
400 162310911
401 165901151
402 169568417
403 173291577
404 177066812
405 180915029
406 184863771
407 188918534
408 193059430
409 197262777
410 201524816
411 205868795
412 210324461
413 214898330
414 219569114
415 224310043
416 229117452
417 234017083
418 239040338
419 244195775
420 249460339
421 254802436
422 260218466
423 265738585
424 271396945
425 277202139
426 283129321
427 289144535
428 295242993
429 301456932
430 307824977
431 314356624
432 321023550
433 327789549
434 334649288
435 341637377
436 348797935
437 356141163
438 363634328
439 371238934
440 378949177
441 386801433
442 394844883
443 403092443
444 411507682
445 420046804
446 428704287
447 437521813
448 446551722
449 455807005
450 465249543
451 474830686
452 484543355
453 494434944
454 504562393
455 514939726
456 525527157
457 536269941
458 547158658
459 558246803
460 569597371
461 581224252
462 593083626
463 605117138
464 617314792
465 629733181
466 642443002
467 655461536
468 668737718
469 682206885
470 695860533
471 709759227
472 723979796
473 738543076
474 753392290
475 768456802
476 783728737
477 799272915
478 815172700
479 831452246
480 848050243
481 864887178
482 881953128
483 899322732
484 917087901
485 935271624
486 953809031
487 972615020
488 991675037
489 1011070969
490 1030905654
491 1051202104
492 1071889555
493 1092876582
494 1114146494
495 1135789191
496 1157918165
497 1180558496
498 1203631340
499 1227037003
500 1250758849
501 1274892125
502 1299559906
503 1324795149
504 1350510875
505 1376593435
506 1403028629
507 1429922644
508 1457405859
509 1485514730
510 1514155683
511 1543203181
512 1572641892
513 1602588815
514 1633186342
515 1664474165
516 1696351486
517 1728682008
518 1761445285
519 1794769597
520 1828814019
521 1863617807
522 1899069884
523 1935027797
524 1971466974
525 2008523557
526 2046376390
527 2085069567
528 2124477324
529 2164444125
530 2204944946
531 2246127897
532 2288186708
533 2331170910
534 2374944919
535 2419337740
536 2464324227
537 2510066877
538 2556771251
539 2604494051
540 2653092123
541 2702371962
542 2752305410
543 2803076889
544 2854908075
545 2907857789
546 2961774353
547 3016448100
548 3071844250
549 3128162791
550 3185648506
551 3244364764
552 3304143118
553 3364759211
554 3426176909
555 3488609875
556 3552329115
557 3617404129
558 3683644973
559 3750812077
560 3818868910
561 3888039623
562 3958620113
563 4030694695
564 4104054622
565 4178434675
566 4253798862
567 4330394472
568 4408538904
569 4488321060
570 4569519033
571 4651842318
572 4735247672
573 4820010876
574 4906476594
575 4994736912
576 5084558311
577 5175624602
578 5267881025
579 5361632211
580 5457255131
581 5554842531
582 5654142432
583 5754818741
584 5856810174
585 5960441397
586 6066126885
587 6173974428
588 6283701754
589 6394940039
590 6507631461
591 6622124245
592 6738864791
593 6857978989
594 6979157639
595 7101997795
596 7226445406
597 7352875310
598 7481764169
599 7613253926
600 7747013059
601 7882597151
602 8019945383
603 8159473589
604 8301699931
605 8446769883
606 8594331579
607 8743910527
608 8895427207
609 9049331616
610 9206196601
611 9366172128
612 9528873964
613 9693797200
614 9860852104
615 10030525166
616 10203444811
617 10379770883
618 10559080583
619 10740831340
620 10924931305
621 11111897941
622 11302407501
623 11496649064
624 11694166218
625 11894357291
626 12097132737
627 12303060819
628 12512858130
629 12726732383
630 12944198756
631 13164595478
632 13387825436
633 13614512988
634 13845431958
635 14080805456
636 14320115376
637 14562646835
638 14808285424
639 15057708438
640 15311761934
641 15570675608
642 15833884237
643 16100636108
644 16370803829
645 16645102455
646 16924464220
647 17209145957
648 17498519429
649 17791774046
650 18088779028
651 18390299936
652 18697344550
653 19010199275
654 19328185010
655 19650420611
656 19976773039
657 20308074230
658 20645397422
659 20989055317
660 21338329924
661 21692252275
662 22050672926
663 22414516095
664 22784933595
665 23162249395
666 23545709392
667 23934271129
668 24327753869
669 24727156223
670 25133732686
671 25547828658
672 25968624018
673 26395003862
674 26826776509
675 27265010674
676 27711074049
677 28165345366
678 28626916844
679 29094594714
680 29568189289
681 30048827936
682 30537983178
683 31036093648
684 31542172860
685 32054919139
686 32574145537
687 33101072871
688 33637272712
689 34183218205
690 34737861066
691 35299789674
692 35868789249
693 36446196097
694 37033709594
695 37631824690
696 38239430818
697 38855010405
698 39478304136
699 40110766887
700 40754246129
701 41409245858
702 42074572214
703 42748621670
704 43431106384
705 44123576445
706 44828039580
707 45545054957
708 46273316616
709 47011088823
710 47758082837
711 48515954457
712 49286853483
713 50071414346
714 50868227777
715 51675405572
716 52492664809
717 53321790300
718 54165067429
719 55023197297
720 55894677570
721 56777447396
722 57671203191
723 58577896159
724 59499981893
725 60438193000
726 61390936476
727 62356017675
728 63333073337
729 64324194785
730 65332058203
731 66357434382
732 67398598180
733 68453223508
734 69520908559
735 70603888232
736 71705076914
737 72825301246
738 73962674804
739 75114713008
740 76281000319
741 77463912237
742 78666575137
743 79889917242
744 81131914957
745 82389864969
746 83663349085
747 84954946378
748 86267969252
749 87603420299
750 88959165726
751 90332267436
752 91722264269
753 93131965301
754 94564921811
755 96022203051
756 97501548558
757 98999798351
758 100516425306
759 102054461912
760 103617749612
761 105207405771
762 106820987034
763 108455156577
764 110109349227
765 111786772339
766 113491593995
767 115225043914
768 116984444361
769 118766223652
770 120569807381
771 122398600243
772 124257075520
773 126146598389
774 128064289941
775 130006300065
776 131972040551
777 133965174080
778 135990465810
779 138049392322
780 140138902214
781 142254820391
782 144396494515
783 146567931024
784 148774232292
785 151016929662
786 153292814315
787 155597432252
788 157930020989
789 160294887144
790 162697537961
791 165139589171
792 167617597202
793 170126825416
794 172666450793
795 175241066390
796 177856618213
797 180514863855
798 183212054568
799 185943122312
800 188707238814
801 191509268101
802 194355568996
803 197248118105
804 200182877692
805 203154366440
806 206161765751
807 209210305125
808 212306734650
809 215453184594
810 218645374888
811 221877405056
812 225148372390
813 228463928649
814 231831317974
815 235252791803
816 238723820584
817 242238106889
818 245794599859
819 249399381601
820 253060280355
821 256779627993
822 260552564683
823 264372446164
824 268238120513
825 272156052482
826 276134692273
827 280176565688
828 284276410040
829 288427113649
830 292627499395
831 296884449016
832 301206972463
833 305597861214
834 310051495326
835 314560205170
836 319122798205
837 323746659718
838 328441342645
839 333209887681
840 338046344401
841 342942408883
842 347896803977
843 352917538518
844 358014816334
845 363191837821
846 368442307795
847 373757394476
848 379135648951
849 384585624470
850 390118316230
851 395737102460
852 401435216507
853 407203321410
854 413039853891
855 418953890989
856 424957296394
857 431053708853
858 437235795593
859 443493626599
860 449825581962
861 456241275517
862 462753393721
863 469365943387
864 476071080066
865 482858110773
866 489725383995
867 496683248414
868 503745148015
869 510915363490
870 518185630677
871 525544451047
872 532990017359
873 540533511079
874 548189274537
875 555961836768
876 563842494708
877 571818966004
878 579889205275
879 588065207835
880 596362372780
881 604785459785
882 613325149310
883 621968457024
884 630713200422
885 639572085807
886 648561674937
887 657687142087
888 666938387037
889 676301564345
890 685774468635
891 695370557493
892 705107486530
893 714990931444
894 725010091661
895 735150138513
896 745408824452
897 755800520881
898 766343974694
899 777045306277
900 787893092424
901 798871398499
902 809977766202
903 821227723044
904 832641286737
905 844224855443
906 855966393492
907 867848981159
908 879869816425
909 892045506340
910 904397535591
911 916932622159
912 929637921709
913 942495539191
914 955502460050
915 968676334546
916 982040200877
917 995601286295
918 1009345773349
919 1023254606037
920 1037324694610
921 1051574721415
922 1066029208513
923 1080696124591
924 1095560713935
925 1110602493920
926 1125818361297
927 1141228319560
928 1156858331646
929 1172716951103
930 1188788582220
931 1205051283087
932 1221501719211
933 1238161366709
934 1255057902769
935 1272200375557
936 1289572315975
937 1307150420390
938 1324930934998
939 1342936786986
940 1361197671394
941 1379723068032
942 1398495392607
943 1417490092525
944 1436703101383
945 1456158699765
946 1475888764993
947 1495903486004
948 1516183934622
949 1536703993094
950 1557459476699
951 1578476148379
952 1599787909637
953 1621405824525
954 1643309773051
955 1665471817396
956 1687887677315
957 1710584875844
958 1733599281643
959 1756942796500
960 1780594225510
961 1804523575124
962 1828726241588
963 1853231840544
964 1878078521962
965 1903278837236
966 1928810454136
967 1954641531896
968 1980766953640
969 2007218276106
970 2034036325376
971 2061234357322
972 2088788516103
973 2116665185001
974 2144858936892
975 2173403175320
976 2202341606107
977 2231688453890
978 2261418067666
979 2291494818317
980 2321913119721
981 2352708241781
982 2383926705567
983 2415584018270
984 2447652863191
985 2480095151903
986 2512905159630
987 2546120572871
988 2579790652383
989 2613931921957
990 2648515601309
991 2683501004908
992 2718881926599
993 2754698808770
994 2791004040226
995 2827815023108
996 2865101499418
997 2902820283286
998 2940964457767
999 2979577185567
1000 3018714402027