0 1
1 1
2 2
3 2
4 3
5 3
6 4
7 4
8 6
9 5
10 7
11 8
12 8
13 9
14 13
15 10
16 13
17 15
18 16
19 18
20 21
21 17
22 24
23 28
24 26
25 26
26 36
27 32
28 38
29 42
30 40
31 46
32 52
33 48
34 63
35 63
36 59
37 63
38 85
39 77
40 81
41 92
42 89
43 102
44 116
45 98
46 122
47 134
48 130
49 140
50 157
51 145
52 165
53 182
54 190
55 191
56 207
57 195
58 235
59 259
60 232
61 252
62 293
63 279
64 311
65 316
66 323
67 342
68 381
69 370
70 404
71 431
72 412
73 447
74 504
75 477
76 524
77 540
78 560
79 596
80 621
81 599
82 682
83 731
84 702
85 719
86 809
87 796
88 849
89 909
90 900
91 935
92 1004
93 982
94 1101
95 1121
96 1114
97 1187
98 1283
99 1261
100 1313
101 1380
102 1409
103 1504
104 1583
105 1516
106 1668
107 1716
108 1746
109 1821
110 1937
111 1936
112 2014
113 2121
114 2154
115 2226
116 2335
117 2324
118 2541
119 2629
120 2576
121 2682
122 2870
123 2857
124 3063
125 3125
126 3175
127 3292
128 3450
129 3481
130 3641
131 3793
132 3811
133 3958
134 4234
135 4146
136 4361
137 4507
138 4628
139 4828
140 4929
141 4954
142 5295
143 5455
144 5486
145 5655
146 5941
147 5962
148 6264
149 6431
150 6537
151 6767
152 7033
153 7096
154 7467
155 7610
156 7677
157 7957
158 8383
159 8458
160 8736
161 8943
162 9148
163 9471
164 9804
165 9786
166 10342
167 10615
168 10726
169 11115
170 11485
171 11589
172 12041
173 12371
174 12697
175 12971
176 13373
177 13501
178 14191
179 14545
180 14650
181 15134
182 15694
183 15823
184 16409
185 16787
186 17184
187 17652
188 18198
189 18385
190 19110
191 19526
192 19839
193 20464
194 21156
195 21294
196 22078
197 22597
198 23083
199 23729
200 24263
201 24616
202 25658
203 26114
204 26525
205 27166
206 28134
207 28499
208 29480
209 30101
210 30526
211 31373
212 32232
213 32719
214 33930
215 34504
216 35106
217 35986
218 37148
219 37629
220 38659
221 39389
222 40414
223 41471
224 42347
225 42832
226 44329
227 45251
228 45988
229 47310
230 48523
231 49029
232 50572
233 51550
234 52648
235 53753
236 55129
237 55897
238 57803
239 58838
240 59696
241 61271
242 62747
243 63734
244 65592
245 66605
246 68089
247 69534
248 71142
249 72338
250 74395
251 75778
252 77058
253 78838
254 80935
255 81865
256 84005
257 85644
258 87496
259 89417
260 91123
261 92496
262 95467
263 96864
264 98657
265 100843
266 103065
267 104636
268 107370
269 109332
270 111282
271 113873
272 116203
273 117914
274 121264
275 122841
276 125244
277 128139
278 131026
279 132967
280 135941
281 138216
282 141174
283 144028
284 146927
285 149136
286 153081
287 155541
288 158281
289 161534
290 164925
291 167368
292 171533
293 174439
294 177635
295 181068
296 184466
297 187632
298 192451
299 195171
300 198501
301 202595
302 207099
303 209939
304 214642
305 217992
306 222368
307 226844
308 230882
309 234434
310 239930
311 243647
312 248078
313 253158
314 257947
315 261374
316 267463
317 271590
318 276958
319 282127
320 286879
321 291725
322 298392
323 302627
324 307983
325 313683
326 319738
327 324679
328 331794
329 336757
330 342628
331 349023
332 355328
333 360778
334 369014
335 373890
336 380420
337 387892
338 394688
339 400761
340 408915
341 415033
342 423086
343 430146
344 437336
345 444153
346 453799
347 460163
348 468211
349 476843
350 485125
351 492251
352 502246
353 509616
354 518744
355 527629
356 536187
357 544777
358 556393
359 563696
360 573051
361 583492
362 593725
363 602364
364 613965
365 622565
366 634051
367 644872
368 655136
369 665129
370 678023
371 687424
372 699389
373 711545
374 723229
375 733488
376 747930
377 758580
378 771525
379 784042
380 796265
381 808949
382 824871
383 835412
384 849446
385 863546
386 877419
387 890883
388 907414
389 919755
390 935144
391 950356
392 965351
393 979796
394 998360
395 1010926
396 1027860
397 1045450
398 1061973
399 1076621
400 1095849
401 1111104
402 1130351
403 1148146
404 1165000
405 1182552
406 1204065
407 1220077
408 1239784
409 1259876
410 1279183
411 1297443
412 1320650
413 1337849
414 1360494
415 1380942
416 1401462
417 1423444
418 1448280
419 1466114
420 1489542
421 1513427
422 1536786
423 1558392
424 1585091
425 1605523
426 1632186
427 1657241
428 1680536
429 1705596
430 1735309
431 1757288
432 1785218
433 1812812
434 1838931
435 1864563
436 1896722
437 1921959
438 1952171
439 1980956
440 2009422
441 2038779
442 2073504
443 2098201
444 2131267
445 2163689
446 2195601
447 2227000
448 2262625
449 2291305
450 2327044
451 2361476
452 2395570
453 2430014
454 2469156
455 2498375
456 2538006
457 2576817
458 2612682
459 2648735
460 2690917
461 2724883
462 2768368
463 2807491
464 2845316
465 2886468
466 2932505
467 2969119
468 3014214
469 3057637
470 3100324
471 3141998
472 3192590
473 3232056
474 3281492
475 3327487
476 3372310
477 3420743
478 3474739
479 3515710
480 3567427
481 3619994
482 3670416
483 3718820
484 3775519
485 3822739
486 3880388
487 3934256
488 3986585
489 4042188
490 4103765
491 4152368
492 4215690
493 4274844
494 4330309
495 4388720
496 4455926
497 4510496
498 4577272
499 4637875
500 4699265
501 4765946
502 4837745
503 4892652
504 4964219
505 5033114
506 5100233
507 5169095
508 5244088
509 5307078
510 5384266
511 5457233
512 5529196
513 5602993
514 5684501
515 5750858
516 5834748
517 5915696
518 5991546
519 6068639
520 6156729
521 6231391
522 6322080
523 6404301
524 6485671
525 6571860
526 6668453
527 6746116
528 6840830
529 6932238
530 7019951
531 7112569
532 7215438
533 7298782
534 7401579
535 7497925
536 7592212
537 7696148
538 7803797
539 7890235
540 8001866
541 8107301
542 8212291
543 8316889
544 8430657
545 8529874
546 8649255
547 8761083
548 8870374
549 8986967
550 9110780
551 9212340
552 9342326
553 9462972
554 9579166
555 9701240
556 9834786
557 9951270
558 10086760
559 10211968
560 10338295
561 10472250
562 10617355
563 10734791
564 10880456
565 11020685
566 11155888
567 11296233
568 11448382
569 11578475
570 11735408
571 11883627
572 12028291
573 12180955
574 12342937
575 12480188
576 12649516
577 12810654
578 12964439
579 13124209
580 13298926
581 13450341
582 13632434
583 13796262
584 13961081
585 14140194
586 14326440
587 14484991
588 14675852
589 14856471
590 15035248
591 15222511
592 15423149
593 15593457
594 15797488
595 15986730
596 16179500
597 16385954
598 16594984
599 16774155
600 16993946
601 17205375
602 17408991
603 17617524
604 17843279
605 18043333
606 18280347
607 18499180
608 18714158
609 18943335
610 19185528
611 19393968
612 19647378
613 19885463
614 20113597
615 20355304
616 20615038
617 20844167
618 21110524
619 21355707
620 21605874
621 21871468
622 22148287
623 22381394
624 22665018
625 22938904
626 23203412
627 23483160
628 23773929
629 24031049
630 24334271
631 24618456
632 24906286
633 25204839
634 25513245
635 25784360
636 26111972
637 26421840
638 26719698
639 27034685
640 27366993
641 27663063
642 28013169
643 28331795
644 28650819
645 28994839
646 29348156
647 29661509
648 30029360
649 30374873
650 30718489
651 31077308
652 31456940
653 31792145
654 32183512
655 32548435
656 32913663
657 33307157
658 33704401
659 34054366
660 34475123
661 34871972
662 35264701
663 35666969
664 36091349
665 36477729
666 36919853
667 37338184
668 37751626
669 38190986
670 38645475
671 39045709
672 39522149
673 39969652
674 40405903
675 40868688
676 41355222
677 41793209
678 42291720
679 42754929
680 43230294
681 43734814
682 44246424
683 44696316
684 45229586
685 45738421
686 46240568
687 46766944
688 47307798
689 47799093
690 48369046
691 48901626
692 49436563
693 49998310
694 50570058
695 51087721
696 51698173
697 52275898
698 52833951
699 53421134
700 54037084
701 54600969
702 55247153
703 55837645
704 56438534
705 57078776
706 57730020
707 58320660
708 58996987
709 59641004
710 60281867
711 60952738
712 61647121
713 62273053
714 62991091
715 63671261
716 64356840
717 65080265
718 65805694
719 66461339
720 67235071
721 67964420
722 68689557
723 69437826
724 70213014
725 70933492
726 71743144
727 72510678
728 73274688
729 74080891
730 74904718
731 75653724
732 76527675
733 77342354
734 78147072
735 78997494
736 79874822
737 80689040
738 81597557
739 82448203
740 83318254
741 84234258
742 85157590
743 85995485
744 86967840
745 87894281
746 88807931
747 89765619
748 90744075
749 91648040
750 92677636
751 93642258
752 94622129
753 95645961
754 96673702
755 97627057
756 98720485
757 99762133
758 100785933
759 101851099
760 102958711
761 103982931
762 105140566
763 106214701
764 107301244
765 108461002
766 109625623
767 110704279
768 111916934
769 113071471
770 114228936
771 115437164
772 116680651
773 117826242
774 119108280
775 120322476
776 121557476
777 122852908
778 124147745
779 125343766
780 126718325
781 128029038
782 129328466
783 130669533
784 132043119
785 133338295
786 134788198
787 136155546
788 137528740
789 138968160
790 140423382
791 141779490
792 143323027
793 144769331
794 146211990
795 147733233
796 149281810
797 150740671
798 152343274
799 153857099
800 155410239
801 157033285
802 158662607
803 160167962
804 161882851
805 163518201
806 165140970
807 166840030
808 168560809
809 170178710
810 171987190
811 173692765
812 175428588
813 177228499
814 179037010
815 180743928
816 182661043
817 184490501
818 186296367
819 188173721
820 190116567
821 191943928
822 193955907
823 195850023
824 197769725
825 199801455
826 201830831
827 203740201
828 205868866
829 207889250
830 209933231
831 212042256
832 214196372
833 216224208
834 218460834
835 220592400
836 222756078
837 225018626
838 227262146
839 229379081
840 231766987
841 234037267
842 236314401
843 238664076
844 241047440
845 243323523
846 245826423
847 248206381
848 250603706
849 253108232
850 255628575
851 258007245
852 260665442
853 263180374
854 265699200
855 268331785
856 271010074
857 273549877
858 276320497
859 278950326
860 281639100
861 284440045
862 287241401
863 289887397
864 292830919
865 295649065
866 298471079
867 301399032
868 304353585
869 307173035
870 310272778
871 313217742
872 316218589
873 319312057
874 322405578
875 325374056
876 328658673
877 331801875
878 334927170
879 338159508
880 341462268
881 344622201
882 348063875
883 351313901
884 354636648
885 358108786
886 361568150
887 364864601
888 368488614
889 371955224
890 375452208
891 379068528
892 382744193
893 386235498
894 390032154
895 393676704
896 397380528
897 401234323
898 405050191
899 408694681
900 412755359
901 416620231
902 420502595
903 424493459
904 428545676
905 432456881
906 436689598
907 440744762
908 444826508
909 449074700
910 453336491
911 457414125
912 461908547
913 466167304
914 470464054
915 474926406
916 479433591
917 483775347
918 488442506
919 492899928
920 497478101
921 502205111
922 506924176
923 511445561
924 516379443
925 521138432
926 525925310
927 530866106
928 535843387
929 540625072
930 545832074
931 550794038
932 555865280
933 561080351
934 566277228
935 571325086
936 576806204
937 582078864
938 587362818
939 592806948
940 598346660
941 603678273
942 609432198
943 614910090
944 620484213
945 626289172
946 632083472
947 637654698
948 643712826
949 649523772
950 655386641
951 661448722
952 667561912
953 673448050
954 679783239
955 685872955
956 692096027
957 698504326
958 704861987
959 711011974
960 717743114
961 724198516
962 730694932
963 737359453
964 744078404
965 750644973
966 757665238
967 764391490
968 771246166
969 778305868
970 785369596
971 792204193
972 799630619
973 806720071
974 813876456
975 821284914
976 828754780
977 836000269
978 843708170
979 851129194
980 858728896
981 866538333
982 874361405
983 881888766
984 890035794
985 897925280
986 905851718
987 914022163
988 922226751
989 930212716
990 938768562
991 946986965
992 955374018
993 963955176
994 972534153
995 980911487
996 989947878
997 998630900
998 1007359739
999 1016341657
1000 1025424141