0 1 1 0 2 0 3 1 4 0 5 1 6 1 7 0 8 1 9 1 10 2 11 2 12 1 13 2 14 2 15 3 16 3 17 2 18 3 19 3 20 5 21 5 22 4 23 5 24 5 25 7 26 7 27 6 28 7 29 7 30 10 31 10 32 9 33 11 34 10 35 13 36 14 37 12 38 14 39 14 40 17 41 18 42 17 43 19 44 19 45 22 46 23 47 22 48 24 49 24 50 28 51 29 52 28 53 31 54 31 55 35 56 36 57 35 58 38 59 38 60 43 61 44 62 43 63 47 64 47 65 52 66 54 67 52 68 56 69 57 70 62 71 64 72 63 73 67 74 68 75 74 76 76 77 75 78 79 79 80 80 87 81 89 82 88 83 93 84 94 85 101 86 104 87 103 88 108 89 109 90 117 91 120 92 119 93 125 94 126 95 134 96 138 97 137 98 143 99 145 100 153 101 157 102 157 103 163 104 165 105 174 106 178 107 178 108 185 109 187 110 197 111 201 112 201 113 209 114 211 115 221 116 226 117 226 118 234 119 237 120 248 121 253 122 253 123 262 124 265 125 276 126 282 127 282 128 291 129 295 130 307 131 313 132 314 133 323 134 327 135 340 136 346 137 347 138 357 139 361 140 375 141 382 142 383 143 394 144 398 145 412 146 420 147 421 148 432 149 437 150 452 151 460 152 462 153 474 154 479 155 494 156 503 157 505 158 517 159 523 160 539 161 548 162 551 163 564 164 570 165 587 166 596 167 599 168 613 169 619 170 637 171 647 172 650 173 665 174 672 175 690 176 701 177 704 178 719 179 727 180 746 181 757 182 761 183 777 184 785 185 805 186 817 187 821 188 837 189 846 190 867 191 879 192 884 193 901 194 910 195 932 196 945 197 950 198 968 199 977 200 1000 201 1014 202 1019 203 1038 204 1048 205 1071 206 1086 207 1092 208 1111 209 1122 210 1146 211 1161 212 1168 213 1188 214 1199 215 1224 216 1240 217 1247 218 1268 219 1280 220 1306 221 1322 222 1330 223 1352 224 1364 225 1391 226 1408 227 1416 228 1439 229 1452 230 1480 231 1498 232 1506 233 1530 234 1544 235 1572 236 1591 237 1600 238 1624 239 1639 240 1669 241 1688 242 1698 243 1723 244 1738 245 1769 246 1789 247 1799 248 1825 249 1841 250 1873 251 1894 252 1905 253 1932 254 1948 255 1981 256 2003 257 2014 258 2042 259 2059 260 2093 261 2116 262 2128 263 2157 264 2175 265 2209 266 2233 267 2246 268 2275 269 2294 270 2330 271 2354 272 2368 273 2399 274 2418 275 2455 276 2480 277 2494 278 2526 279 2546 280 2584 281 2610 282 2625 283 2658 284 2679 285 2718 286 2745 287 2760 288 2794 289 2816 290 2856 291 2884 292 2900 293 2935 294 2958 295 2999 296 3028 297 3045 298 3080 299 3104 300 3147 301 3176 302 3194 303 3231 304 3255 305 3299 306 3330 307 3348 308 3386 309 3411 310 3456 311 3488 312 3507 313 3546 314 3572 315 3618 316 3651 317 3671 318 3711 319 3738 320 3785 321 3819 322 3840 323 3881 324 3909 325 3957 326 3992 327 4014 328 4056 329 4085 330 4135 331 4170 332 4193 333 4237 334 4266 335 4317 336 4354 337 4377 338 4422 339 4453 340 4505 341 4543 342 4567 343 4613 344 4645 345 4698 346 4737 347 4762 348 4809 349 4842 350 4897 351 4937 352 4963 353 5011 354 5045 355 5101 356 5142 357 5169 358 5218 359 5253 360 5311 361 5353 362 5381 363 5432 364 5467 365 5526 366 5570 367 5598 368 5650 369 5687 370 5747 371 5792 372 5822 373 5875 374 5913 375 5974 376 6020 377 6051 378 6105 379 6144 380 6207 381 6254 382 6286 383 6342 384 6382 385 6446 386 6494 387 6527 388 6584 389 6625 390 6691 391 6740 392 6774 393 6833 394 6875 395 6942 396 6993 397 7027 398 7087 399 7131 400 7199 401 7251 402 7287 403 7348 404 7393 405 7463 406 7516 407 7553 408 7615 409 7661 410 7733 411 7787 412 7825 413 7889 414 7936 415 8009 416 8065 417 8104 418 8169 419 8217 420 8292 421 8349 422 8389 423 8456 424 8505 425 8581 426 8640 427 8681 428 8749 429 8800 430 8877 431 8937 432 8980 433 9049 434 9101 435 9180 436 9241 437 9285 438 9356 439 9409 440 9490 441 9552 442 9597 443 9670 444 9724 445 9806 446 9870 447 9916 448 9990 449 10046 450 10130 451 10195 452 10242 453 10318 454 10375 455 10460 456 10527 457 10575 458 10652 459 10711 460 10798 461 10866 462 10916 463 10994 464 11054 465 11143 466 11212 467 11263 468 11343 469 11404 470 11495 471 11566 472 11618 473 11700 474 11762 475 11854 476 11927 477 11980 478 12063 479 12127 480 12221 481 12295 482 12350 483 12435 484 12500 485 12595 486 12671 487 12727 488 12813 489 12880 490 12977 491 13054 492 13112 493 13200 494 13268 495 13367 496 13445 497 13504 498 13594 499 13663 500 13764 501 13844 502 13904 503 13996 504 14067 505 14169 506 14251 507 14312 508 14405 509 14478 510 14582 511 14665 512 14728 513 14823 514 14897 515 15003 516 15088 517 15152 518 15248 519 15324 520 15432 521 15518 522 15584 523 15682 524 15759 525 15869 526 15957 527 16024 528 16124 529 16202 530 16314 531 16404 532 16472 533 16574 534 16654 535 16767 536 16859 537 16929 538 17032 539 17114 540 17229 541 17322 542 17394 543 17499 544 17582 545 17699 546 17794 547 17867 548 17974 549 18059 550 18178 551 18274 552 18349 553 18458 554 18544 555 18665 556 18763 557 18839 558 18950 559 19038 560 19161 561 19261 562 19338 563 19451 564 19541 565 19665 566 19767 567 19846 568 19960 569 20052 570 20179 571 20282 572 20363 573 20479 574 20572 575 20701 576 20806 577 20888 578 21006 579 21101 580 21232 581 21339 582 21423 583 21543 584 21639 585 21772 586 21881 587 21966 588 22088 589 22186 590 22321 591 22432 592 22519 593 22643 594 22743 595 22879 596 22992 597 23081 598 23206 599 23308 600 23447 601 23561 602 23652 603 23780 604 23883 605 24024 606 24140 607 24232 608 24362 609 24467 610 24610 611 24728 612 24822 613 24954 614 25061 615 25206 616 25326 617 25421 618 25555 619 25664 620 25811 621 25933 622 26030 623 26166 624 26277 625 26426 626 26550 627 26649 628 26786 629 26899 630 27051 631 27176 632 27277 633 27417 634 27531 635 27685 636 27813 637 27915 638 28057 639 28173 640 28329 641 28459 642 28563 643 28707 644 28825 645 28983 646 29115 647 29221 648 29367 649 29487 650 29647 651 29781 652 29889 653 30037 654 30159 655 30321 656 30457 657 30567 658 30717 659 30841 660 31006 661 31143 662 31255 663 31408 664 31533 665 31700 666 31840 667 31953 668 32108 669 32236 670 32405 671 32547 672 32662 673 32819 674 32949 675 33120 676 33264 677 33381 678 33540 679 33672 680 33846 681 33992 682 34111 683 34272 684 34406 685 34582 686 34730 687 34851 688 35014 689 35150 690 35329 691 35479 692 35602 693 35768 694 35905 695 36086 696 36239 697 36363 698 36531 699 36671 700 36854 701 37009 702 37136 703 37306 704 37448 705 37633 706 37790 707 37919 708 38091 709 38235 710 38423 711 38582 712 38713 713 38888 714 39034 715 39224 716 39385 717 39518 718 39695 719 39843 720 40036 721 40199 722 40334 723 40514 724 40664 725 40859 726 41025 727 41161 728 41343 729 41496 730 41693 731 41861 732 42000 733 42184 734 42339 735 42539 736 42709 737 42850 738 43036 739 43193 740 43396 741 43568 742 43711 743 43900 744 44059 745 44264 746 44439 747 44584 748 44775 749 44936 750 45144 751 45321 752 45468 753 45662 754 45825 755 46035 756 46215 757 46364 758 46560 759 46726 760 46938 761 47120 762 47272 763 47470 764 47638 765 47853 766 48037 767 48191 768 48392 769 48562 770 48780 771 48966 772 49122 773 49326 774 49498 775 49718 776 49907 777 50065 778 50271 779 50446 780 50669 781 50860 782 51020 783 51229 784 51406 785 51631 786 51825 787 51987 788 52198 789 52378 790 52606 791 52802 792 52967 793 53180 794 53362 795 53593 796 53791 797 53958 798 54174 799 54358 800 54592 801 54793 802 54962 803 55181 804 55367 805 55603 806 55807 807 55978 808 56199 809 56388 810 56627 811 56833 812 57007 813 57231 814 57422 815 57663 816 57872 817 58048 818 58274 819 58468 820 58712 821 58923 822 59102 823 59331 824 59527 825 59774 826 59987 827 60168 828 60400 829 60598 830 60848 831 61064 832 61247 833 61482 834 61683 835 61935 836 62154 837 62339 838 62576 839 62780 840 63035 841 63256 842 63444 843 63684 844 63890 845 64148 846 64372 847 64562 848 64804 849 65013 850 65274 851 65500 852 65693 853 65938 854 66149 855 66413 856 66642 857 66837 858 67085 859 67298 860 67565 861 67797 862 67994 863 68245 864 68461 865 68730 866 68965 867 69165 868 69418 869 69637 870 69909 871 70146 872 70349 873 70605 874 70826 875 71101 876 71341 877 71546 878 71805 879 72029 880 72307 881 72549 882 72757 883 73019 884 73245 885 73526 886 73771 887 73981 888 74246 889 74475 890 74759 891 75007 892 75219 893 75487 894 75719 895 76005 896 76256 897 76471 898 76741 899 76976 900 77266 901 77519 902 77737 903 78010 904 78247 905 78540 906 78796 907 79016 908 79292 909 79532 910 79828 911 80087 912 80310 913 80589 914 80831 915 81130 916 81392 917 81617 918 81899 919 82144 920 82446 921 82711 922 82939 923 83224 924 83472 925 83776 926 84044 927 84275 928 84562 929 84813 930 85121 931 85391 932 85625 933 85916 934 86169 935 86480 936 86753 937 86989 938 87283 939 87539 940 87853 941 88129 942 88368 943 88665 944 88924 945 89241 946 89520 947 89761 948 90061 949 90323 950 90643 951 90925 952 91169 953 91472 954 91737 955 92060 956 92345 957 92592 958 92897 959 93165 960 93492 961 93779 962 94029 963 94338 964 94608 965 94938 966 95229 967 95481 968 95793 969 96066 970 96399 971 96693 972 96948 973 97263 974 97539 975 97875 976 98172 977 98430 978 98748 979 99027 980 99366 981 99666 982 99927 983 100248 984 100530 985 100872 986 101175 987 101439 988 101763 989 102048 990 102394 991 102699 992 102966 993 103294 994 103581 995 103930 996 104239 997 104508 998 104839 999 105130 1000 105482