0 1 1 0 2 0 3 0 4 1 5 1 6 0 7 0 8 2 9 2 10 1 11 0 12 2 13 3 14 2 15 1 16 3 17 4 18 4 19 2 20 4 21 5 22 5 23 4 24 6 25 7 26 7 27 6 28 8 29 9 30 9 31 8 32 11 33 12 34 12 35 11 36 14 37 15 38 15 39 14 40 18 41 19 42 19 43 18 44 22 45 24 46 23 47 22 48 27 49 29 50 29 51 27 52 32 53 35 54 35 55 33 56 38 57 41 58 42 59 40 60 45 61 48 62 49 63 48 64 53 65 56 66 57 67 56 68 62 69 65 70 66 71 65 72 72 73 75 74 76 75 75 76 82 77 86 78 87 79 86 80 94 81 98 82 99 83 98 84 106 85 111 86 112 87 111 88 120 89 125 90 127 91 125 92 134 93 140 94 142 95 141 96 150 97 156 98 159 99 158 100 167 101 173 102 176 103 176 104 186 105 192 106 195 107 195 108 206 109 212 110 215 111 215 112 227 113 234 114 237 115 237 116 249 117 257 118 260 119 260 120 273 121 281 122 285 123 285 124 298 125 307 126 311 127 311 128 325 129 334 130 339 131 339 132 353 133 363 134 368 135 369 136 383 137 393 138 399 139 400 140 415 141 425 142 431 143 433 144 449 145 459 146 465 147 467 148 484 149 495 150 501 151 503 152 521 153 533 154 539 155 541 156 559 157 572 158 579 159 581 160 600 161 613 162 621 163 623 164 642 165 656 166 664 167 667 168 687 169 701 170 710 171 713 172 733 173 748 174 757 175 761 176 782 177 797 178 807 179 811 180 833 181 848 182 858 183 863 184 886 185 902 186 912 187 917 188 941 189 958 190 968 191 973 192 998 193 1016 194 1027 195 1032 196 1057 197 1076 198 1088 199 1093 200 1119 201 1138 202 1151 203 1157 204 1183 205 1203 206 1216 207 1223 208 1250 209 1270 210 1284 211 1291 212 1319 213 1340 214 1354 215 1362 216 1391 217 1412 218 1427 219 1435 220 1465 221 1487 222 1502 223 1511 224 1542 225 1565 226 1580 227 1589 228 1621 229 1645 230 1661 231 1670 232 1703 233 1728 234 1745 235 1754 236 1787 237 1813 238 1831 239 1841 240 1875 241 1901 242 1920 243 1931 244 1965 245 1992 246 2011 247 2023 248 2059 249 2086 250 2106 251 2118 252 2155 253 2183 254 2203 255 2216 256 2254 257 2283 258 2304 259 2317 260 2356 261 2386 262 2407 263 2421 264 2461 265 2492 266 2514 267 2528 268 2569 269 2601 270 2624 271 2638 272 2680 273 2713 274 2737 275 2752 276 2794 277 2828 278 2853 279 2869 280 2912 281 2946 282 2972 283 2989 284 3033 285 3068 286 3094 287 3112 288 3158 289 3193 290 3220 291 3238 292 3285 293 3322 294 3349 295 3368 296 3416 297 3454 298 3482 299 3501 300 3550 301 3589 302 3618 303 3638 304 3688 305 3728 306 3758 307 3778 308 3829 309 3870 310 3901 311 3922 312 3974 313 4016 314 4048 315 4070 316 4122 317 4165 318 4198 319 4221 320 4275 321 4318 322 4352 323 4376 324 4431 325 4475 326 4509 327 4534 328 4591 329 4636 330 4671 331 4696 332 4754 333 4801 334 4836 335 4862 336 4921 337 4969 338 5006 339 5032 340 5092 341 5141 342 5179 343 5206 344 5267 345 5317 346 5356 347 5384 348 5446 349 5497 350 5537 351 5566 352 5629 353 5681 354 5722 355 5752 356 5816 357 5869 358 5911 359 5942 360 6008 361 6061 362 6104 363 6136 364 6203 365 6258 366 6301 367 6334 368 6403 369 6459 370 6503 371 6536 372 6606 373 6664 374 6709 375 6743 376 6814 377 6873 378 6920 379 6954 380 7026 381 7086 382 7134 383 7170 384 7243 385 7304 386 7353 387 7390 388 7464 389 7526 390 7576 391 7614 392 7690 393 7753 394 7804 395 7843 396 7920 397 7984 398 8036 399 8076 400 8155 401 8220 402 8273 403 8314 404 8394 405 8461 406 8514 407 8556 408 8638 409 8706 410 8761 411 8803 412 8886 413 8956 414 9012 415 9055 416 9139 417 9210 418 9268 419 9312 420 9397 421 9469 422 9528 423 9574 424 9660 425 9733 426 9793 427 9840 428 9928 429 10002 430 10063 431 10111 432 10201 433 10276 434 10338 435 10387 436 10478 437 10555 438 10618 439 10668 440 10761 441 10839 442 10903 443 10954 444 11048 445 11128 446 11193 447 11245 448 11341 449 11422 450 11489 451 11541 452 11638 453 11721 454 11789 455 11843 456 11941 457 12025 458 12095 459 12150 460 12249 461 12334 462 12405 463 12462 464 12563 465 12649 466 12721 467 12779 468 12882 469 12969 470 13042 471 13101 472 13206 473 13295 474 13369 475 13429 476 13535 477 13626 478 13701 479 13762 480 13870 481 13962 482 14039 483 14101 484 14210 485 14304 486 14382 487 14445 488 14556 489 14651 490 14731 491 14795 492 14907 493 15004 494 15085 495 15151 496 15264 497 15362 498 15445 499 15512 500 15627 501 15726 502 15810 503 15879 504 15996 505 16096 506 16181 507 16251 508 16370 509 16472 510 16558 511 16629 512 16750 513 16854 514 16941 515 17013 516 17135 517 17241 518 17330 519 17403 520 17527 521 17634 522 17725 523 17799 524 17924 525 18033 526 18125 527 18201 528 18328 529 18438 530 18532 531 18609 532 18737 533 18849 534 18944 535 19023 536 19153 537 19266 538 19363 539 19443 540 19575 541 19689 542 19787 543 19869 544 20003 545 20119 546 20218 547 20301 548 20437 549 20555 550 20655 551 20739 552 20877 553 20997 554 21099 555 21184 556 21323 557 21445 558 21549 559 21635 560 21776 561 21899 562 22005 563 22093 564 22235 565 22360 566 22467 567 22557 568 22701 569 22827 570 22936 571 23027 572 23173 573 23301 574 23411 575 23504 576 23652 577 23781 578 23893 579 23987 580 24137 581 24268 582 24381 583 24477 584 24629 585 24762 586 24876 587 24973 588 25127 589 25262 590 25378 591 25476 592 25632 593 25769 594 25887 595 25986 596 26143 597 26282 598 26402 599 26503 600 26662 601 26802 602 26924 603 27027 604 27187 605 27329 606 27452 607 27557 608 27720 609 27863 610 27988 611 28094 612 28259 613 28404 614 28530 615 28638 616 28805 617 28952 618 29080 619 29189 620 29358 621 29507 622 29636 623 29747 624 29918 625 30069 626 30200 627 30312 628 30485 629 30638 630 30771 631 30884 632 31059 633 31214 634 31349 635 31464 636 31640 637 31797 638 31934 639 32051 640 32229 641 32387 642 32526 643 32645 644 32825 645 32985 646 33125 647 33246 648 33429 649 33590 650 33732 651 33854 652 34039 653 34203 654 34346 655 34470 656 34657 657 34823 658 34968 659 35093 660 35282 661 35450 662 35597 663 35724 664 35915 665 36085 666 36234 667 36362 668 36555 669 36727 670 36878 671 37008 672 37203 673 37377 674 37530 675 37662 676 37858 677 38034 678 38189 679 38323 680 38522 681 38699 682 38856 683 38992 684 39193 685 39372 686 39530 687 39668 688 39872 689 40053 690 40213 691 40352 692 40558 693 40742 694 40903 695 41044 696 41252 697 41438 698 41602 699 41744 700 41954 701 42142 702 42308 703 42452 704 42664 705 42854 706 43022 707 43168 708 43382 709 43574 710 43744 711 43892 712 44108 713 44302 714 44474 715 44624 716 44842 717 45038 718 45212 719 45364 720 45585 721 45782 722 45958 723 46112 724 46335 725 46535 726 46712 727 46868 728 47094 729 47296 730 47475 731 47632 732 47860 733 48065 734 48246 735 48405 736 48635 737 48842 738 49026 739 49186 740 49418 741 49627 742 49813 743 49976 744 50210 745 50421 746 50609 747 50774 748 51010 749 51223 750 51413 751 51580 752 51819 753 52034 754 52226 755 52395 756 52636 757 52853 758 53047 759 53218 760 53462 761 53681 762 53877 763 54050 764 54296 765 54518 766 54715 767 54890 768 55139 769 55363 770 55563 771 55739 772 55990 773 56217 774 56419 775 56597 776 56850 777 57079 778 57284 779 57464 780 57719 781 57950 782 58157 783 58340 784 58597 785 58830 786 59039 787 59224 788 59484 789 59719 790 59930 791 60117 792 60380 793 60617 794 60830 795 61019 796 61284 797 61524 798 61739 799 61930 800 62198 801 62440 802 62657 803 62850 804 63120 805 63365 806 63584 807 63779 808 64052 809 64299 810 64521 811 64717 812 64992 813 65242 814 65466 815 65665 816 65942 817 66194 818 66421 819 66622 820 66901 821 67155 822 67384 823 67588 824 67870 825 68126 826 68357 827 68563 828 68848 829 69106 830 69339 831 69547 832 69835 833 70096 834 70331 835 70541 836 70831 837 71095 838 71332 839 71544 840 71837 841 72103 842 72343 843 72557 844 72852 845 73121 846 73363 847 73579 848 73877 849 74148 850 74393 851 74611 852 74911 853 75185 854 75432 855 75653 856 75955 857 76231 858 76481 859 76704 860 77009 861 77287 862 77539 863 77765 864 78073 865 78353 866 78607 867 78835 868 79146 869 79429 870 79685 871 79915 872 80229 873 80515 874 80773 875 81005 876 81321 877 81610 878 81871 879 82105 880 82424 881 82715 882 82979 883 83215 884 83536 885 83830 886 84096 887 84335 888 84659 889 84955 890 85224 891 85465 892 85791 893 86090 894 86361 895 86605 896 86934 897 87235 898 87509 899 87755 900 88087 901 88390 902 88666 903 88915 904 89250 905 89556 906 89834 907 90085 908 90423 909 90732 910 91012 911 91265 912 91606 913 91918 914 92201 915 92456 916 92799 917 93114 918 93400 919 93657 920 94003 921 94320 922 94609 923 94869 924 95217 925 95537 926 95828 927 96091 928 96442 929 96764 930 97058 931 97323 932 97677 933 98002 934 98298 935 98566 936 98923 937 99250 938 99549 939 99819 940 100179 941 100509 942 100810 943 101083 944 101446 945 101779 946 102082 947 102357 948 102723 949 103059 950 103365 951 103642 952 104011 953 104350 954 104659 955 104938 956 105309 957 105651 958 105963 959 106245 960 106619 961 106963 962 107278 963 107563 964 107939 965 108286 966 108603 967 108891 968 109271 969 109620 970 109940 971 110230 972 110613 973 110965 974 111287 975 111580 976 111966 977 112321 978 112646 979 112941 980 113330 981 113688 982 114015 983 114313 984 114705 985 115066 986 115396 987 115696 988 116091 989 116455 990 116788 991 117090 992 117488 993 117855 994 118191 995 118496 996 118896 997 119266 998 119605 999 119913 1000 120316