0 1
1 1
2 2
3 3
4 5
5 7
6 11
7 14
8 20
9 26
10 35
11 44
12 58
13 71
14 90
15 110
16 136
17 163
18 199
19 235
20 282
21 331
22 391
23 454
24 532
25 612
26 709
27 811
28 931
29 1057
30 1206
31 1360
32 1540
33 1729
34 1945
35 2172
36 2432
37 2702
38 3009
39 3331
40 3692
41 4070
42 4494
43 4935
44 5427
45 5942
46 6510
47 7104
48 7760
49 8442
50 9192
51 9975
52 10829
53 11720
54 12692
55 13702
56 14800
57 15944
58 17180
59 18467
60 19858
61 21301
62 22856
63 24473
64 26207
65 28009
66 29941
67 31943
68 34085
69 36308
70 38677
71 41134
72 43752
73 46461
74 49342
75 52327
76 55491
77 58767
78 62239
79 65827
80 69624
81 73551
82 77695
83 81979
84 86499
85 91164
86 96079
87 101155
88 106491
89 111999
90 117788
91 123755
92 130019
93 136479
94 143247
95 150224
96 157532
97 165056
98 172929
99 181038
100 189509
101 198230
102 207338
103 216705
104 226479
105 236534
106 247010
107 257783
108 269005
109 280534
110 292534
111 304865
112 317683
113 330850
114 344534
115 358579
116 373165
117 388138
118 403670
119 419609
120 436140
121 453091
122 470660
123 488678
124 507334
125 526461
126 546261
127 566547
128 587535
129 609040
130 631269
131 654039
132 677571
133 701661
134 726544
135 752019
136 778311
137 805221
138 832989
139 861394
140 890691
141 920661
142 951549
143 983139
144 1015691
145 1048966
146 1083239
147 1118274
148 1154336
149 1191191
150 1229120
151 1267865
152 1307723
153 1348439
154 1390299
155 1433051
156 1476997
157 1521860
158 1567959
159 1615020
160 1663351
161 1712680
162 1763332
163 1815010
164 1868056
165 1922176
166 1977700
167 2034337
168 2092435
169 2151676
170 2212426
171 2274370
172 2337862
173 2402590
174 2468926
175 2536531
176 2605795
177 2676382
178 2748670
179 2822326
180 2897747
181 2974571
182 3053214
183 3133318
184 3215286
185 3298763
186 3384171
187 3471126
188 3560070
189 3650622
190 3743211
191 3837459
192 3933815
193 4031871
194 4132096
195 4234086
196 4338296
197 4444325
198 4552649
199 4662836
200 4775383
201 4889861
202 5006753
203 5125634
204 5247008
205 5370418
206 5496389
207 5624468
208 5755166
209 5888033
210 6023602
211 6161390
212 6301952
213 6444809
214 6590501
215 6738553
216 6889527
217 7042914
218 7199299
219 7358177
220 7520118
221 7684620
222 7852276
223 8022550
224 8196058
225 8372268
226 8551780
227 8734066
228 8919750
229 9108268
230 9300268
231 9495190
232 9693666
233 9895140
234 10100268
235 10308458
236 10520390
237 10735476
238 10954380
239 11176518
240 11402579
241 11631941
242 11865318
243 12102093
244 12342963
245 12587315
246 12835871
247 13087980
248 13344390
249 13604454
250 13868903
251 14137094
252 14409784
253 14686291
254 14967398
255 15252428
256 15542146
257 15835879
258 16134419
259 16437053
260 16744600
261 17056351
262 17373107
263 17694164
264 18020350
265 18350920
266 18686729
267 19027037
268 19372681
269 19722925
270 20078634
271 20439030
272 20805006
273 21175789
274 21552253
275 21933630
276 22320822
277 22713018
278 23111149
279 23514409
280 23923710
281 24338250
282 24758970
283 25185025
284 25617385
285 26055210
286 26499450
287 26949270
288 27405650
289 27867710
290 28336460
291 28811025
292 29292395
293 29779700
294 30273960
295 30774260
296 31281650
297 31795220
298 32316000
299 32843085
300 33377536
301 33918401
302 34466772
303 35021703
304 35584265
305 36153517
306 36730561
307 37314409
308 37906195
309 38504936
310 39111745
311 39725644
312 40347778
313 40977121
314 41614850
315 42259945
316 42913561
317 43574683
318 44244499
319 44921945
320 45608242
321 46302331
322 47005411
323 47716429
324 48436617
325 49164872
326 49902459
327 50648281
328 51403581
329 52167267
330 52940616
331 53722485
332 54514185
333 55314579
334 56124955
335 56944182
336 57773582
337 58611972
338 59460709
339 60318616
340 61187027
341 62064770
342 62953214
343 63851135
344 64759937
345 65678402
346 66607910
347 67547249
348 68497835
349 69458402
350 70430402
351 71412575
352 72406349
353 73410470
354 74426402
355 75452837
356 76491275
357 77540414
358 78601730
359 79673927
360 80758518
361 81854151
362 82962376
363 84081848
364 85214092
365 86357769
366 87514441
367 88682713
368 89864185
369 91057468
370 92264137
371 93482809
372 94715097
373 95959561
374 97217852
375 98488537
376 99773241
377 101070537
378 102382089
379 103706412
380 105045209
381 106397001
382 107763465
383 109143129
384 110537709
385 111945674
386 113368779
387 114805500
388 116257566
389 117723459
390 119204948
391 120700455
392 122211789
393 123737379
394 125279007
395 126835109
396 128407507
397 129994576
398 131598179
399 133216698
400 134851969
401 136502380
402 138169808
403 139852580
404 141552614
405 143268244
406 145001360
407 146750303
408 148517005
409 150299744
410 152100494
411 153917540
412 155752828
413 157604650
414 159474994
415 161362089
416 163267965
417 165190858
418 167132770
419 169091944
420 171070425
421 173066391
422 175081930
423 177115228
424 179168344
425 181239471
426 183330711
427 185440192
428 187570060
429 189718450
430 191887479
431 194075289
432 196284041
433 198511811
434 200760804
435 203029104
436 205318886
437 207628241
438 209959389
439 212310354
440 214683401
441 217076561
442 219492069
443 221927964
444 224386526
445 226865726
446 229367889
447 231890994
448 234437336
449 237004901
450 239596030
451 242208640
452 244845118
453 247503389
454 250185809
455 252890311
456 255619297
457 258370630
458 261146759
459 263945555
460 266769436
461 269616280
462 272488552
463 275384060
464 278305316
465 281250136
466 284221000
467 287215732
468 290236860
469 293282136
470 296354136
471 299450620
472 302574132
473 305722440
474 308898136
475 312098916
476 315327420
477 318581352
478 321863320
479 325171036
480 328507157
481 331869321
482 335260234
483 338677543
484 342123921
485 345597023
486 349099571
487 352629146
488 356188520
489 359775282
490 363392171
491 367036784
492 370711910
493 374415071
494 378149106
495 381911546
496 385705196
497 389527595
498 393381599
499 397264671
500 401179718
501 405124211
502 409101023
503 413107634
504 417146968
505 421216428
506 425318989
507 429452063
508 433618591
509 437815993
510 442047262
511 446309740
512 450606472
513 454934809
514 459297761
515 463692688
516 468122652
517 472584934
518 477082649
519 481613087
520 486179328
521 490778670
522 495414246
523 500083275
524 504788943
525 509528478
526 514305030
527 519115836
528 523964100
529 528846978
530 533767728
531 538723515
532 543717561
533 548747040
534 553815228
535 558919218
536 564062340
537 569241696
538 574460580
539 579716103
540 585011614
541 590344141
542 595717088
543 601127493
544 606578723
545 612067825
546 617598221
547 623166875
548 628777265
549 634426364
550 640117613
551 645847994
552 651621004
553 657433541
554 663289158
555 669184763
556 675123871
557 681103399
558 687126919
559 693191263
560 699300060
561 705450151
562 711645127
563 717881839
564 724163935
565 730488180
566 736858279
567 743271007
568 749730031
569 756232135
570 762781044
571 769373455
572 776013151
573 782696839
574 789428263
575 796204140
576 803028272
577 809897288
578 816815049
579 823778194
580 830790545
581 837848750
582 844956690
583 852110925
584 859315395
585 866566670
586 873868650
587 881217915
588 888618425
589 896066670
590 903566670
591 911114925
592 918715415
593 926364650
594 934066670
595 941817895
596 949622425
597 957476690
598 965384750
599 973343045
600 981355696
601 989419051
602 997537292
603 1005706778
604 1013931650
605 1022208277
606 1030540861
607 1038925679
608 1047366995
609 1055861096
610 1064412205
611 1073016619
612 1081678623
613 1090394421
614 1099168360
615 1107996655
616 1116883611
617 1125825453
618 1134826549
619 1143883030
620 1152999327
621 1162171581
622 1171404181
623 1180693279
624 1190043327
625 1199450382
626 1208918959
627 1218445126
628 1228033356
629 1237679727
630 1247388776
631 1257156485
632 1266987455
633 1276877679
634 1286831715
635 1296845567
636 1306923857
637 1317062492
638 1327266159
639 1337530776
640 1347860987
641 1358252720
642 1368710684
643 1379230710
644 1389817572
645 1400467112
646 1411184060
647 1421964269
648 1432812535
649 1443724612
650 1454705362
651 1465750550
652 1476864994
653 1488044470
654 1499293862
655 1510608847
656 1521994375
657 1533446134
658 1544969030
659 1556558762
660 1568220303
661 1579949251
662 1591750646
663 1603620098
664 1615562602
665 1627573779
666 1639658691
667 1651812858
668 1664041410
669 1676339878
670 1688713347
671 1701157359
672 1713677067
673 1726267911
674 1738935112
675 1751674122
676 1764490116
677 1777378557
678 1790344689
679 1803383872
680 1816501419
681 1829692701
682 1842962985
683 1856307654
684 1869732044
685 1883231434
686 1896811229
687 1910466720
688 1924203266
689 1938016169
690 1951910858
691 1965882530
692 1979936684
693 1994068529
694 2008283517
695 2022576869
696 2036954107
697 2051410346
698 2065951179
699 2080571733
700 2095277554
701 2110063780
702 2124936028
703 2139889330
704 2154929374
705 2170051204
706 2185260460
707 2200552198
708 2215932130
709 2231395204
710 2246947204
711 2262583090
712 2278308598
713 2294118700
714 2310019204
715 2326004974
716 2342081890
717 2358244828
718 2374499620
719 2390841154
720 2407275335
721 2423796941
722 2440411950
723 2457115153
724 2473912479
725 2490798731
726 2507779911
727 2524850712
728 2542017210
729 2559274110
730 2576627439
731 2594071914
732 2611613636
733 2629247211
734 2646978814
735 2664803064
736 2682726086
737 2700742511
738 2718858539
739 2737068689
740 2755379236
741 2773784711
742 2792291339
743 2810893664
744 2829597986
745 2848398736
746 2867302289
747 2886303089
748 2905407461
749 2924609861
750 2943916690
751 2963322290
752 2982833138
753 3002443589
754 3022160069
755 3041976946
756 3061900722
757 3081925650
758 3102058309
759 3122292965
760 3142636146
761 3163082130
762 3183637522
763 3204296485
764 3225065701
765 3245939346
766 3266924050
767 3288014002
768 3309215910
769 3330523846
770 3351944596
771 3373472245
772 3395113527
773 3416862540
774 3438726096
775 3460698176
776 3482785670
777 3504982572
778 3527295720
779 3549719121
780 3572259692
781 3594911321
782 3617681004
783 3640562643
784 3663563181
785 3686676533
786 3709909721
787 3733256541
788 3756724095
789 3780306192
790 3804009881
791 3827828984
792 3851770630
793 3875828521
794 3900009866
795 3924308381
796 3948731221
797 3973272115
798 3997938299
799 4022723381
800 4047634678
801 4072665811
802 4097824043
803 4123103009
804 4148510053
805 4174038688
806 4199696339
807 4225476533
808 4251386641
809 4277420203
810 4303584672
811 4329873465
812 4356294117
813 4382840059
814 4409518771
815 4436323698
816 4463262402
817 4490328204
818 4517528749
819 4544857372
820 4572321663
821 4599914970
822 4627644966
823 4655504875
824 4683502453
825 4711630938
826 4739898030
827 4768296981
828 4796835575
829 4825506938
830 4854318938
831 4883264715
832 4912352081
833 4941574190
834 4970938938
835 5000439353
836 5030083415
837 5059864166
838 5089789530
839 5119852563
840 5150061274
841 5180408591
842 5210902608
843 5241536268
844 5272317608
845 5303239585
846 5334310321
847 5365522645
848 5396884765
849 5428389524
850 5460045073
851 5491844269
852 5523795349
853 5555891041
854 5588139668
855 5620533973
856 5653082221
857 5685777169
858 5718627169
859 5751624848
860 5784778645
861 5818081201
862 5851540897
863 5885150389
864 5918918145
865 5952836690
866 5986914579
867 6021144352
868 6055534506
869 6090077595
870 6124782204
871 6159640755
872 6194661921
873 6229838139
874 6265178023
875 6300674025
876 6336334847
877 6372152808
878 6408136699
879 6444278854
880 6480588005
881 6517056500
882 6553693160
883 6590490200
884 6627456530
885 6664584380
886 6701882600
887 6739343435
888 6776975825
889 6814771880
890 6852740630
891 6890874200
892 6929181560
893 6967654850
894 7006303130
895 7045118405
896 7084109825
897 7123269410
898 7162606250
899 7202112380
900 7241796981
901 7281651951
902 7321686562
903 7361892728
904 7402279660
905 7442839287
906 7483580911
907 7524496324
908 7565594920
909 7606868506
910 7648326415
911 7689960469
912 7731780093
913 7773776971
914 7815960620
915 7858322740
916 7900872786
917 7943602473
918 7986521349
919 8029620990
920 8072911037
921 8116383081
922 8160046701
923 8203893504
924 8247933162
925 8292157142
926 8336575209
927 8381178846
928 8425977756
929 8470963437
930 8516145686
931 8561515860
932 8607083850
933 8652841029
934 8698797225
935 8744943827
936 8791290757
937 8837829262
938 8884569359
939 8931502311
940 8978638072
941 9025967920
942 9073501904
943 9121231160
944 9169165832
945 9217297072
946 9265634960
947 9314170664
948 9362914360
949 9411857072
950 9461009072
951 9510361400
952 9559924264
953 9609688720
954 9659665072
955 9709844232
956 9760236600
957 9810833104
958 9861644080
959 9912660472
960 9963892713
961 10015331601
962 10066987666
963 10118851723
964 10170934237
965 10223226039
966 10275737691
967 10328459878
968 10381403260
969 10434558538
970 10487936307
971 10541527284
972 10595342162
973 10649371511
974 10703626122
975 10758096582
976 10812793616
977 10867707827
978 10922850039
979 10978210707
980 11033800754
981 11089610651
982 11145651255
983 11201913054
984 11258407004
985 11315123444
986 11372073429
987 11429247315
988 11486656091
989 11544290129
990 11602160518
991 11660257480
992 11718592204
993 11777154929
994 11835956777
995 11894988004
996 11954259832
997 12013762366
998 12073506929
999 12133483643
1000 12193703764