0 1 1 0 2 0 3 1 4 0 5 1 6 1 7 0 8 1 9 2 10 1 11 2 12 2 13 1 14 3 15 3 16 2 17 3 18 4 19 3 20 5 21 5 22 4 23 6 24 6 25 6 26 7 27 8 28 7 29 9 30 10 31 9 32 11 33 12 34 11 35 13 36 15 37 13 38 16 39 17 40 16 41 19 42 20 43 19 44 22 45 24 46 22 47 26 48 27 49 26 50 30 51 31 52 30 53 34 54 36 55 35 56 39 57 40 58 40 59 44 60 46 61 45 62 49 63 52 64 51 65 56 66 58 67 57 68 62 69 65 70 64 71 69 72 72 73 71 74 77 75 80 76 79 77 85 78 88 79 87 80 94 81 97 82 96 83 103 84 106 85 106 86 113 87 116 88 116 89 123 90 127 91 127 92 134 93 138 94 138 95 146 96 150 97 150 98 158 99 163 100 163 101 171 102 176 103 176 104 185 105 190 106 190 107 199 108 205 109 205 110 215 111 220 112 220 113 231 114 236 115 237 116 247 117 253 118 254 119 265 120 271 121 272 122 283 123 289 124 291 125 302 126 309 127 310 128 322 129 329 130 331 131 343 132 350 133 352 134 364 135 373 136 374 137 387 138 395 139 397 140 411 141 419 142 421 143 435 144 444 145 446 146 461 147 469 148 472 149 487 150 496 151 499 152 514 153 524 154 527 155 543 156 552 157 556 158 572 159 582 160 586 161 602 162 613 163 617 164 634 165 645 166 649 167 666 168 678 169 682 170 700 171 712 172 716 173 735 174 747 175 752 176 771 177 783 178 788 179 808 180 821 181 826 182 846 183 859 184 865 185 886 186 899 187 905 188 926 189 940 190 947 191 968 192 982 193 989 194 1011 195 1026 196 1033 197 1055 198 1071 199 1078 200 1101 201 1117 202 1124 203 1148 204 1164 205 1172 206 1196 207 1213 208 1221 209 1246 210 1263 211 1271 212 1297 213 1314 214 1323 215 1349 216 1367 217 1376 218 1403 219 1421 220 1431 221 1458 222 1476 223 1487 224 1514 225 1534 226 1544 227 1572 228 1592 229 1603 230 1632 231 1652 232 1663 233 1692 234 1714 235 1725 236 1755 237 1776 238 1788 239 1819 240 1841 241 1853 242 1884 243 1907 244 1919 245 1952 246 1974 247 1987 248 2020 249 2043 250 2057 251 2090 252 2114 253 2128 254 2162 255 2186 256 2201 257 2235 258 2260 259 2275 260 2310 261 2336 262 2351 263 2387 264 2413 265 2429 266 2465 267 2492 268 2508 269 2545 270 2573 271 2589 272 2627 273 2655 274 2672 275 2711 276 2739 277 2756 278 2796 279 2825 280 2843 281 2883 282 2912 283 2931 284 2972 285 3002 286 3021 287 3062 288 3093 289 3113 290 3155 291 3186 292 3206 293 3249 294 3281 295 3302 296 3345 297 3378 298 3399 299 3443 300 3477 301 3498 302 3543 303 3577 304 3599 305 3645 306 3680 307 3702 308 3749 309 3784 310 3807 311 3855 312 3890 313 3914 314 3962 315 3999 316 4023 317 4072 318 4109 319 4134 320 4184 321 4221 322 4247 323 4297 324 4336 325 4362 326 4413 327 4452 328 4479 329 4531 330 4571 331 4598 332 4650 333 4692 334 4719 335 4773 336 4814 337 4842 338 4897 339 4939 340 4968 341 5023 342 5066 343 5095 344 5152 345 5195 346 5225 347 5282 348 5326 349 5357 350 5415 351 5460 352 5491 353 5550 354 5595 355 5628 356 5687 357 5733 358 5766 359 5826 360 5874 361 5907 362 5968 363 6016 364 6050 365 6112 366 6161 367 6195 368 6258 369 6308 370 6343 371 6407 372 6457 373 6493 374 6558 375 6609 376 6645 377 6711 378 6763 379 6800 380 6867 381 6919 382 6957 383 7025 384 7078 385 7117 386 7185 387 7239 388 7279 389 7348 390 7403 391 7443 392 7513 393 7569 394 7610 395 7681 396 7738 397 7779 398 7851 399 7909 400 7951 401 8024 402 8082 403 8125 404 8199 405 8259 406 8302 407 8377 408 8437 409 8481 410 8558 411 8618 412 8663 413 8740 414 8802 415 8848 416 8926 417 8988 418 9035 419 9114 420 9177 421 9225 422 9304 423 9369 424 9417 425 9498 426 9563 427 9612 428 9694 429 9760 430 9810 431 9892 432 9960 433 10010 434 10094 435 10162 436 10213 437 10298 438 10367 439 10419 440 10505 441 10575 442 10627 443 10715 444 10785 445 10839 446 10927 447 10998 448 11053 449 11142 450 11215 451 11270 452 11360 453 11433 454 11490 455 11581 456 11655 457 11712 458 11804 459 11880 460 11938 461 12031 462 12107 463 12166 464 12260 465 12338 466 12397 467 12492 468 12571 469 12631 470 12728 471 12807 472 12868 473 12966 474 13046 475 13108 476 13207 477 13288 478 13351 479 13451 480 13533 481 13597 482 13698 483 13781 484 13846 485 13948 486 14032 487 14098 488 14201 489 14286 490 14353 491 14457 492 14543 493 14611 494 14716 495 14804 496 14872 497 14978 498 15067 499 15136 500 15244 501 15333 502 15403 503 15512 504 15603 505 15674 506 15784 507 15875 508 15947 509 16059 510 16151 511 16224 512 16336 513 16430 514 16504 515 16618 516 16712 517 16787 518 16902 519 16997 520 17074 521 17189 522 17286 523 17363 524 17480 525 17578 526 17656 527 17774 528 17873 529 17952 530 18071 531 18172 532 18251 533 18372 534 18473 535 18554 536 18676 537 18778 538 18860 539 18983 540 19087 541 19169 542 19294 543 19398 544 19482 545 19608 546 19713 547 19798 548 19925 549 20032 550 20118 551 20246 552 20353 553 20441 554 20570 555 20679 556 20767 557 20897 558 21008 559 21097 560 21229 561 21340 562 21430 563 21563 564 21676 565 21767 566 21901 567 22015 568 22107 569 22243 570 22358 571 22451 572 22588 573 22704 574 22798 575 22937 576 23054 577 23149 578 23289 579 23407 580 23504 581 23645 582 23764 583 23862 584 24004 585 24125 586 24224 587 24367 588 24489 589 24589 590 24734 591 24857 592 24958 593 25104 594 25229 595 25331 596 25478 597 25604 598 25707 599 25856 600 25983 601 26087 602 26237 603 26366 604 26471 605 26623 606 26752 607 26858 608 27012 609 27142 610 27250 611 27404 612 27536 613 27645 614 27801 615 27934 616 28044 617 28201 618 28335 619 28447 620 28605 621 28741 622 28853 623 29013 624 29150 625 29264 626 29425 627 29563 628 29678 629 29840 630 29981 631 30096 632 30260 633 30401 634 30518 635 30684 636 30826 637 30944 638 31111 639 31255 640 31374 641 31543 642 31687 643 31808 644 31978 645 32124 646 32246 647 32417 648 32565 649 32688 650 32861 651 33009 652 33134 653 33308 654 33458 655 33584 656 33759 657 33911 658 34038 659 34215 660 34368 661 34496 662 34674 663 34829 664 34958 665 35138 666 35294 667 35424 668 35606 669 35763 670 35895 671 36078 672 36236 673 36369 674 36554 675 36714 676 36848 677 37034 678 37195 679 37331 680 37519 681 37681 682 37818 683 38007 684 38171 685 38310 686 38500 687 38665 688 38805 689 38997 690 39164 691 39305 692 39498 693 39667 694 39809 695 40004 696 40174 697 40317 698 40514 699 40685 700 40830 701 41028 702 41201 703 41347 704 41547 705 41721 706 41868 707 42070 708 42245 709 42394 710 42597 711 42774 712 42924 713 43129 714 43307 715 43459 716 43665 717 43844 718 43998 719 44205 720 44387 721 44541 722 44750 723 44933 724 45089 725 45300 726 45484 727 45641 728 45853 729 46040 730 46198 731 46412 732 46599 733 46759 734 46975 735 47164 736 47325 737 47542 738 47733 739 47895 740 48115 741 48306 742 48470 743 48691 744 48884 745 49050 746 49272 747 49467 748 49634 749 49858 750 50054 751 50223 752 50448 753 50646 754 50816 755 51043 756 51243 757 51414 758 51643 759 51844 760 52017 761 52247 762 52450 763 52624 764 52856 765 53061 766 53236 767 53470 768 53676 769 53853 770 54089 771 54296 772 54474 773 54712 774 54921 775 55101 776 55340 777 55550 778 55732 779 55973 780 56185 781 56368 782 56610 783 56824 784 57009 785 57253 786 57468 787 57654 788 57900 789 58117 790 58305 791 58552 792 58771 793 58960 794 59209 795 59430 796 59620 797 59871 798 60093 799 60285 800 60538 801 60762 802 60955 803 61210 804 61435 805 61630 806 61887 807 62113 808 62310 809 62568 810 62797 811 62995 812 63255 813 63485 814 63685 815 63947 816 64178 817 64380 818 64643 819 64877 820 65080 821 65345 822 65580 823 65785 824 66052 825 66289 826 66495 827 66763 828 67003 829 67210 830 67481 831 67721 832 67930 833 68203 834 68445 835 68656 836 68930 837 69174 838 69386 839 69663 840 69908 841 70122 842 70400 843 70647 844 70863 845 71143 846 71392 847 71609 848 71891 849 72141 850 72361 851 72644 852 72896 853 73117 854 73402 855 73657 856 73879 857 74166 858 74422 859 74646 860 74935 861 75193 862 75418 863 75709 864 75969 865 76196 866 76489 867 76750 868 76979 869 77274 870 77537 871 77767 872 78064 873 78329 874 78561 875 78860 876 79126 877 79360 878 79661 879 79929 880 80165 881 80467 882 80737 883 80975 884 81279 885 81551 886 81790 887 82096 888 82370 889 82611 890 82919 891 83195 892 83437 893 83747 894 84025 895 84269 896 84581 897 84860 898 85106 899 85420 900 85702 901 85949 902 86265 903 86548 904 86797 905 87116 906 87400 907 87651 908 87971 909 88258 910 88511 911 88833 912 89121 913 89376 914 89700 915 89990 916 90247 917 90572 918 90865 919 91123 920 91451 921 91745 922 92005 923 92335 924 92631 925 92893 926 93224 927 93523 928 93786 929 94120 930 94420 931 94685 932 95021 933 95323 934 95590 935 95928 936 96232 937 96500 938 96841 939 97146 940 97417 941 97759 942 98066 943 98339 944 98683 945 98993 946 99267 947 99613 948 99924 949 100201 950 100549 951 100862 952 101140 953 101490 954 101806 955 102086 956 102438 957 102755 958 103037 959 103391 960 103711 961 103994 962 104350 963 104672 964 104957 965 105316 966 105639 967 105926 968 106287 969 106612 970 106901 971 107264 972 107591 973 107882 974 108247 975 108576 976 108869 977 109236 978 109567 979 109862 980 110231 981 110564 982 110861 983 111232 984 111567 985 111866 986 112239 987 112576 988 112877 989 113252 990 113592 991 113894 992 114271 993 114613 994 114917 995 115297 996 115640 997 115946 998 116328 999 116674 1000 116982