0 1 1 0 2 0 3 1 4 0 5 1 6 1 7 1 8 1 9 1 10 3 11 1 12 2 13 3 14 2 15 4 16 3 17 4 18 4 19 4 20 7 21 5 22 6 23 7 24 7 25 9 26 8 27 10 28 10 29 10 30 14 31 12 32 13 33 15 34 15 35 18 36 17 37 19 38 20 39 20 40 25 41 23 42 25 43 27 44 27 45 32 46 30 47 33 48 35 49 35 50 41 51 39 52 42 53 44 54 45 55 51 56 49 57 53 58 55 59 56 60 63 61 61 62 65 63 68 64 69 65 76 66 75 67 79 68 82 69 84 70 92 71 90 72 95 73 99 74 100 75 109 76 108 77 113 78 117 79 119 80 129 81 127 82 133 83 138 84 140 85 150 86 149 87 156 88 160 89 163 90 175 91 173 92 180 93 186 94 189 95 200 96 200 97 208 98 213 99 217 100 230 101 229 102 237 103 244 104 248 105 261 106 261 107 270 108 277 109 281 110 296 111 296 112 305 113 313 114 318 115 333 116 333 117 344 118 352 119 357 120 374 121 374 122 385 123 394 124 400 125 417 126 418 127 430 128 439 129 446 130 464 131 465 132 478 133 488 134 495 135 514 136 516 137 529 138 540 139 548 140 568 141 570 142 584 143 596 144 604 145 625 146 628 147 643 148 655 149 664 150 687 151 689 152 705 153 719 154 728 155 751 156 755 157 772 158 785 159 796 160 821 161 824 162 842 163 857 164 868 165 893 166 898 167 917 168 932 169 944 170 971 171 976 172 995 173 1012 174 1025 175 1052 176 1058 177 1079 178 1096 179 1109 180 1139 181 1145 182 1166 183 1185 184 1199 185 1229 186 1236 187 1259 188 1278 189 1293 190 1325 191 1332 192 1356 193 1376 194 1392 195 1425 196 1433 197 1458 198 1479 199 1496 200 1530 201 1539 202 1565 203 1587 204 1605 205 1640 206 1650 207 1677 208 1700 209 1719 210 1756 211 1766 212 1794 213 1819 214 1838 215 1876 216 1888 217 1917 218 1942 219 1963 220 2003 221 2014 222 2045 223 2072 224 2093 225 2134 226 2147 227 2179 228 2206 229 2229 230 2272 231 2285 232 2318 233 2347 234 2371 235 2414 236 2429 237 2464 238 2493 239 2518 240 2564 241 2579 242 2614 243 2646 244 2672 245 2718 246 2735 247 2772 248 2804 249 2831 250 2880 251 2897 252 2935 253 2969 254 2997 255 3047 256 3065 257 3105 258 3140 259 3169 260 3221 261 3240 262 3281 263 3317 264 3348 265 3401 266 3421 267 3464 268 3501 269 3533 270 3588 271 3609 272 3653 273 3692 274 3725 275 3781 276 3804 277 3849 278 3889 279 3924 280 3982 281 4005 282 4052 283 4094 284 4129 285 4189 286 4214 287 4262 288 4305 289 4342 290 4404 291 4429 292 4479 293 4524 294 4562 295 4625 296 4652 297 4704 298 4749 299 4789 300 4855 301 4882 302 4935 303 4983 304 5024 305 5090 306 5120 307 5175 308 5223 309 5266 310 5335 311 5365 312 5421 313 5472 314 5516 315 5586 316 5618 317 5676 318 5728 319 5773 320 5846 321 5879 322 5938 323 5992 324 6039 325 6113 326 6147 327 6209 328 6264 329 6312 330 6389 331 6424 332 6487 333 6544 334 6594 335 6672 336 6709 337 6774 338 6832 339 6884 340 6964 341 7002 342 7069 343 7129 344 7182 345 7264 346 7304 347 7372 348 7434 349 7489 350 7573 351 7614 352 7684 353 7748 354 7804 355 7890 356 7933 357 8005 358 8070 359 8128 360 8217 361 8260 362 8334 363 8402 364 8461 365 8551 366 8597 367 8673 368 8741 369 8803 370 8896 371 8942 372 9020 373 9091 374 9154 375 9248 376 9297 377 9377 378 9449 379 9514 380 9611 381 9661 382 9742 383 9817 384 9884 385 9982 386 10034 387 10118 388 10194 389 10262 390 10364 391 10417 392 10502 393 10581 394 10651 395 10754 396 10809 397 10897 398 10977 399 11049 400 11155 401 11211 402 11301 403 11383 404 11457 405 11565 406 11623 407 11715 408 11799 409 11875 410 11985 411 12045 412 12139 413 12225 414 12303 415 12415 416 12477 417 12573 418 12661 419 12741 420 12856 421 12919 422 13017 423 13108 424 13189 425 13306 426 13372 427 13472 428 13564 429 13648 430 13768 431 13834 432 13937 433 14032 434 14117 435 14239 436 14308 437 14413 438 14509 439 14597 440 14722 441 14792 442 14899 443 14998 444 15088 445 15214 446 15287 447 15397 448 15497 449 15589 450 15719 451 15793 452 15904 453 16008 454 16102 455 16233 456 16310 457 16424 458 16529 459 16625 460 16760 461 16838 462 16954 463 17062 464 17160 465 17297 466 17377 467 17496 468 17606 469 17706 470 17846 471 17928 472 18049 473 18161 474 18264 475 18406 476 18490 477 18614 478 18728 479 18833 480 18978 481 19064 482 19190 483 19307 484 19414 485 19561 486 19650 487 19778 488 19897 489 20007 490 20157 491 20247 492 20378 493 20500 494 20611 495 20764 496 20857 497 20990 498 21114 499 21228 500 21384 501 21478 502 21614 503 21741 504 21857 505 22015 506 22112 507 22251 508 22379 509 22498 510 22660 511 22758 512 22899 513 23031 514 23152 515 23315 516 23417 517 23561 518 23694 519 23818 520 23985 521 24088 522 24234 523 24371 524 24497 525 24666 526 24772 527 24921 528 25060 529 25188 530 25361 531 25469 532 25620 533 25762 534 25893 535 26068 536 26178 537 26333 538 26477 539 26610 540 26789 541 26901 542 27058 543 27205 544 27341 545 27522 546 27637 547 27797 548 27946 549 28085 550 28269 551 28386 552 28549 553 28701 554 28842 555 29029 556 29149 557 29314 558 29469 559 29613 560 29803 561 29925 562 30093 563 30251 564 30397 565 30590 566 30715 567 30886 568 31046 569 31195 570 31392 571 31518 572 31692 573 31856 574 32007 575 32206 576 32336 577 32513 578 32678 579 32833 580 33036 581 33167 582 33347 583 33516 584 33673 585 33878 586 34013 587 34196 588 34367 589 34527 590 34736 591 34873 592 35058 593 35233 594 35396 595 35607 596 35747 597 35936 598 36113 599 36278 600 36494 601 36636 602 36827 603 37008 604 37176 605 37394 606 37539 607 37734 608 37917 609 38088 610 38310 611 38457 612 38655 613 38841 614 39015 615 39240 616 39390 617 39591 618 39780 619 39957 620 40185 621 40338 622 40542 623 40734 624 40914 625 41145 626 41301 627 41508 628 41703 629 41886 630 42121 631 42279 632 42489 633 42688 634 42873 635 43111 636 43273 637 43486 638 43687 639 43876 640 44118 641 44281 642 44498 643 44703 644 44894 645 45139 646 45306 647 45526 648 45733 649 45928 650 46177 651 46346 652 46569 653 46780 654 46978 655 47229 656 47402 657 47629 658 47842 659 48043 660 48299 661 48474 662 48703 663 48921 664 49125 665 49383 666 49562 667 49795 668 50015 669 50222 670 50485 671 50666 672 50902 673 51126 674 51336 675 51602 676 51786 677 52026 678 52253 679 52466 680 52736 681 52923 682 53166 683 53396 684 53613 685 53886 686 54076 687 54323 688 54556 689 54776 690 55053 691 55246 692 55496 693 55733 694 55956 695 56236 696 56433 697 56686 698 56926 699 57153 700 57437 701 57636 702 57893 703 58137 704 58366 705 58654 706 58857 707 59117 708 59364 709 59597 710 59889 711 60094 712 60358 713 60609 714 60845 715 61140 716 61349 717 61617 718 61870 719 62110 720 62410 721 62621 722 62892 723 63150 724 63393 725 63695 726 63911 727 64186 728 64446 729 64693 730 65000 731 65218 732 65496 733 65761 734 66011 735 66321 736 66543 737 66825 738 67093 739 67346 740 67661 741 67886 742 68171 743 68443 744 68700 745 69018 746 69246 747 69536 748 69811 749 70071 750 70394 751 70625 752 70918 753 71197 754 71461 755 71787 756 72022 757 72319 758 72601 759 72869 760 73199 761 73437 762 73738 763 74024 764 74295 765 74629 766 74871 767 75175 768 75465 769 75740 770 76078 771 76323 772 76631 773 76925 774 77203 775 77545 776 77794 777 78106 778 78403 779 78685 780 79032 781 79283 782 79599 783 79901 784 80186 785 80536 786 80792 787 81112 788 81416 789 81706 790 82061 791 82319 792 82643 793 82952 794 83245 795 83603 796 83866 797 84194 798 84506 799 84803 800 85166 801 85432 802 85763 803 86080 804 86381 805 86747 806 87017 807 87353 808 87673 809 87977 810 88349 811 88622 812 88961 813 89286 814 89594 815 89969 816 90246 817 90590 818 90918 819 91230 820 91610 821 91890 822 92238 823 92570 824 92886 825 93270 826 93554 827 93906 828 94242 829 94562 830 94950 831 95238 832 95594 833 95934 834 96258 835 96650 836 96942 837 97302 838 97646 839 97974 840 98371 841 98666 842 99030 843 99379 844 99710 845 100111 846 100411 847 100779 848 101131 849 101467 850 101873 851 102175 852 102548 853 102905 854 103244 855 103654 856 103961 857 104338 858 104698 859 105042 860 105457 861 105767 862 106148 863 106513 864 106861 865 107279 866 107594 867 107980 868 108348 869 108700 870 109124 871 109442 872 109831 873 110205 874 110561 875 110988 876 111311 877 111705 878 112082 879 112442 880 112875 881 113201 882 113599 883 113981 884 114345 885 114782 886 115112 887 115515 888 115901 889 116269 890 116711 891 117045 892 117452 893 117842 894 118215 895 118661 896 118999 897 119411 898 119805 899 120182 900 120633 901 120975 902 121391 903 121790 904 122171 905 122626 906 122973 907 123393 908 123796 909 124182 910 124642 911 124992 912 125417 913 125825 914 126214 915 126679 916 127034 917 127463 918 127875 919 128269 920 128739 921 129097 922 129531 923 129948 924 130346 925 130820 926 131183 927 131622 928 132042 929 132445 930 132925 931 133291 932 133734 933 134160 934 134567 935 135050 936 135422 937 135870 938 136299 939 136711 940 137200 941 137575 942 138027 943 138462 944 138878 945 139371 946 139751 947 140208 948 140647 949 141067 950 141566 951 141950 952 142411 953 142855 954 143280 955 143783 956 144171 957 144638 958 145086 959 145515 960 146024 961 146416 962 146887 963 147340 964 147774 965 148287 966 148684 967 149160 968 149617 969 150056 970 150574 971 150975 972 151456 973 151918 974 152361 975 152884 976 153290 977 153775 978 154242 979 154690 980 155218 981 155628 982 156118 983 156590 984 157042 985 157575 986 157990 987 158485 988 158961 989 159418 990 159957 991 160375 992 160875 993 161357 994 161818 995 162361 996 162785 997 163290 998 163775 999 164242 1000 164791