0 1 1 0 2 0 3 0 4 0 5 0 6 0 7 1 8 1 9 0 10 0 11 1 12 1 13 0 14 1 15 1 16 1 17 0 18 1 19 2 20 1 21 1 22 2 23 2 24 2 25 1 26 2 27 2 28 2 29 2 30 3 31 3 32 3 33 3 34 3 35 4 36 4 37 3 38 4 39 4 40 5 41 4 42 5 43 6 44 6 45 5 46 6 47 7 48 7 49 6 50 7 51 8 52 8 53 7 54 9 55 10 56 10 57 9 58 10 59 11 60 11 61 10 62 12 63 13 64 13 65 12 66 14 67 15 68 15 69 14 70 16 71 17 72 17 73 16 74 18 75 19 76 19 77 19 78 21 79 22 80 22 81 21 82 23 83 24 84 25 85 24 86 26 87 27 88 28 89 27 90 29 91 31 92 31 93 30 94 32 95 34 96 35 97 33 98 36 99 38 100 38 101 37 102 40 103 42 104 42 105 41 106 44 107 46 108 46 109 45 110 49 111 50 112 51 113 50 114 53 115 55 116 55 117 55 118 58 119 60 120 61 121 60 122 63 123 65 124 66 125 65 126 69 127 71 128 72 129 71 130 74 131 77 132 78 133 77 134 81 135 83 136 84 137 83 138 87 139 90 140 91 141 90 142 94 143 97 144 98 145 97 146 101 147 104 148 105 149 104 150 109 151 112 152 113 153 112 154 117 155 120 156 121 157 120 158 125 159 128 160 129 161 129 162 134 163 137 164 138 165 138 166 143 167 146 168 148 169 147 170 152 171 155 172 157 173 157 174 162 175 166 176 168 177 167 178 172 179 176 180 178 181 177 182 183 183 187 184 189 185 188 186 194 187 199 188 200 189 200 190 206 191 210 192 212 193 211 194 218 195 222 196 224 197 224 198 231 199 235 200 237 201 237 202 243 203 248 204 250 205 250 206 257 207 261 208 264 209 264 210 271 211 276 212 278 213 278 214 285 215 290 216 293 217 293 218 300 219 305 220 308 221 308 222 316 223 321 224 324 225 324 226 331 227 337 228 340 229 340 230 348 231 354 232 357 233 357 234 365 235 371 236 374 237 374 238 383 239 389 240 392 241 392 242 401 243 407 244 410 245 411 246 420 247 426 248 429 249 430 250 439 251 445 252 449 253 450 254 459 255 465 256 469 257 470 258 479 259 486 260 490 261 491 262 500 263 507 264 512 265 512 266 522 267 529 268 533 269 534 270 544 271 552 272 556 273 557 274 567 275 575 276 579 277 580 278 591 279 598 280 603 281 604 282 615 283 623 284 627 285 629 286 640 287 648 288 653 289 654 290 665 291 673 292 678 293 680 294 692 295 700 296 705 297 707 298 718 299 727 300 732 301 734 302 746 303 754 304 760 305 762 306 774 307 783 308 789 309 791 310 803 311 812 312 818 313 820 314 832 315 842 316 848 317 850 318 863 319 873 320 879 321 881 322 894 323 904 324 910 325 912 326 926 327 936 328 942 329 945 330 959 331 969 332 975 333 978 334 992 335 1002 336 1009 337 1012 338 1026 339 1036 340 1043 341 1047 342 1061 343 1072 344 1079 345 1082 346 1096 347 1107 348 1115 349 1118 350 1133 351 1144 352 1152 353 1155 354 1170 355 1182 356 1189 357 1193 358 1208 359 1220 360 1228 361 1231 362 1247 363 1259 364 1267 365 1271 366 1287 367 1299 368 1307 369 1311 370 1327 371 1340 372 1348 373 1352 374 1369 375 1381 376 1390 377 1394 378 1411 379 1424 380 1432 381 1437 382 1454 383 1467 384 1476 385 1481 386 1498 387 1511 388 1520 389 1525 390 1543 391 1556 392 1566 393 1571 394 1588 395 1602 396 1612 397 1617 398 1635 399 1649 400 1659 401 1664 402 1682 403 1697 404 1707 405 1712 406 1731 407 1746 408 1756 409 1761 410 1780 411 1795 412 1805 413 1811 414 1831 415 1846 416 1856 417 1862 418 1882 419 1897 420 1908 421 1914 422 1934 423 1949 424 1960 425 1967 426 1987 427 2003 428 2014 429 2021 430 2041 431 2057 432 2069 433 2075 434 2096 435 2112 436 2124 437 2131 438 2152 439 2169 440 2181 441 2188 442 2209 443 2226 444 2238 445 2245 446 2267 447 2284 448 2297 449 2304 450 2326 451 2344 452 2356 453 2364 454 2386 455 2404 456 2417 457 2424 458 2447 459 2465 460 2478 461 2486 462 2510 463 2528 464 2541 465 2549 466 2572 467 2591 468 2604 469 2613 470 2637 471 2655 472 2669 473 2678 474 2702 475 2721 476 2735 477 2744 478 2768 479 2787 480 2802 481 2811 482 2835 483 2855 484 2870 485 2879 486 2904 487 2924 488 2939 489 2948 490 2973 491 2994 492 3009 493 3018 494 3044 495 3065 496 3080 497 3090 498 3116 499 3137 500 3152 501 3162 502 3189 503 3210 504 3226 505 3236 506 3263 507 3284 508 3300 509 3311 510 3338 511 3360 512 3376 513 3387 514 3414 515 3436 516 3453 517 3464 518 3492 519 3514 520 3531 521 3542 522 3570 523 3593 524 3610 525 3622 526 3650 527 3673 528 3691 529 3702 530 3731 531 3754 532 3772 533 3784 534 3813 535 3837 536 3855 537 3867 538 3896 539 3921 540 3939 541 3951 542 3981 543 4005 544 4024 545 4036 546 4067 547 4092 548 4110 549 4123 550 4154 551 4179 552 4198 553 4211 554 4242 555 4267 556 4286 557 4300 558 4332 559 4357 560 4377 561 4391 562 4422 563 4448 564 4468 565 4482 566 4514 567 4540 568 4561 569 4575 570 4607 571 4634 572 4655 573 4669 574 4702 575 4729 576 4750 577 4764 578 4797 579 4825 580 4846 581 4861 582 4895 583 4923 584 4944 585 4959 586 4993 587 5021 588 5043 589 5058 590 5093 591 5121 592 5143 593 5159 594 5194 595 5223 596 5245 597 5261 598 5296 599 5325 600 5348 601 5364 602 5400 603 5429 604 5452 605 5469 606 5505 607 5535 608 5558 609 5575 610 5611 611 5641 612 5665 613 5682 614 5719 615 5749 616 5774 617 5791 618 5828 619 5859 620 5883 621 5901 622 5938 623 5970 624 5995 625 6012 626 6050 627 6082 628 6107 629 6125 630 6164 631 6196 632 6221 633 6239 634 6278 635 6311 636 6336 637 6355 638 6395 639 6427 640 6453 641 6472 642 6512 643 6545 644 6571 645 6591 646 6631 647 6664 648 6691 649 6711 650 6751 651 6785 652 6812 653 6832 654 6873 655 6907 656 6935 657 6955 658 6996 659 7031 660 7059 661 7079 662 7121 663 7156 664 7184 665 7205 666 7247 667 7283 668 7311 669 7332 670 7375 671 7411 672 7440 673 7461 674 7504 675 7540 676 7569 677 7591 678 7635 679 7672 680 7701 681 7723 682 7767 683 7804 684 7834 685 7856 686 7901 687 7938 688 7968 689 7991 690 8036 691 8074 692 8104 693 8128 694 8173 695 8211 696 8242 697 8265 698 8311 699 8349 700 8381 701 8405 702 8451 703 8490 704 8522 705 8546 706 8592 707 8632 708 8664 709 8688 710 8735 711 8775 712 8808 713 8832 714 8880 715 8921 716 8953 717 8978 718 9026 719 9067 720 9100 721 9125 722 9174 723 9215 724 9248 725 9274 726 9324 727 9365 728 9399 729 9425 730 9474 731 9516 732 9550 733 9577 734 9627 735 9669 736 9704 737 9731 738 9781 739 9824 740 9859 741 9886 742 9937 743 9980 744 10016 745 10043 746 10094 747 10138 748 10174 749 10202 750 10254 751 10298 752 10334 753 10362 754 10414 755 10459 756 10496 757 10524 758 10577 759 10622 760 10659 761 10688 762 10741 763 10787 764 10824 765 10853 766 10907 767 10953 768 10991 769 11020 770 11075 771 11121 772 11159 773 11189 774 11244 775 11291 776 11329 777 11360 778 11415 779 11462 780 11501 781 11532 782 11588 783 11635 784 11675 785 11706 786 11762 787 11810 788 11850 789 11882 790 11938 791 11987 792 12028 793 12059 794 12116 795 12165 796 12206 797 12238 798 12296 799 12346 800 12387 801 12419 802 12477 803 12528 804 12569 805 12602 806 12661 807 12711 808 12753 809 12786 810 12846 811 12897 812 12939 813 12973 814 13033 815 13084 816 13127 817 13161 818 13221 819 13273 820 13316 821 13351 822 13412 823 13464 824 13508 825 13543 826 13604 827 13657 828 13701 829 13736 830 13798 831 13851 832 13896 833 13932 834 13994 835 14048 836 14093 837 14129 838 14192 839 14246 840 14292 841 14328 842 14391 843 14446 844 14492 845 14529 846 14593 847 14649 848 14695 849 14732 850 14796 851 14852 852 14899 853 14936 854 15002 855 15058 856 15105 857 15143 858 15209 859 15266 860 15313 861 15352 862 15418 863 15475 864 15523 865 15562 866 15629 867 15686 868 15735 869 15775 870 15842 871 15900 872 15949 873 15989 874 16056 875 16115 876 16165 877 16205 878 16273 879 16332 880 16383 881 16423 882 16492 883 16552 884 16602 885 16643 886 16712 887 16773 888 16824 889 16865 890 16935 891 16996 892 17047 893 17089 894 17160 895 17221 896 17273 897 17315 898 17386 899 17448 900 17500 901 17543 902 17615 903 17677 904 17730 905 17773 906 17845 907 17908 908 17961 909 18005 910 18078 911 18141 912 18195 913 18239 914 18312 915 18376 916 18430 917 18475 918 18549 919 18613 920 18668 921 18713 922 18787 923 18852 924 18908 925 18953 926 19028 927 19093 928 19149 929 19195 930 19270 931 19337 932 19393 933 19439 934 19515 935 19582 936 19639 937 19685 938 19762 939 19829 940 19886 941 19933 942 20011 943 20079 944 20136 945 20184 946 20262 947 20330 948 20388 949 20436 950 20515 951 20583 952 20642 953 20691 954 20770 955 20839 956 20898 957 20948 958 21027 959 21097 960 21157 961 21206 962 21286 963 21356 964 21417 965 21467 966 21548 967 21619 968 21680 969 21730 970 21811 971 21883 972 21944 973 21995 974 22077 975 22149 976 22211 977 22262 978 22345 979 22418 980 22480 981 22532 982 22615 983 22688 984 22751 985 22803 986 22887 987 22961 988 23024 989 23077 990 23162 991 23236 992 23300 993 23353 994 23438 995 23513 996 23577 997 23631 998 23717 999 23792 1000 23857