0 1 1 0 2 0 3 1 4 1 5 1 6 1 7 1 8 3 9 2 10 2 11 3 12 4 13 4 14 4 15 5 16 7 17 6 18 7 19 8 20 10 21 10 22 10 23 12 24 15 25 14 26 15 27 17 28 20 29 20 30 21 31 23 32 27 33 27 34 28 35 31 36 35 37 35 38 37 39 40 40 45 41 45 42 47 43 51 44 56 45 57 46 59 47 63 48 70 49 70 50 73 51 78 52 84 53 86 54 89 55 94 56 102 57 103 58 107 59 113 60 121 61 123 62 127 63 134 64 143 65 145 66 150 67 157 68 167 69 170 70 175 71 183 72 194 73 197 74 203 75 212 76 223 77 227 78 234 79 243 80 256 81 260 82 267 83 278 84 291 85 296 86 304 87 315 88 330 89 335 90 344 91 356 92 371 93 378 94 387 95 400 96 417 97 423 98 434 99 448 100 465 101 473 102 484 103 499 104 518 105 526 106 538 107 554 108 574 109 583 110 596 111 613 112 634 113 644 114 658 115 676 116 698 117 709 118 724 119 743 120 767 121 778 122 794 123 815 124 839 125 852 126 869 127 890 128 917 129 930 130 948 131 971 132 998 133 1013 134 1032 135 1056 136 1085 137 1100 138 1121 139 1146 140 1176 141 1193 142 1214 143 1241 144 1273 145 1290 146 1313 147 1341 148 1374 149 1393 150 1417 151 1446 152 1481 153 1501 154 1526 155 1557 156 1593 157 1614 158 1641 159 1673 160 1711 161 1733 162 1761 163 1795 164 1834 165 1858 166 1887 167 1922 168 1964 169 1988 170 2019 171 2056 172 2098 173 2125 174 2157 175 2195 176 2240 177 2267 178 2301 179 2341 180 2387 181 2416 182 2451 183 2493 184 2541 185 2571 186 2608 187 2651 188 2701 189 2733 190 2771 191 2816 192 2868 193 2901 194 2941 195 2988 196 3041 197 3076 198 3118 199 3166 200 3222 201 3258 202 3301 203 3352 204 3409 205 3447 206 3492 207 3544 208 3604 209 3643 210 3690 211 3744 212 3805 213 3847 214 3895 215 3951 216 4015 217 4057 218 4108 219 4166 220 4231 221 4276 222 4328 223 4388 224 4456 225 4502 226 4556 227 4618 228 4688 229 4736 230 4792 231 4856 232 4928 233 4978 234 5036 235 5102 236 5176 237 5228 238 5288 239 5356 240 5433 241 5486 242 5548 243 5619 244 5697 245 5753 246 5817 247 5889 248 5971 249 6028 250 6094 251 6169 252 6252 253 6312 254 6380 255 6457 256 6543 257 6604 258 6675 259 6754 260 6842 261 6906 262 6978 263 7060 264 7151 265 7216 266 7291 267 7375 268 7468 269 7536 270 7613 271 7699 272 7795 273 7865 274 7944 275 8033 276 8131 277 8203 278 8285 279 8376 280 8477 281 8551 282 8635 283 8729 284 8832 285 8909 286 8995 287 9091 288 9198 289 9276 290 9365 291 9464 292 9572 293 9654 294 9745 295 9846 296 9958 297 10041 298 10135 299 10239 300 10353 301 10439 302 10535 303 10642 304 10759 305 10847 306 10946 307 11055 308 11175 309 11266 310 11367 311 11479 312 11602 313 11695 314 11799 315 11914 316 12039 317 12135 318 12242 319 12359 320 12488 321 12586 322 12695 323 12816 324 12947 325 13048 326 13160 327 13283 328 13418 329 13521 330 13636 331 13762 332 13899 333 14006 334 14123 335 14252 336 14393 337 14501 338 14622 339 14754 340 14897 341 15009 342 15132 343 15267 344 15414 345 15528 346 15654 347 15792 348 15942 349 16059 350 16188 351 16329 352 16482 353 16602 354 16734 355 16878 356 17034 357 17157 358 17292 359 17439 360 17599 361 17724 362 17862 363 18013 364 18175 365 18304 366 18445 367 18598 368 18765 369 18896 370 19040 371 19197 372 19366 373 19501 374 19648 375 19808 376 19981 377 20118 378 20269 379 20432 380 20608 381 20749 382 20902 383 21069 384 21249 385 21392 386 21549 387 21719 388 21902 389 22049 390 22209 391 22382 392 22569 393 22719 394 22882 395 23059 396 23249 397 23402 398 23569 399 23749 400 23943 401 24099 402 24269 403 24453 404 24650 405 24810 406 24983 407 25170 408 25372 409 25534 410 25711 411 25902 412 26106 413 26273 414 26453 415 26647 416 26856 417 27025 418 27209 419 27407 420 27619 421 27792 422 27979 423 28181 424 28397 425 28573 426 28764 427 28969 428 29189 429 29369 430 29563 431 29772 432 29996 433 30179 434 30377 435 30590 436 30817 437 31004 438 31206 439 31422 440 31654 441 31844 442 32049 443 32270 444 32505 445 32699 446 32908 447 33132 448 33372 449 33569 450 33782 451 34010 452 34253 453 34455 454 34671 455 34903 456 35151 457 35355 458 35576 459 35812 460 36063 461 36272 462 36496 463 36736 464 36992 465 37204 466 37432 467 37676 468 37936 469 38152 470 38384 471 38632 472 38896 473 39116 474 39352 475 39604 476 39872 477 40096 478 40336 479 40592 480 40865 481 41092 482 41336 483 41597 484 41873 485 42105 486 42353 487 42617 488 42899 489 43134 490 43386 491 43655 492 43940 493 44180 494 44436 495 44709 496 44999 497 45242 498 45503 499 45780 500 46074 501 46322 502 46586 503 46868 504 47167 505 47418 506 47687 507 47973 508 48276 509 48532 510 48805 511 49095 512 49403 513 49663 514 49940 515 50235 516 50547 517 50811 518 51093 519 51392 520 51709 521 51977 522 52263 523 52567 524 52888 525 53161 526 53451 527 53759 528 54086 529 54362 530 54657 531 54970 532 55300 533 55582 534 55881 535 56198 536 56534 537 56819 538 57123 539 57445 540 57785 541 58075 542 58383 543 58710 544 59055 545 59349 546 59662 547 59993 548 60343 549 60642 550 60959 551 61295 552 61650 553 61953 554 62275 555 62616 556 62975 557 63283 558 63610 559 63955 560 64320 561 64632 562 64963 563 65314 564 65683 565 66000 566 66336 567 66691 568 67066 569 67387 570 67728 571 68088 572 68467 573 68794 574 69139 575 69504 576 69889 577 70219 578 70570 579 70940 580 71329 581 71665 582 72020 583 72395 584 72790 585 73130 586 73490 587 73870 588 74270 589 74615 590 74980 591 75365 592 75770 593 76120 594 76490 595 76880 596 77290 597 77645 598 78020 599 78415 600 78831 601 79190 602 79570 603 79971 604 80391 605 80756 606 81141 607 81546 608 81973 609 82342 610 82732 611 83143 612 83574 613 83949 614 84344 615 84760 616 85197 617 85576 618 85977 619 86398 620 86840 621 87225 622 87630 623 88057 624 88505 625 88894 626 89305 627 89737 628 90190 629 90585 630 91001 631 91438 632 91897 633 92297 634 92718 635 93161 636 93625 637 94030 638 94457 639 94905 640 95375 641 95785 642 96217 643 96671 644 97146 645 97562 646 97999 647 98458 648 98940 649 99360 650 99803 651 100268 652 100754 653 101181 654 101629 655 102099 656 102592 657 103023 658 103477 659 103953 660 104451 661 104888 662 105347 663 105829 664 106333 665 106775 666 107240 667 107727 668 108237 669 108685 670 109155 671 109648 672 110164 673 110617 674 111093 675 111592 676 112113 677 112572 678 113054 679 113558 680 114086 681 114550 682 115037 683 115548 684 116081 685 116551 686 117044 687 117560 688 118100 689 118575 690 119074 691 119596 692 120141 693 120623 694 121127 695 121655 696 122207 697 122693 698 123204 699 123738 700 124295 701 124788 702 125304 703 125844 704 126408 705 126906 706 127428 707 127974 708 128544 709 129048 710 129576 711 130128 712 130704 713 131214 714 131748 715 132306 716 132888 717 133404 718 133944 719 134508 720 135097 721 135618 722 136164 723 136735 724 137329 725 137857 726 138409 727 138985 728 139587 729 140120 730 140678 731 141261 732 141868 733 142408 734 142972 735 143561 736 144175 737 144720 738 145291 739 145886 740 146506 741 147058 742 147634 743 148236 744 148863 745 149420 746 150003 747 150611 748 151244 749 151808 750 152397 751 153011 752 153651 753 154221 754 154816 755 155437 756 156083 757 156659 758 157261 759 157888 760 158541 761 159123 762 159731 763 160365 764 161024 765 161613 766 162227 767 162867 768 163534 769 164128 770 164749 771 165396 772 166068 773 166670 774 167297 775 167950 776 168630 777 169237 778 169871 779 170531 780 171217 781 171831 782 172471 783 173138 784 173831 785 174451 786 175098 787 175771 788 176471 789 177098 790 177751 791 178431 792 179138 793 179771 794 180431 795 181118 796 181831 797 182471 798 183138 799 183831 800 184552 801 185198 802 185871 803 186572 804 187299 805 187952 806 188632 807 189339 808 190074 809 190733 810 191420 811 192134 812 192875 813 193542 814 194235 815 194956 816 195705 817 196377 818 197078 819 197806 820 198561 821 199241 822 199948 823 200683 824 201446 825 202132 826 202846 827 203588 828 204358 829 205051 830 205772 831 206521 832 207298 833 207998 834 208726 835 209482 836 210266 837 210973 838 211708 839 212471 840 213263 841 213976 842 214718 843 215489 844 216287 845 217008 846 217757 847 218534 848 219341 849 220068 850 220824 851 221609 852 222422 853 223157 854 223920 855 224712 856 225533 857 226274 858 227045 859 227844 860 228672 861 229421 862 230198 863 231005 864 231841 865 232596 866 233381 867 234195 868 235038 869 235801 870 236593 871 237414 872 238265 873 239035 874 239834 875 240663 876 241521 877 242298 878 243105 879 243941 880 244807 881 245591 882 246405 883 247249 884 248122 885 248914 886 249735 887 250586 888 251468 889 252266 890 253095 891 253954 892 254842 893 255649 894 256485 895 257351 896 258248 897 259061 898 259905 899 260779 900 261683 901 262504 902 263355 903 264237 904 265149 905 265977 906 266836 907 267725 908 268645 909 269481 910 270347 911 271244 912 272172 913 273015 914 273889 915 274794 916 275729 917 276580 918 277462 919 278374 920 279318 921 280176 922 281065 923 281986 924 282937 925 283803 926 284700 927 285628 928 286588 929 287461 930 288366 931 289302 932 290269 933 291151 934 292063 935 293007 936 293983 937 294871 938 295792 939 296744 940 297727 941 298624 942 299552 943 300512 944 301504 945 302408 946 303344 947 304312 948 305312 949 306224 950 307168 951 308144 952 309152 953 310072 954 311024 955 312008 956 313024 957 313952 958 314912 959 315904 960 316929 961 317864 962 318832 963 319833 964 320865 965 321809 966 322785 967 323793 968 324835 969 325786 970 326770 971 327787 972 328836 973 329796 974 330788 975 331813 976 332871 977 333838 978 334839 979 335872 980 336938 981 337914 982 338922 983 339964 984 341039 985 342022 986 343039 987 344089 988 345172 989 346164 990 347189 991 348247 992 349339 993 350339 994 351372 995 352439 996 353539 997 354547 998 355589 999 356664 1000 357773