0 1
1 0
2 1
3 1
4 1
5 2
6 0
7 3
8 2
9 3
10 2
11 4
12 3
13 4
14 4
15 4
16 8
17 4
18 8
19 6
20 9
21 8
22 10
23 10
24 13
25 12
26 13
27 16
28 16
29 19
30 17
31 21
32 23
33 23
34 25
35 29
36 31
37 31
38 31
39 37
40 40
41 42
42 44
43 48
44 49
45 54
46 55
47 64
48 67
49 68
50 70
51 77
52 84
53 90
54 92
55 99
56 102
57 108
58 115
59 127
60 133
61 135
62 138
63 150
64 165
65 171
66 183
67 186
68 198
69 201
70 220
71 237
72 249
73 252
74 261
75 276
76 301
77 316
78 329
79 342
80 353
81 366
82 394
83 422
84 444
85 449
86 461
87 488
88 523
89 552
90 578
91 590
92 608
93 634
94 675
95 723
96 757
97 766
98 784
99 825
100 878
101 928
102 962
103 992
104 1015
105 1056
106 1118
107 1199
108 1241
109 1265
110 1289
111 1348
112 1433
113 1517
114 1569
115 1609
116 1646
117 1707
118 1809
119 1916
120 1988
121 2031
122 2059
123 2157
124 2279
125 2403
126 2490
127 2554
128 2595
129 2697
130 2840
131 3003
132 3121
133 3170
134 3227
135 3363
136 3549
137 3736
138 3864
139 3938
140 4025
141 4157
142 4370
143 4617
144 4783
145 4863
146 4962
147 5137
148 5402
149 5684
150 5871
151 5986
152 6101
153 6298
154 6621
155 6965
156 7206
157 7333
158 7452
159 7708
160 8117
161 8474
162 8768
163 8943
164 9107
165 9384
166 9854
167 10323
168 10689
169 10859
170 11038
171 11396
172 11945
173 12501
174 12918
175 13140
176 13387
177 13801
178 14422
179 15106
180 15608
181 15839
182 16117
183 16632
184 17378
185 18163
186 18745
187 19081
188 19418
189 19964
190 20845
191 21806
192 22477
193 22869
194 23236
195 23917
196 25003
197 26092
198 26834
199 27359
200 27789
201 28572
202 29785
203 31088
204 32038
205 32595
206 33097
207 34083
208 35487
209 36965
210 38092
211 38739
212 39330
213 40463
214 42081
215 43865
216 45212
217 45939
218 46626
219 47976
220 49889
221 51897
222 53391
223 54323
224 55206
225 56670
226 58888
227 61315
228 63060
229 64099
230 65115
231 66813
232 69415
233 72205
234 74203
235 75474
236 76698
237 78645
238 81652
239 84853
240 87225
241 88639
242 89971
243 92358
244 95854
245 99438
246 102239
247 104011
248 105539
249 108231
250 112201
251 116377
252 119654
253 121598
254 123385
255 126550
256 131189
257 136013
258 139700
259 141961
260 144177
261 147692
262 152886
263 158581
264 162841
265 165394
266 168002
267 172130
268 178082
269 184512
270 189396
271 192429
272 195391
273 200052
274 206937
275 214355
276 220029
277 223565
278 226829
279 232251
280 240277
281 248496
282 254872
283 259147
284 262982
285 269103
286 278242
287 287775
288 295164
289 299934
290 304305
291 311385
292 321674
293 332550
294 341046
295 346496
296 351663
297 359815
298 371336
299 383869
300 393640
301 399641
302 405524
303 414988
304 428190
305 442278
306 453380
307 460572
308 467361
309 477840
310 492822
311 508912
312 521427
313 529725
314 537463
315 549363
316 566692
317 584939
318 598951
319 608562
320 617492
321 630812
322 650270
323 671044
324 687152
325 697949
326 708136
327 723729
328 745618
329 768812
330 787272
331 799592
332 811064
333 828752
334 853409
335 879726
336 900992
337 914903
338 927778
339 947953
340 975945
341 1005459
342 1029109
343 1045218
344 1060289
345 1082775
346 1114358
347 1148117
348 1174706
349 1192771
350 1210063
351 1235286
352 1270733
353 1308830
354 1338794
355 1359524
356 1379409
357 1407850
358 1447695
359 1490611
360 1524626
361 1547825
362 1569794
363 1602416
364 1647597
365 1695182
366 1733708
367 1760625
368 1785395
369 1821920
370 1872650
371 1925970
372 1969404
373 1999826
374 2027824
375 2069099
376 2126231
377 2186332
378 2234940
379 2269114
380 2301280
381 2347223
382 2410660
383 2478776
384 2533648
385 2571613
386 2608428
387 2660745
388 2731585
389 2807481
390 2869016
391 2911988
392 2953366
393 3011835
394 3091240
395 3176298
396 3245741
397 3294631
398 3340681
399 3406202
400 3495859
401 3590240
402 3667266
403 3723160
404 3775235
405 3848217
406 3948742
407 4054763
408 4140896
409 4203347
410 4262039
411 4343979
412 4455666
413 4573869
414 4670784
415 4740929
416 4807409
417 4899631
418 5023255
419 5155437
420 5264564
421 5342097
422 5416030
423 5520119
424 5658360
425 5805194
426 5927182
427 6015214
428 6098458
429 6213939
430 6368045
431 6531647
432 6666926
433 6765999
434 6859739
435 6988089
436 7160558
437 7343228
438 7493165
439 7604606
440 7710243
441 7852256
442 8043450
443 8247560
444 8415239
445 8539122
446 8657483
447 8817526
448 9029909
449 9255283
450 9442538
451 9581143
452 9712669
453 9891589
454 10127449
455 10377333
456 10587431
457 10742784
458 10888717
459 11088145
460 11350568
461 11626881
462 11859374
463 12033512
464 12197654
465 12418389
466 12709821
467 13018534
468 13276182
469 13469167
470 13653648
471 13898694
472 14220569
473 14563280
474 14849214
475 15064512
476 15271935
477 15544178
478 15899785
479 16279546
480 16597997
481 16836935
482 17065950
483 17369604
484 17765169
485 18183723
486 18537407
487 18805989
488 19060017
489 19395932
490 19834685
491 20296450
492 20687451
493 20987027
494 21269912
495 21642697
496 22128974
497 22640331
498 23072844
499 23405663
500 23721846
501 24133276
502 24667781
503 25235243
504 25715726
505 26082560
506 26435194
507 26894015
508 27483215
509 28108871
510 28640953
511 29047498
512 29438711
513 29946923
514 30597527
515 31287823
516 31877321
517 32330522
518 32763277
519 33324312
520 34044422
521 34803788
522 35452077
523 35957913
524 36439177
525 37056583
526 37852833
527 38693177
528 39407757
529 39966801
530 40500821
531 41182951
532 42058811
533 42984202
534 43774009
535 44392821
536 44986487
537 45742650
538 46704374
539 47722800
540 48598072
541 49279839
542 49933448
543 50771479
544 51831186
545 52949714
546 53916564
547 54673747
548 55396150
549 56318541
550 57485715
551 58716258
552 59778354
553 60616093
554 61417698
555 62432966
556 63719240
557 65075014
558 66240844
559 67167104
560 68056833
561 69170713
562 70580490
563 72074582
564 73359927
565 74380053
566 75364187
567 76595610
568 78144432
569 79782156
570 81197973
571 82323285
572 83405354
573 84763204
574 86465718
575 88260318
576 89821399
577 91066291
578 92256423
579 93751186
580 95622920
581 97587400
582 99299901
583 100676309
584 101991433
585 103631223
586 105685488
587 107847543
588 109727326
589 111238285
590 112691422
591 114492784
592 116740546
593 119114198
594 121178650
595 122840156
596 124447611
597 126429904
598 128888859
599 131489757
600 133759133
601 135584092
602 137348232
603 139528206
604 142226342
605 145069952
606 147561696
607 149578948
608 151516680
609 153904409
610 156864985
611 159975527
612 162701836
613 164923236
614 167054904
615 169673062
616 172919645
617 176326072
618 179309700
619 181750757
620 184099965
621 186966636
622 190509560
623 194241563
624 197517154
625 200191073
626 202775446
627 205928082
628 209797311
629 213874253
630 217466373
631 220396722
632 223229958
633 226687552
634 230918970
635 235373498
636 239309920
637 242531459
638 245638589
639 249423014
640 254053496
641 258913674
642 263208629
643 266751871
644 270167721
645 274298626
646 279361765
647 284681737
648 289373472
649 293254617
650 297004982
651 301520908
652 307044614
653 312854725
654 317985735
655 322235601
656 326352428
657 331301191
658 337323192
659 343657895
660 349274607
661 353922351
662 358420651
663 363843169
664 370417500
665 377315800
666 383459997
667 388561737
668 393482740
669 399402354
670 406576463
671 414095972
672 420795360
673 426379844
674 431772647
675 438234165
676 446063375
677 454271317
678 461571478
679 467677870
680 473594575
681 480638647
682 489155242
683 498110470
684 506079212
685 512746279
686 519226398
687 526927334
688 536199841
689 545945493
690 554642861
691 561928608
692 568999575
693 577406848
694 587513497
695 598115096
696 607606128
697 615579587
698 623293731
699 632462751
700 643479242
701 654999729
702 665326356
703 674049456
704 682484714
705 692470061
706 704463135
707 717015377
708 728261659
709 737772207
710 746994014
711 757871620
712 770899026
713 784560863
714 796813431
715 807177795
716 817259237
717 829125491
718 843277129
719 858129868
720 871480273
721 882769826
722 893755795
723 906692968
724 922085734
725 938211107
726 952743476
727 965081199
728 977055662
729 991121448
730 1007863418
731 1025376179
732 1041163798
733 1054625328
734 1067685051
735 1082979673
736 1101188682
737 1120224332
738 1137373558
739 1152038204
740 1166287311
741 1182911918
742 1202662900
743 1223342105
744 1241997715
745 1257950012
746 1273484116
747 1291597293
748 1313022874
749 1335451047
750 1355745427
751 1373101710
752 1389996833
753 1409701032
754 1432956510
755 1457281240
756 1479345507
757 1498249793
758 1516626955
759 1538036606
760 1563287700
761 1589656159
762 1613581263
763 1634169543
764 1654192650
765 1677423112
766 1704821656
767 1733449919
768 1759400447
769 1781779291
770 1803583729
771 1828792862
772 1858475277
773 1889522869
774 1917691552
775 1942010124
776 1965740486
777 1993133529
778 2025291730
779 2058926512
780 2089509892
781 2115918177
782 2141674124
783 2171436509
784 2206301268
785 2242697370
786 2275884653
787 2304617937
788 2332588737
789 2364866155
790 2402650817
791 2442051210
792 2478008031
793 2509228214
794 2539625377
795 2574615597
796 2615551823
797 2658245642
798 2697190713
799 2731067744
800 2764116502
801 2802029287
802 2846300895
803 2892549109
804 2934759587
805 2971488748
806 3007399311
807 3048539374
808 3096429525
809 3146449944
810 3192190294
811 3232030168
812 3270967334
813 3315556259
814 3367389325
815 3421473829
816 3471028781
817 3514286305
818 3556492970
819 3604781742
820 3660898754
821 3719347638
822 3772936690
823 3819881481
824 3865674349
825 3917931969
826 3978639791
827 4041873415
828 4099844352
829 4150703609
830 4200385746
831 4256949621
832 4322523447
833 4390888751
834 4453634112
835 4508709844
836 4562593035
837 4623861513
838 4694682927
839 4768545036
840 4836456720
841 4896064482
842 4954395094
843 5020734541
844 5097277816
845 5177021487
846 5250469974
847 5315086681
848 5378254475
849 5449975519
850 5532691760
851 5618786230
852 5698114047
853 5768104903
854 5836532481
855 5914037098
856 6003405405
857 6096412459
858 6182086740
859 6257831006
860 6331955363
861 6415693555
862 6512118204
863 6612549666
864 6705136679
865 6787030707
866 6867273222
867 6957864419
868 7061899601
869 7170215475
870 7270267187
871 7358820370
872 7445566312
873 7543493720
874 7655763458
875 7772562231
876 7880657940
877 7976471296
878 8070239271
879 8176002560
880 8297164945
881 8423087005
882 8539689525
883 8643307714
884 8744743398
885 8858885385
886 8989589130
887 9125467150
888 9251244950
889 9363177308
890 9472904290
891 9596088858
892 9736929037
893 9883444914
894 10019160217
895 10140046852
896 10258685939
897 10391696429
898 10543453813
899 10701331583
900 10847786147
901 10978306075
902 11106367703
903 11249956842
904 11413563693
905 11583568706
906 11741538049
907 11882587667
908 12020835266
909 12175689915
910 12352029251
911 12535086568
912 12705299550
913 12857617482
914 13006920859
915 13173874496
916 13363866331
917 13561085418
918 13744487054
919 13908832688
920 14070088573
921 14250026805
922 14454487098
923 14666916078
924 14864589344
925 15041779985
926 15215867377
927 15409958263
928 15630012086
929 15858619457
930 16071631117
931 16262700867
932 16450436124
933 16659647498
934 16896536060
935 17142472788
936 17371940418
937 17578104415
938 17780514608
939 18005851988
940 18260884408
941 18525396638
942 18772324575
943 18994699918
944 19213008858
945 19455598382
946 19730065228
947 20014721011
948 20280448618
949 20520058472
950 20755483605
951 21016671680
952 21311761258
953 21617914888
954 21903948526
955 22162044345
956 22415859919
957 22697198529
958 23014405799
959 23343514857
960 23651429010
961 23929349614
962 24202666464
963 24505598956
964 24846681418
965 25200315274
966 25531616900
967 25831077760
968 26125421744
969 26451322466
970 26818049270
971 27198031946
972 27554158781
973 27876668898
974 28193751891
975 28544238428
976 28938430787
977 29346847783
978 29729613776
979 30076750651
980 30418301404
981 30795122060
982 31218463786
983 31657312703
984 32068844921
985 32442288712
986 32810007727
987 33215413241
988 33670079512
989 34141269574
990 34583679352
991 34985403599
992 35380921691
993 35816882171
994 36305231456
995 36810982882
996 37286476310
997 37718783868
998 38144174481
999 38612727800
1000 39137216460