0 1 1 1 2 2 3 3 4 5 5 7 6 11 7 15 8 22 9 30 10 12 11 14 12 21 13 24 14 34 15 17 16 21 17 25 18 33 19 39 20 24 21 27 22 34 23 39 24 50 25 30 26 36 27 42 28 50 29 58 30 40 31 44 32 53 33 60 34 71 35 48 36 56 37 63 38 73 39 83 40 60 41 66 42 77 43 85 44 99 45 71 46 80 47 89 48 102 49 113 50 85 51 93 52 106 53 116 54 132 55 98 56 110 57 121 58 135 59 149 60 116 61 125 62 140 63 153 64 171 65 131 66 145 67 158 68 175 69 191 70 151 71 163 72 181 73 195 74 216 75 170 76 186 77 201 78 221 79 239 80 193 81 207 82 227 83 244 84 268 85 214 86 233 87 251 88 273 89 294 90 241 91 257 92 280 93 300 94 326 95 265 96 287 97 307 98 332 99 356 100 295 101 314 102 340 103 362 104 392 105 323 106 347 107 370 108 399 109 425 110 356 111 378 112 407 113 432 114 465 115 387 116 415 117 441 118 472 119 502 120 425 121 449 122 481 123 510 124 546 125 459 126 490 127 519 128 554 129 587 130 500 131 528 132 564 133 595 134 635 135 539 136 573 137 605 138 644 139 680 140 584 141 615 142 654 143 689 144 733 145 626 146 664 147 700 148 742 149 782 150 676 151 710 152 753 153 792 154 839 155 722 156 764 157 803 158 849 159 893 160 776 161 814 162 861 163 903 164 955 165 827 166 872 167 915 168 966 169 1013 170 885 171 927 172 978 173 1024 174 1080 175 940 176 990 177 1037 178 1091 179 1143 180 1004 181 1049 182 1104 183 1155 184 1215 185 1063 186 1117 187 1168 188 1227 189 1283 190 1131 191 1181 192 1241 193 1295 194 1360 195 1196 196 1254 197 1309 198 1373 199 1433 200 1269 201 1323 202 1387 203 1446 204 1516 205 1338 206 1401 207 1461 208 1529 209 1594 210 1417 211 1475 212 1544 213 1608 214 1682 215 1491 216 1559 217 1623 218 1696 219 1766 220 1575 221 1638 222 1712 223 1780 224 1860 225 1655 226 1727 227 1796 228 1875 229 1949 230 1744 231 1812 232 1891 233 1964 234 2049 235 1829 236 1907 237 1981 238 2064 239 2144 240 1925 241 1997 242 2081 243 2160 244 2250 245 2015 246 2098 247 2177 248 2266 249 2351 250 2116 251 2194 252 2284 253 2367 254 2463 255 2213 256 2301 257 2385 258 2480 259 2570 260 2320 261 2403 262 2498 263 2587 264 2689 265 2422 266 2516 267 2606 268 2706 269 2802 270 2536 271 2624 272 2725 273 2820 274 2927 275 2644 276 2744 277 2839 278 2945 279 3047 280 2764 281 2858 282 2965 283 3065 284 3179 285 2879 286 2984 287 3085 288 3198 289 3305 290 3005 291 3105 292 3218 293 3324 294 3444 295 3126 296 3238 297 3345 298 3463 299 3577 300 3260 301 3365 302 3484 303 3597 304 3723 305 3387 306 3505 307 3618 308 3743 309 3863 310 3527 311 3639 312 3765 313 3883 314 4016 315 3662 316 3786 317 3905 318 4037 319 4163 320 3809 321 3927 322 4059 323 4184 324 4324 325 3950 326 4081 327 4207 328 4345 329 4478 330 4105 331 4229 332 4368 333 4500 334 4646 335 4253 336 4391 337 4523 338 4668 339 4808 340 4415 341 4546 342 4692 343 4830 344 4984 345 4571 346 4715 347 4854 348 5007 349 5153 350 4740 351 4878 352 5031 353 5176 354 5337 355 4903 356 5055 357 5201 358 5360 359 5514 360 5081 361 5225 362 5385 363 5538 364 5706 365 5251 366 5410 367 5563 368 5730 369 5891 370 5436 371 5588 372 5756 373 5915 374 6091 375 5615 376 5781 377 5941 378 6116 379 6284 380 5808 381 5967 382 6142 383 6309 384 6493 385 5994 386 6168 387 6336 388 6518 389 6694 390 6196 391 6362 392 6545 393 6720 394 6911 395 6390 396 6572 397 6747 398 6937 399 7121 400 6600 401 6774 402 6965 403 7147 404 7347 405 6803 406 6992 407 7175 408 7374 409 7565 410 7021 411 7203 412 7402 413 7592 414 7800 415 7232 416 7430 417 7621 418 7827 419 8027 420 7460 421 7649 422 7856 423 8055 424 8271 425 7679 426 7885 427 8084 428 8299 429 8507 430 7915 431 8113 432 8329 433 8535 434 8760 435 8144 436 8358 437 8565 438 8789 439 9005 440 8389 441 8595 442 8819 443 9034 444 9268 445 8626 446 8849 447 9065 448 9297 449 9522 450 8881 451 9095 452 9328 453 9552 454 9794 455 9127 456 9359 457 9583 458 9824 459 10058 460 9391 461 9614 462 9856 463 10088 464 10340 465 9647 466 9887 467 10120 468 10371 469 10613 470 9920 471 10152 472 10403 473 10644 474 10905 475 10185 476 10435 477 10677 478 10936 479 11188 480 10469 481 10709 482 10969 483 11220 484 11490 485 10743 486 11002 487 11253 488 11522 489 11783 490 11036 491 11286 492 11556 493 11815 494 12095 495 11321 496 11589 497 11849 498 12128 499 12398 500 11624 501 11883 502 12162 503 12431 504 12721 505 11918 506 12196 507 12466 508 12754 509 13034 510 12232 511 12500 512 12789 513 13068 514 13367 515 12536 516 12824 517 13103 518 13401 519 13691 520 12860 521 13138 522 13437 523 13725 524 14035 525 13175 526 13472 527 13761 528 14070 529 14369 530 13509 531 13797 532 14106 533 14404 534 14724 535 13834 536 14142 537 14441 538 14759 539 15069 540 14180 541 14477 542 14796 543 15105 544 15435 545 14515 546 14833 547 15142 548 15471 549 15791 550 14871 551 15179 552 15509 553 15827 554 16168 555 15218 556 15546 557 15865 558 16205 559 16535 560 15585 561 15903 562 16243 563 16572 564 16924 565 15942 566 16281 567 16611 568 16961 569 17302 570 16321 571 16649 572 17000 573 17340 574 17702 575 16689 576 17039 577 17379 578 17740 579 18092 580 17079 581 17418 582 17780 583 18130 584 18504 585 17459 586 17819 587 18170 588 18543 589 18905 590 17860 591 18210 592 18583 593 18944 594 19329 595 18251 596 18623 597 18985 598 19368 599 19742 600 18665 601 19025 602 19409 603 19782 604 20178 605 19067 606 19450 607 19823 608 20218 609 20603 610 19492 611 19864 612 20260 613 20643 614 21051 615 19907 616 20301 617 20685 618 21092 619 21488 620 20344 621 20727 622 21134 623 21529 624 21949 625 20770 626 21176 627 21572 628 21990 629 22398 630 21220 631 21614 632 22033 633 22440 634 22871 635 21658 636 22076 637 22483 638 22913 639 23333 640 22120 641 22526 642 22957 643 23375 644 23819 645 22571 646 23000 647 23419 648 23862 649 24293 650 23045 651 23463 652 23906 653 24336 654 24792 655 23508 656 23950 657 24381 658 24835 659 25279 660 23996 661 24425 662 24880 663 25323 664 25791 665 24471 666 24925 667 25368 668 25835 669 26291 670 24971 671 25413 672 25881 673 26335 674 26816 675 25460 676 25926 677 26381 678 26861 679 27329 680 25973 681 26427 682 26907 683 27374 684 27868 685 26474 686 26953 687 27421 688 27913 689 28394 690 27001 691 27467 692 27960 693 28440 694 28946 695 27515 696 28007 697 28487 698 28992 699 29486 700 28055 701 28534 702 29040 703 29532 704 30052 705 28583 706 29087 707 29580 708 30099 709 30605 710 29136 711 29628 712 30147 713 30652 714 31185 715 29677 716 30195 717 30701 718 31232 719 31752 720 30245 721 30749 722 31281 723 31800 724 32346 725 30799 726 31330 727 31849 728 32394 729 32927 730 31380 731 31898 732 32444 733 32975 734 33535 735 31949 736 32493 737 33025 738 33584 739 34130 740 32544 741 33075 742 33634 743 34179 744 34753 745 33126 746 33684 747 34230 748 34802 749 35362 750 33736 751 34280 752 34853 753 35412 754 35999 755 34332 756 34904 757 35463 758 36049 759 36623 760 34956 761 35514 762 36101 763 36673 764 37275 765 35567 766 36152 767 36725 768 37326 769 37913 770 36205 771 36777 772 37378 773 37964 774 38580 775 36830 776 37430 777 38017 778 38631 779 39233 780 37484 781 38069 782 38684 783 39285 784 39915 785 38123 786 38737 787 39338 788 39967 789 40583 790 38791 791 39391 792 40021 793 40635 794 41280 795 39446 796 40074 797 40689 798 41333 799 41963 800 40129 801 40743 802 41387 803 42016 804 42676 805 40798 806 41441 807 42071 808 42729 809 43374 810 41497 811 42125 812 42784 813 43428 814 44102 815 42181 816 42839 817 43483 818 44156 819 44816 820 42895 821 43538 822 44212 823 44870 824 45560 825 43595 826 44267 827 44926 828 45615 829 46289 830 44324 831 44982 832 45671 833 46344 834 47049 835 45039 836 45727 837 46401 838 47104 839 47794 840 45785 841 46457 842 47161 843 47850 844 48570 845 46515 846 47218 847 47907 848 48626 849 49331 850 47276 851 47964 852 48684 853 49387 854 50123 855 48023 856 48741 857 49445 858 50180 859 50900 860 48800 861 49503 862 50238 863 50957 864 51709 865 49562 866 50296 867 51016 868 51766 869 52502 870 50356 871 51074 872 51825 873 52560 874 53327 875 51134 876 51884 877 52619 878 53385 879 54137 880 51944 881 52678 882 53445 883 54195 884 54979 885 52739 886 53504 887 54255 888 55038 889 55805 890 53565 891 54315 892 55098 893 55864 894 56664 895 54376 896 55158 897 55925 898 56723 899 57507 900 55220 901 55985 902 56784 903 57567 904 58383 905 56047 906 56845 907 57628 908 58443 909 59243 910 56907 911 57689 912 58505 913 59303 914 60136 915 57752 916 58566 917 59365 918 60197 919 61013 920 58629 921 59427 922 60259 923 61074 924 61924 925 59490 926 60321 927 61137 928 61985 929 62818 930 60385 931 61199 932 62048 933 62880 934 63746 935 61263 936 62111 937 62943 938 63808 939 64658 940 62175 941 63006 942 63872 943 64720 944 65604 945 63071 946 63935 947 64784 948 65667 949 66533 950 64000 951 64848 952 65731 953 66596 954 67497 955 64913 956 65795 957 66661 958 67560 959 68444 960 65861 961 66725 962 67625 963 68508 964 69426 965 66791 966 67690 967 68573 968 69490 969 70391 970 67756 971 68638 972 69556 973 70455 974 71391 975 68705 976 69621 977 70521 978 71456 979 72374 980 69688 981 70587 982 71522 983 72439 984 73393 985 70654 986 71588 987 72506 988 73458 989 74394 990 71656 991 72572 992 73525 993 74460 994 75431 995 72640 996 73592 997 74527 998 75497 999 76451 1000 73660