0 1 1 0 2 0 3 1 4 1 5 1 6 1 7 1 8 2 9 2 10 2 11 2 12 4 13 3 14 3 15 5 16 5 17 5 18 6 19 6 20 8 21 8 22 8 23 9 24 12 25 11 26 11 27 14 28 15 29 15 30 17 31 17 32 20 33 21 34 21 35 23 36 27 37 26 38 27 39 31 40 33 41 33 42 36 43 37 44 41 45 43 46 43 47 46 48 52 49 51 50 53 51 58 52 61 53 62 54 66 55 68 56 73 57 76 58 77 59 81 60 89 61 88 62 91 63 98 64 102 65 104 66 109 67 112 68 119 69 123 70 125 71 130 72 140 73 140 74 144 75 153 76 158 77 161 78 168 79 172 80 181 81 186 82 189 83 196 84 208 85 209 86 214 87 225 88 232 89 236 90 245 91 250 92 261 93 268 94 272 95 281 96 295 97 297 98 304 99 317 100 326 101 331 102 342 103 349 104 362 105 371 106 376 107 387 108 404 109 407 110 416 111 431 112 442 113 449 114 462 115 471 116 486 117 497 118 504 119 517 120 537 121 541 122 552 123 570 124 583 125 592 126 607 127 618 128 636 129 649 130 658 131 673 132 696 133 702 134 715 135 736 136 751 137 762 138 780 139 793 140 814 141 829 142 840 143 858 144 884 145 892 146 907 147 931 148 949 149 962 150 983 151 998 152 1022 153 1040 154 1053 155 1074 156 1103 157 1113 158 1131 159 1158 160 1179 161 1194 162 1218 163 1236 164 1263 165 1284 166 1299 167 1323 168 1356 169 1368 170 1389 171 1419 172 1443 173 1461 174 1488 175 1509 176 1539 177 1563 178 1581 179 1608 180 1645 181 1659 182 1683 183 1717 184 1744 185 1765 186 1795 187 1819 188 1853 189 1880 190 1901 191 1931 192 1972 193 1989 194 2016 195 2054 196 2084 197 2108 198 2142 199 2169 200 2207 201 2237 202 2261 203 2295 204 2340 205 2360 206 2390 207 2432 208 2466 209 2493 210 2531 211 2561 212 2603 213 2637 214 2664 215 2702 216 2751 217 2774 218 2808 219 2854 220 2892 221 2922 222 2964 223 2998 224 3044 225 3082 226 3112 227 3154 228 3208 229 3234 230 3272 231 3322 232 3364 233 3398 234 3444 235 3482 236 3532 237 3574 238 3608 239 3654 240 3713 241 3742 242 3784 243 3839 244 3885 245 3923 246 3973 247 4015 248 4070 249 4116 250 4154 251 4204 252 4268 253 4301 254 4347 255 4407 256 4457 257 4499 258 4554 259 4600 260 4660 261 4710 262 4752 263 4807 264 4876 265 4913 266 4963 267 5028 268 5083 269 5129 270 5189 271 5239 272 5304 273 5359 274 5405 275 5465 276 5539 277 5580 278 5635 279 5705 280 5765 281 5815 282 5880 283 5935 284 6005 285 6065 286 6115 287 6180 288 6260 289 6305 290 6365 291 6440 292 6505 293 6560 294 6630 295 6690 296 6765 297 6830 298 6885 299 6955 300 7041 301 7090 302 7155 303 7236 304 7306 305 7366 306 7441 307 7506 308 7587 309 7657 310 7717 311 7792 312 7884 313 7938 314 8008 315 8095 316 8170 317 8235 318 8316 319 8386 320 8473 321 8548 322 8613 323 8694 324 8792 325 8851 326 8926 327 9019 328 9100 329 9170 330 9257 331 9332 332 9425 333 9506 334 9576 335 9663 336 9767 337 9831 338 9912 339 10011 340 10098 341 10173 342 10266 343 10347 344 10446 345 10533 346 10608 347 10701 348 10812 349 10881 350 10968 351 11073 352 11166 353 11247 354 11346 355 11433 356 11538 357 11631 358 11712 359 11811 360 11929 361 12003 362 12096 363 12208 364 12307 365 12394 366 12499 367 12592 368 12704 369 12803 370 12890 371 12995 372 13120 373 13200 374 13299 375 13418 376 13523 377 13616 378 13728 379 13827 380 13946 381 14051 382 14144 383 14256 384 14388 385 14474 386 14579 387 14705 388 14817 389 14916 390 15035 391 15140 392 15266 393 15378 394 15477 395 15596 396 15735 397 15827 398 15939 399 16072 400 16191 401 16296 402 16422 403 16534 404 16667 405 16786 406 16891 407 17017 408 17164 409 17262 410 17381 411 17521 412 17647 413 17759 414 17892 415 18011 416 18151 417 18277 418 18389 419 18522 420 18677 421 18781 422 18907 423 19055 424 19188 425 19307 426 19447 427 19573 428 19721 429 19854 430 19973 431 20113 432 20276 433 20387 434 20520 435 20676 436 20816 437 20942 438 21090 439 21223 440 21379 441 21519 442 21645 443 21793 444 21964 445 22082 446 22222 447 22386 448 22534 449 22667 450 22823 451 22963 452 23127 453 23275 454 23408 455 23564 456 23743 457 23868 458 24016 459 24188 460 24344 461 24484 462 24648 463 24796 464 24968 465 25124 466 25264 467 25428 468 25616 469 25748 470 25904 471 26084 472 26248 473 26396 474 26568 475 26724 476 26904 477 27068 478 27216 479 27388 480 27585 481 27724 482 27888 483 28077 484 28249 485 28405 486 28585 487 28749 488 28938 489 29110 490 29266 491 29446 492 29652 493 29799 494 29971 495 30169 496 30349 497 30513 498 30702 499 30874 500 31072 501 31252 502 31416 503 31605 504 31820 505 31975 506 32155 507 32362 508 32551 509 32723 510 32921 511 33101 512 33308 513 33497 514 33669 515 33867 516 34091 517 34254 518 34443 519 34659 520 34857 521 35037 522 35244 523 35433 524 35649 525 35847 526 36027 527 36234 528 36468 529 36639 530 36837 531 37062 532 37269 533 37458 534 37674 535 37872 536 38097 537 38304 538 38493 539 38709 540 38953 541 39132 542 39339 543 39574 544 39790 545 39988 546 40213 547 40420 548 40655 549 40871 550 41069 551 41294 552 41548 553 41736 554 41952 555 42197 556 42422 557 42629 558 42864 559 43080 560 43325 561 43550 562 43757 563 43992 564 44256 565 44453 566 44678 567 44933 568 45168 569 45384 570 45629 571 45854 572 46109 573 46344 574 46560 575 46805 576 47079 577 47285 578 47520 579 47785 580 48030 581 48255 582 48510 583 48745 584 49010 585 49255 586 49480 587 49735 588 50020 589 50235 590 50480 591 50755 592 51010 593 51245 594 51510 595 51755 596 52030 597 52285 598 52520 599 52785 600 53081 601 53305 602 53560 603 53846 604 54111 605 54356 606 54631 607 54886 608 55172 609 55437 610 55682 611 55957 612 56264 613 56498 614 56763 615 57060 616 57335 617 57590 618 57876 619 58141 620 58438 621 58713 622 58968 623 59254 624 59572 625 59816 626 60091 627 60399 628 60685 629 60950 630 61247 631 61522 632 61830 633 62116 634 62381 635 62678 636 63007 637 63261 638 63547 639 63866 640 64163 641 64438 642 64746 643 65032 644 65351 645 65648 646 65923 647 66231 648 66572 649 66836 650 67133 651 67463 652 67771 653 68057 654 68376 655 68673 656 69003 657 69311 658 69597 659 69916 660 70269 661 70543 662 70851 663 71193 664 71512 665 71809 666 72139 667 72447 668 72789 669 73108 670 73405 671 73735 672 74100 673 74385 674 74704 675 75058 676 75388 677 75696 678 76038 679 76357 680 76711 681 77041 682 77349 683 77691 684 78068 685 78364 686 78694 687 79060 688 79402 689 79721 690 80075 691 80405 692 80771 693 81113 694 81432 695 81786 696 82175 697 82482 698 82824 699 83202 700 83556 701 83886 702 84252 703 84594 704 84972 705 85326 706 85656 707 86022 708 86424 709 86742 710 87096 711 87486 712 87852 713 88194 714 88572 715 88926 716 89316 717 89682 718 90024 719 90402 720 90817 721 91146 722 91512 723 91915 724 92293 725 92647 726 93037 727 93403 728 93806 729 94184 730 94538 731 94928 732 95356 733 95697 734 96075 735 96491 736 96881 737 97247 738 97650 739 98028 740 98444 741 98834 742 99200 743 99603 744 100044 745 100397 746 100787 747 101216 748 101619 749 101997 750 102413 751 102803 752 103232 753 103635 754 104013 755 104429 756 104883 757 105248 758 105651 759 106093 760 106509 761 106899 762 107328 763 107731 764 108173 765 108589 766 108979 767 109408 768 109876 769 110253 770 110669 771 111124 772 111553 773 111956 774 112398 775 112814 776 113269 777 113698 778 114101 779 114543 780 115025 781 115414 782 115843 783 116312 784 116754 785 117170 786 117625 787 118054 788 118523 789 118965 790 119381 791 119836 792 120332 793 120734 794 121176 795 121659 796 122114 797 122543 798 123012 799 123454 800 123937 801 124392 802 124821 803 125290 804 125800 805 126215 806 126670 807 127167 808 127636 809 128078 810 128561 811 129016 812 129513 813 129982 814 130424 815 130907 816 131431 817 131859 818 132328 819 132839 820 133322 821 133777 822 134274 823 134743 824 135254 825 135737 826 136192 827 136689 828 137228 829 137669 830 138152 831 138677 832 139174 833 139643 834 140154 835 140637 836 141162 837 141659 838 142128 839 142639 840 143193 841 143647 842 144144 843 144684 844 145195 845 145678 846 146203 847 146700 848 147240 849 147751 850 148234 851 148759 852 149328 853 149796 854 150307 855 150862 856 151387 857 151884 858 152424 859 152935 860 153490 861 154015 862 154512 863 155052 864 155636 865 156118 866 156643 867 157213 868 157753 869 158264 870 158819 871 159344 872 159914 873 160454 874 160965 875 161520 876 162119 877 162615 878 163155 879 163740 880 164295 881 164820 882 165390 883 165930 884 166515 885 167070 886 167595 887 168165 888 168780 889 169290 890 169845 891 170445 892 171015 893 171555 894 172140 895 172695 896 173295 897 173865 898 174405 899 174990 900 175621 901 176145 902 176715 903 177331 904 177916 905 178471 906 179071 907 179641 908 180257 909 180842 910 181397 911 181997 912 182644 913 183183 914 183768 915 184400 916 185000 917 185570 918 186186 919 186771 920 187403 921 188003 922 188573 923 189189 924 189852 925 190406 926 191006 927 191654 928 192270 929 192855 930 193487 931 194087 932 194735 933 195351 934 195936 935 196568 936 197247 937 197816 938 198432 939 199096 940 199728 941 200328 942 200976 943 201592 944 202256 945 202888 946 203488 947 204136 948 204832 949 205416 950 206048 951 206728 952 207376 953 207992 954 208656 955 209288 956 209968 957 210616 958 211232 959 211896 960 212609 961 213208 962 213856 963 214553 964 215217 965 215849 966 216529 967 217177 968 217874 969 218538 970 219170 971 219850 972 220580 973 221195 974 221859 975 222573 976 223253 977 223901 978 224598 979 225262 980 225976 981 226656 982 227304 983 228001 984 228748 985 229379 986 230059 987 230790 988 231487 989 232151 990 232865 991 233545 992 234276 993 234973 994 235637 995 236351 996 237115 997 237762 998 238459 999 239207 1000 239921