0 1 1 0 2 0 3 1 4 1 5 0 6 1 7 2 8 1 9 1 10 2 11 2 12 3 13 2 14 3 15 4 16 4 17 3 18 5 19 6 20 5 21 6 22 7 23 7 24 9 25 8 26 9 27 11 28 12 29 10 30 13 31 15 32 14 33 15 34 17 35 18 36 20 37 19 38 21 39 24 40 25 41 23 42 28 43 30 44 29 45 31 46 34 47 35 48 38 49 38 50 40 51 44 52 46 53 44 54 50 55 53 56 53 57 55 58 59 59 61 60 65 61 65 62 68 63 74 64 76 65 74 66 82 67 86 68 86 69 89 70 95 71 97 72 102 73 103 74 107 75 114 76 117 77 116 78 125 79 130 80 131 81 135 82 142 83 145 84 152 85 153 86 158 87 167 88 171 89 170 90 181 91 188 92 189 93 194 94 203 95 207 96 215 97 217 98 224 99 234 100 239 101 239 102 252 103 260 104 262 105 269 106 279 107 284 108 294 109 297 110 305 111 317 112 324 113 324 114 339 115 349 116 352 117 360 118 372 119 379 120 390 121 394 122 404 123 418 124 426 125 427 126 445 127 456 128 460 129 470 130 484 131 492 132 505 133 511 134 522 135 538 136 548 137 550 138 570 139 583 140 589 141 600 142 616 143 626 144 641 145 648 146 661 147 680 148 691 149 694 150 717 151 732 152 739 153 752 154 771 155 782 156 799 157 808 158 823 159 844 160 857 161 862 162 887 163 904 164 913 165 928 166 949 167 962 168 982 169 992 170 1009 171 1033 172 1048 173 1054 174 1082 175 1102 176 1112 177 1129 178 1153 179 1168 180 1190 181 1202 182 1222 183 1248 184 1265 185 1273 186 1304 187 1326 188 1338 189 1358 190 1384 191 1401 192 1426 193 1440 194 1462 195 1491 196 1511 197 1520 198 1554 199 1579 200 1593 201 1615 202 1644 203 1664 204 1691 205 1707 206 1732 207 1764 208 1786 209 1797 210 1835 211 1862 212 1878 213 1903 214 1935 215 1957 216 1987 217 2006 218 2033 219 2068 220 2093 221 2106 222 2147 223 2177 224 2196 225 2223 226 2258 227 2283 228 2316 229 2337 230 2367 231 2406 232 2433 233 2448 234 2493 235 2526 236 2547 237 2577 238 2616 239 2643 240 2679 241 2703 242 2736 243 2778 244 2808 245 2826 246 2874 247 2910 248 2934 249 2967 250 3009 251 3039 252 3079 253 3105 254 3141 255 3187 256 3220 257 3240 258 3292 259 3332 260 3358 261 3394 262 3440 263 3473 264 3516 265 3545 266 3585 267 3634 268 3670 269 3693 270 3749 271 3792 272 3821 273 3861 274 3910 275 3946 276 3993 277 4025 278 4068 279 4121 280 4161 281 4186 282 4246 283 4293 284 4325 285 4368 286 4421 287 4461 288 4511 289 4546 290 4593 291 4650 292 4693 293 4721 294 4786 295 4836 296 4871 297 4918 298 4975 299 5018 300 5072 301 5111 302 5161 303 5222 304 5269 305 5300 306 5369 307 5423 308 5462 309 5512 310 5573 311 5620 312 5678 313 5720 314 5774 315 5840 316 5890 317 5924 318 5998 319 6056 320 6098 321 6152 322 6218 323 6268 324 6330 325 6376 326 6434 327 6504 328 6558 329 6596 330 6674 331 6736 332 6782 333 6840 334 6910 335 6964 336 7031 337 7080 338 7142 339 7217 340 7275 341 7316 342 7399 343 7466 344 7515 345 7577 346 7652 347 7710 348 7781 349 7834 350 7901 351 7980 352 8042 353 8087 354 8175 355 8246 356 8299 357 8366 358 8445 359 8507 360 8583 361 8640 362 8711 363 8795 364 8862 365 8910 366 9003 367 9079 368 9136 369 9207 370 9291 371 9358 372 9438 373 9499 374 9575 375 9664 376 9735 377 9787 378 9886 379 9966 380 10027 381 10103 382 10192 383 10263 384 10348 385 10414 386 10494 387 10588 388 10664 389 10720 390 10824 391 10909 392 10975 393 11055 394 11149 395 11225 396 11315 397 11385 398 11470 399 11570 400 11650 401 11710 402 11820 403 11910 404 11980 405 12065 406 12165 407 12245 408 12340 409 12415 410 12505 411 12610 412 12695 413 12760 414 12875 415 12970 416 13045 417 13135 418 13240 419 13325 420 13426 421 13505 422 13600 423 13711 424 13801 425 13870 426 13991 427 14092 428 14171 429 14266 430 14377 431 14467 432 14573 433 14657 434 14758 435 14874 436 14969 437 15043 438 15170 439 15276 440 15360 441 15461 442 15577 443 15672 444 15784 445 15873 446 15979 447 16101 448 16202 449 16280 450 16413 451 16525 452 16614 453 16720 454 16842 455 16943 456 17060 457 17154 458 17266 459 17394 460 17500 461 17583 462 17723 463 17840 464 17934 465 18046 466 18174 467 18280 468 18403 469 18503 470 18620 471 18754 472 18866 473 18954 474 19100 475 19223 476 19323 477 19440 478 19574 479 19686 480 19815 481 19920 482 20043 483 20184 484 20301 485 20394 486 20547 487 20676 488 20781 489 20904 490 21045 491 21162 492 21297 493 21408 494 21537 495 21684 496 21807 497 21906 498 22065 499 22200 500 22311 501 22440 502 22587 503 22710 504 22852 505 22968 506 23103 507 23257 508 23386 509 23490 510 23656 511 23798 512 23914 513 24049 514 24203 515 24332 516 24480 517 24602 518 24744 519 24904 520 25039 521 25149 522 25322 523 25470 524 25592 525 25734 526 25894 527 26029 528 26184 529 26312 530 26460 531 26627 532 26769 533 26884 534 27064 535 27219 536 27347 537 27495 538 27662 539 27804 540 27965 541 28099 542 28254 543 28428 544 28576 545 28697 546 28885 547 29046 548 29180 549 29335 550 29509 551 29657 552 29825 553 29966 554 30127 555 30308 556 30463 557 30590 558 30785 559 30953 560 31094 561 31255 562 31436 563 31591 564 31766 565 31913 566 32081 567 32270 568 32431 569 32564 570 32767 571 32942 572 33089 573 33257 574 33446 575 33607 576 33789 577 33943 578 34118 579 34314 580 34482 581 34622 582 34832 583 35014 584 35168 585 35343 586 35539 587 35707 588 35897 589 36057 590 36239 591 36443 592 36618 593 36764 594 36982 595 37172 596 37332 597 37514 598 37718 599 37893 600 38090 601 38257 602 38447 603 38658 604 38840 605 38993 606 39219 607 39416 608 39583 609 39773 610 39984 611 40166 612 40371 613 40545 614 40742 615 40961 616 41151 617 41310 618 41544 619 41749 620 41923 621 42120 622 42339 623 42529 624 42741 625 42922 626 43127 627 43354 628 43551 629 43717 630 43960 631 44172 632 44353 633 44558 634 44785 635 44982 636 45202 637 45391 638 45603 639 45838 640 46043 641 46216 642 46467 643 46687 644 46876 645 47088 646 47323 647 47528 648 47756 649 47952 650 48172 651 48416 652 48628 653 48808 654 49068 655 49296 656 49492 657 49712 658 49956 659 50168 660 50404 661 50608 662 50836 663 51088 664 51308 665 51496 666 51764 667 52000 668 52204 669 52432 670 52684 671 52904 672 53149 673 53360 674 53596 675 53857 676 54085 677 54280 678 54557 679 54802 680 55013 681 55249 682 55510 683 55738 684 55991 685 56210 686 56455 687 56724 688 56960 689 57163 690 57449 691 57702 692 57921 693 58166 694 58435 695 58671 696 58933 697 59160 698 59413 699 59691 700 59936 701 60146 702 60441 703 60703 704 60930 705 61183 706 61461 707 61706 708 61976 709 62211 710 62473 711 62760 712 63013 713 63231 714 63536 715 63806 716 64041 717 64303 718 64590 719 64843 720 65122 721 65366 722 65636 723 65932 724 66194 725 66420 726 66734 727 67013 728 67257 729 67527 730 67823 731 68085 732 68373 733 68625 734 68904 735 69210 736 69480 737 69714 738 70038 739 70326 740 70578 741 70857 742 71163 743 71433 744 71730 745 71991 746 72279 747 72594 748 72873 749 73116 750 73449 751 73746 752 74007 753 74295 754 74610 755 74889 756 75196 757 75465 758 75762 759 76087 760 76375 761 76626 762 76969 763 77276 764 77545 765 77842 766 78167 767 78455 768 78771 769 79049 770 79356 771 79690 772 79987 773 80247 774 80600 775 80916 776 81194 777 81501 778 81835 779 82132 780 82458 781 82745 782 83061 783 83405 784 83712 785 83980 786 84343 787 84669 788 84956 789 85272 790 85616 791 85923 792 86258 793 86554 794 86880 795 87234 796 87550 797 87827 798 88201 799 88536 800 88832 801 89158 802 89512 803 89828 804 90173 805 90479 806 90814 807 91178 808 91504 809 91790 810 92174 811 92519 812 92825 813 93160 814 93524 815 93850 816 94205 817 94520 818 94865 819 95240 820 95575 821 95870 822 96265 823 96620 824 96935 825 97280 826 97655 827 97990 828 98355 829 98680 830 99035 831 99420 832 99765 833 100070 834 100475 835 100840 836 101165 837 101520 838 101905 839 102250 840 102626 841 102960 842 103325 843 103721 844 104076 845 104390 846 104806 847 105182 848 105516 849 105881 850 106277 851 106632 852 107018 853 107362 854 107738 855 108144 856 108509 857 108833 858 109260 859 109646 860 109990 861 110366 862 110772 863 111137 864 111534 865 111888 866 112274 867 112691 868 113067 869 113400 870 113838 871 114235 872 114589 873 114975 874 115392 875 115768 876 116175 877 116539 878 116936 879 117364 880 117750 881 118093 882 118543 883 118950 884 119314 885 119711 886 120139 887 120525 888 120943 889 121318 890 121725 891 122164 892 122561 893 122914 894 123375 895 123793 896 124168 897 124575 898 125014 899 125411 900 125840 901 126225 902 126643 903 127094 904 127501 905 127864 906 128337 907 128766 908 129151 909 129569 910 130020 911 130427 912 130867 913 131263 914 131692 915 132154 916 132572 917 132946 918 133430 919 133870 920 134266 921 134695 922 135157 923 135575 924 136027 925 136433 926 136873 927 137347 928 137776 929 138160 930 138656 931 139108 932 139514 933 139954 934 140428 935 140857 936 141320 937 141737 938 142189 939 142674 940 143114 941 143509 942 144017 943 144480 944 144897 945 145349 946 145834 947 146274 948 146749 949 147177 950 147640 951 148137 952 148589 953 148994 954 149514 955 149989 956 150417 957 150880 958 151377 959 151829 960 152315 961 152754 962 153229 963 153738 964 154201 965 154617 966 155150 967 155636 968 156075 969 156550 970 157059 971 157522 972 158020 973 158471 974 158957 975 159478 976 159953 977 160380 978 160925 979 161423 980 161874 981 162360 982 162881 983 163356 984 163866 985 164328 986 164826 987 165360 988 165846 989 166284 990 166842 991 167352 992 167814 993 168312 994 168846 995 169332 996 169854 997 170328 998 170838 999 171384 1000 171882