0 1 1 0 2 1 3 0 4 1 5 1 6 1 7 1 8 1 9 1 10 2 11 2 12 3 13 2 14 3 15 3 16 4 17 4 18 4 19 4 20 5 21 5 22 7 23 6 24 8 25 7 26 9 27 9 28 10 29 10 30 11 31 11 32 13 33 13 34 15 35 15 36 17 37 17 38 19 39 19 40 21 41 21 42 23 43 23 44 26 45 26 46 29 47 29 48 32 49 32 50 35 51 35 52 38 53 38 54 41 55 42 56 45 57 46 58 49 59 50 60 54 61 54 62 58 63 58 64 62 65 63 66 67 67 68 68 72 69 73 70 78 71 79 72 84 73 84 74 89 75 90 76 95 77 97 78 101 79 103 80 108 81 110 82 116 83 117 84 123 85 124 86 130 87 132 88 138 89 140 90 146 91 148 92 155 93 157 94 164 95 166 96 173 97 175 98 182 99 185 100 192 101 195 102 202 103 205 104 213 105 216 106 224 107 227 108 235 109 238 110 247 111 250 112 259 113 262 114 271 115 275 116 284 117 288 118 297 119 301 120 311 121 315 122 325 123 329 124 339 125 344 126 354 127 359 128 369 129 374 130 385 131 390 132 402 133 406 134 418 135 423 136 435 137 441 138 452 139 458 140 470 141 476 142 489 143 495 144 508 145 514 146 527 147 534 148 547 149 554 150 567 151 574 152 588 153 595 154 610 155 617 156 632 157 639 158 654 159 662 160 677 161 685 162 700 163 708 164 724 165 733 166 749 167 758 168 774 169 783 170 800 171 809 172 826 173 835 174 852 175 862 176 880 177 890 178 908 179 918 180 937 181 947 182 966 183 976 184 995 185 1006 186 1025 187 1037 188 1056 189 1068 190 1088 191 1100 192 1121 193 1132 194 1153 195 1165 196 1186 197 1199 198 1220 199 1233 200 1255 201 1268 202 1291 203 1304 204 1327 205 1340 206 1363 207 1377 208 1400 209 1415 210 1438 211 1453 212 1477 213 1492 214 1517 215 1532 216 1557 217 1572 218 1597 219 1613 220 1639 221 1655 222 1681 223 1697 224 1724 225 1741 226 1768 227 1785 228 1812 229 1829 230 1857 231 1875 232 1903 233 1921 234 1949 235 1968 236 1997 237 2016 238 2045 239 2064 240 2094 241 2113 242 2144 243 2163 244 2194 245 2214 246 2245 247 2266 248 2297 249 2318 250 2350 251 2371 252 2404 253 2425 254 2458 255 2480 256 2513 257 2536 258 2569 259 2592 260 2626 261 2649 262 2684 263 2707 264 2743 265 2766 266 2802 267 2826 268 2862 269 2887 270 2923 271 2948 272 2985 273 3010 274 3048 275 3074 276 3112 277 3138 278 3176 279 3203 280 3242 281 3269 282 3308 283 3335 284 3375 285 3403 286 3444 287 3472 288 3513 289 3541 290 3583 291 3612 292 3654 293 3683 294 3725 295 3755 296 3798 297 3829 298 3872 299 3903 300 3947 301 3978 302 4023 303 4054 304 4099 305 4131 306 4176 307 4209 308 4255 309 4288 310 4335 311 4368 312 4416 313 4449 314 4497 315 4531 316 4579 317 4614 318 4662 319 4698 320 4747 321 4783 322 4833 323 4869 324 4920 325 4956 326 5007 327 5044 328 5095 329 5133 330 5185 331 5223 332 5276 333 5314 334 5368 335 5407 336 5461 337 5500 338 5554 339 5594 340 5649 341 5690 342 5745 343 5786 344 5842 345 5884 346 5941 347 5983 348 6040 349 6082 350 6140 351 6183 352 6242 353 6285 354 6344 355 6388 356 6448 357 6493 358 6553 359 6598 360 6659 361 6704 362 6766 363 6812 364 6874 365 6921 366 6983 367 7031 368 7094 369 7142 370 7206 371 7254 372 7319 373 7367 374 7433 375 7482 376 7548 377 7598 378 7664 379 7715 380 7782 381 7833 382 7901 383 7952 384 8021 385 8073 386 8142 387 8195 388 8264 389 8318 390 8388 391 8442 392 8513 393 8567 394 8639 395 8694 396 8767 397 8822 398 8895 399 8951 400 9025 401 9082 402 9156 403 9213 404 9288 405 9346 406 9422 407 9481 408 9557 409 9616 410 9693 411 9753 412 9831 413 9891 414 9969 415 10030 416 10109 417 10171 418 10251 419 10313 420 10394 421 10456 422 10538 423 10601 424 10683 425 10747 426 10829 427 10894 428 10977 429 11043 430 11127 431 11193 432 11278 433 11344 434 11430 435 11497 436 11583 437 11651 438 11737 439 11806 440 11894 441 11963 442 12052 443 12121 444 12211 445 12281 446 12371 447 12442 448 12532 449 12604 450 12695 451 12768 452 12860 453 12933 454 13026 455 13100 456 13194 457 13268 458 13362 459 13437 460 13532 461 13608 462 13704 463 13780 464 13877 465 13954 466 14052 467 14130 468 14228 469 14306 470 14405 471 14484 472 14584 473 14664 474 14764 475 14845 476 14946 477 15028 478 15130 479 15212 480 15315 481 15397 482 15501 483 15584 484 15689 485 15773 486 15878 487 15963 488 16069 489 16155 490 16262 491 16348 492 16456 493 16542 494 16651 495 16739 496 16848 497 16937 498 17046 499 17136 500 17247 501 17337 502 17449 503 17539 504 17652 505 17743 506 17857 507 17949 508 18063 509 18156 510 18271 511 18365 512 18481 513 18575 514 18692 515 18787 516 18905 517 19001 518 19119 519 19216 520 19335 521 19433 522 19553 523 19651 524 19772 525 19871 526 19993 527 20093 528 20216 529 20316 530 20440 531 20541 532 20666 533 20768 534 20893 535 20996 536 21122 537 21226 538 21353 539 21458 540 21586 541 21691 542 21820 543 21926 544 22056 545 22163 546 22293 547 22401 548 22532 549 22641 550 22774 551 22883 552 23017 553 23126 554 23261 555 23372 556 23507 557 23619 558 23754 559 23867 560 24004 561 24118 562 24256 563 24370 564 24509 565 24624 566 24764 567 24880 568 25020 569 25137 570 25278 571 25396 572 25539 573 25657 574 25801 575 25920 576 26065 577 26185 578 26330 579 26451 580 26597 581 26719 582 26866 583 26989 584 27137 585 27261 586 27410 587 27535 588 27685 589 27810 590 27961 591 28087 592 28239 593 28366 594 28519 595 28647 596 28801 597 28930 598 29085 599 29215 600 29371 601 29501 602 29658 603 29789 604 29947 605 30080 606 30238 607 30372 608 30531 609 30666 610 30827 611 30962 612 31124 613 31259 614 31422 615 31559 616 31723 617 31861 618 32025 619 32164 620 32330 621 32470 622 32637 623 32777 624 32945 625 33086 626 33255 627 33398 628 33567 629 33711 630 33881 631 34026 632 34198 633 34343 634 34516 635 34662 636 34836 637 34983 638 35158 639 35306 640 35482 641 35631 642 35808 643 35958 644 36136 645 36287 646 36466 647 36618 648 36798 649 36951 650 37132 651 37286 652 37468 653 37623 654 37806 655 37962 656 38146 657 38303 658 38488 659 38646 660 38833 661 38991 662 39179 663 39338 664 39527 665 39688 666 39877 667 40039 668 40229 669 40392 670 40584 671 40748 672 40941 673 41105 674 41299 675 41465 676 41660 677 41827 678 42022 679 42190 680 42387 681 42556 682 42755 683 42924 684 43124 685 43294 686 43495 687 43667 688 43868 689 44041 690 44243 691 44417 692 44621 693 44796 694 45001 695 45177 696 45383 697 45560 698 45767 699 45945 700 46153 701 46332 702 46541 703 46721 704 46932 705 47113 706 47325 707 47507 708 47720 709 47903 710 48117 711 48301 712 48516 713 48701 714 48917 715 49104 716 49321 717 49509 718 49727 719 49916 720 50136 721 50325 722 50546 723 50736 724 50958 725 51150 726 51373 727 51566 728 51790 729 51984 730 52210 731 52405 732 52632 733 52827 734 53055 735 53252 736 53481 737 53680 738 53909 739 54109 740 54340 741 54541 742 54774 743 54975 744 55209 745 55411 746 55646 747 55850 748 56086 749 56291 750 56528 751 56734 752 56973 753 57180 754 57420 755 57628 756 57869 757 58078 758 58320 759 58531 760 58774 761 58986 762 59230 763 59443 764 59689 765 59903 766 60150 767 60365 768 60613 769 60829 770 61079 771 61296 772 61547 773 61765 774 62017 775 62237 776 62490 777 62711 778 62965 779 63187 780 63443 781 63666 782 63923 783 64147 784 64405 785 64631 786 64890 787 65117 788 65377 789 65605 790 65867 791 66096 792 66360 793 66589 794 66854 795 67085 796 67351 797 67584 798 67850 799 68084 800 68352 801 68587 802 68857 803 69093 804 69364 805 69601 806 69873 807 70112 808 70385 809 70625 810 70899 811 71140 812 71416 813 71658 814 71936 815 72179 816 72458 817 72702 818 72982 819 73228 820 73509 821 73756 822 74038 823 74286 824 74570 825 74820 826 75105 827 75356 828 75642 829 75894 830 76182 831 76435 832 76724 833 76978 834 77268 835 77524 836 77816 837 78073 838 78366 839 78624 840 78919 841 79178 842 79474 843 79734 844 80031 845 80293 846 80591 847 80855 848 81154 849 81419 850 81720 851 81986 852 82289 853 82555 854 82859 855 83127 856 83432 857 83702 858 84008 859 84279 860 84587 861 84859 862 85169 863 85442 864 85753 865 86027 866 86339 867 86615 868 86928 869 87206 870 87520 871 87799 872 88115 873 88395 874 88713 875 88994 876 89313 877 89595 878 89915 879 90199 880 90521 881 90806 882 91129 883 91415 884 91740 885 92028 886 92354 887 92643 888 92970 889 93260 890 93589 891 93881 892 94211 893 94504 894 94835 895 95130 896 95463 897 95759 898 96093 899 96390 900 96726 901 97024 902 97362 903 97661 904 98000 905 98301 906 98641 907 98944 908 99285 909 99589 910 99932 911 100237 912 100582 913 100888 914 101234 915 101542 916 101889 917 102199 918 102547 919 102858 920 103208 921 103520 922 103872 923 104185 924 104539 925 104853 926 105208 927 105524 928 105880 929 106198 930 106555 931 106874 932 107233 933 107553 934 107914 935 108236 936 108598 937 108921 938 109284 939 109609 940 109974 941 110300 942 110666 943 110993 944 111361 945 111690 946 112060 947 112390 948 112761 949 113092 950 113465 951 113798 952 114172 953 114506 954 114881 955 115217 956 115594 957 115932 958 116310 959 116649 960 117029 961 117369 962 117751 963 118092 964 118475 965 118818 966 119202 967 119547 968 119933 969 120279 970 120667 971 121014 972 121404 973 121752 974 122143 975 122493 976 122885 977 123237 978 123630 979 123984 980 124379 981 124734 982 125131 983 125487 984 125886 985 126243 986 126643 987 127002 988 127403 989 127764 990 128167 991 128529 992 128934 993 129297 994 129704 995 130069 996 130477 997 130843 998 131252 999 131620 1000 132031