0 1 1 1 2 2 3 5 4 6 5 7 6 5 7 22 8 9 9 15 10 28 11 33 12 31 13 37 14 43 15 50 16 32 17 63 18 58 19 50 20 55 21 78 22 69 23 64 24 105 25 94 26 91 27 118 28 104 29 101 30 96 31 121 32 122 33 139 34 141 35 102 36 163 37 150 38 154 39 172 40 145 41 164 42 185 43 186 44 187 45 194 46 184 47 153 48 186 49 172 50 231 51 211 52 226 53 196 54 230 55 266 56 243 57 247 58 248 59 280 60 312 61 285 62 262 63 258 64 310 65 325 66 343 67 293 68 335 69 339 70 328 71 320 72 355 73 330 74 327 75 379 76 366 77 433 78 379 79 316 80 434 81 410 82 411 83 430 84 437 85 409 86 432 87 411 88 415 89 465 90 409 91 451 92 457 93 482 94 428 95 414 96 517 97 500 98 496 99 474 100 564 101 568 102 546 103 544 104 541 105 577 106 536 107 542 108 609 109 562 110 581 111 580 112 582 113 579 114 622 115 582 116 622 117 622 118 622 119 668 120 707 121 681 122 646 123 626 124 688 125 747 126 681 127 721 128 663 129 706 130 658 131 727 132 725 133 797 134 720 135 760 136 779 137 829 138 780 139 834 140 793 141 807 142 760 143 793 144 820 145 833 146 839 147 816 148 859 149 869 150 832 151 933 152 894 153 919 154 915 155 955 156 892 157 874 158 956 159 941 160 942 161 916 162 977 163 994 164 999 165 1014 166 991 167 1023 168 976 169 1045 170 1096 171 1031 172 977 173 1053 174 1048 175 1004 176 1162 177 1086 178 1095 179 1072 180 1068 181 1129 182 1090 183 1045 184 1103 185 1082 186 1122 187 1156 188 1220 189 1174 190 1149 191 1155 192 1126 193 1122 194 1243 195 1243 196 1189 197 1235 198 1283 199 1176 200 1267 201 1202 202 1237 203 1179 204 1320 205 1234 206 1284 207 1345 208 1351 209 1375 210 1220 211 1373 212 1332 213 1426 214 1337 215 1360 216 1401 217 1383 218 1333 219 1329 220 1363 221 1450 222 1441 223 1418 224 1460 225 1437 226 1453 227 1508 228 1498 229 1473 230 1479 231 1432 232 1518 233 1450 234 1468 235 1567 236 1541 237 1526 238 1527 239 1663 240 1571 241 1588 242 1602 243 1635 244 1585 245 1590 246 1633 247 1711 248 1573 249 1652 250 1616 251 1683 252 1606 253 1625 254 1630 255 1590 256 1626 257 1747 258 1671 259 1624 260 1630 261 1693 262 1715 263 1739 264 1743 265 1759 266 1715 267 1813 268 1833 269 1857 270 1792 271 1860 272 1774 273 1693 274 1900 275 1802 276 1868 277 1797 278 1762 279 1949 280 1885 281 1854 282 1941 283 1819 284 1887 285 1966 286 1954 287 1978 288 1958 289 2021 290 1908 291 1948 292 1958 293 1936 294 1959 295 1986 296 1972 297 1995 298 2074 299 1945 300 1936 301 2075 302 2036 303 2049 304 2011 305 2084 306 2146 307 2022 308 2064 309 2188 310 2166 311 2197 312 2107 313 2197 314 2189 315 2156 316 2319 317 2149 318 2174 319 2317 320 2205 321 2247 322 2260 323 2067 324 2353 325 2323 326 2338 327 2327 328 2219 329 2223 330 2362 331 2327 332 2350 333 2382 334 2247 335 2386 336 2364 337 2389 338 2323 339 2305 340 2453 341 2351 342 2481 343 2443 344 2381 345 2443 346 2490 347 2514 348 2548 349 2391 350 2404 351 2368 352 2521 353 2432 354 2363 355 2499 356 2500 357 2498 358 2506 359 2466 360 2625 361 2557 362 2517 363 2542 364 2548 365 2680 366 2642 367 2624 368 2646 369 2605 370 2669 371 2647 372 2859 373 2760 374 2737 375 2625 376 2614 377 2701 378 2665 379 2732 380 2621 381 2562 382 2812 383 2777 384 2767 385 2778 386 2811 387 2827 388 2877 389 2764 390 2809 391 2863 392 2810 393 2966 394 2859 395 2761 396 2858 397 2803 398 2844 399 3030 400 2890 401 2886 402 2893 403 2935 404 2824 405 2939 406 2966 407 3006 408 2911 409 3002 410 2971 411 3030 412 2976 413 3061 414 2967 415 3172 416 3007 417 3133 418 2966 419 2945 420 3111 421 3145 422 3263 423 3145 424 3075 425 3162 426 3151 427 2967 428 3142 429 3079 430 2971 431 3179 432 3227 433 3255 434 3193 435 3263 436 3217 437 3249 438 3291 439 3394 440 3273 441 3262 442 3241 443 3283 444 3173 445 3272 446 3267 447 3334 448 3425 449 3403 450 3282 451 3309 452 3412 453 3408 454 3397 455 3376 456 3421 457 3443 458 3458 459 3408 460 3487 461 3497 462 3496 463 3489 464 3405 465 3475 466 3489 467 3430 468 3358 469 3628 470 3566 471 3614 472 3444 473 3472 474 3488 475 3496 476 3618 477 3552 478 3448 479 3516 480 3649 481 3619 482 3670 483 3749 484 3605 485 3591 486 3622 487 3632 488 3880 489 3777 490 3696 491 3844 492 3624 493 3820 494 3727 495 3727 496 3605 497 3818 498 3723 499 3676 500 3767 501 3901 502 3831 503 3738 504 3808 505 3732 506 3934 507 3745 508 3826 509 4097 510 4010 511 3966 512 3895 513 3974 514 3865 515 4122 516 3939 517 3880 518 3939 519 3766 520 3970 521 3940 522 3911 523 3956 524 4041 525 4081 526 4118 527 4042 528 3912 529 3975 530 4096 531 4020 532 4054 533 4114 534 4258 535 4181 536 4124 537 4191 538 4270 539 4064 540 4144 541 4110 542 4161 543 4168 544 4335 545 4114 546 4312 547 4204 548 4322 549 4235 550 4263 551 4273 552 4433 553 4423 554 4122 555 4254 556 4294 557 4308 558 4306 559 4168 560 4147 561 4361 562 4352 563 4401 564 4468 565 4415 566 4483 567 4434 568 4452 569 4276 570 4614 571 4387 572 4555 573 4375 574 4370 575 4574 576 4542 577 4504 578 4442 579 4450 580 4461 581 4440 582 4537 583 4632 584 4483 585 4654 586 4474 587 4745 588 4496 589 4722 590 4786 591 4766 592 4630 593 4815 594 4650 595 4690 596 4749 597 4720 598 4546 599 4669 600 4685 601 4802 602 4671 603 4873 604 4676 605 4672 606 4947 607 4632 608 4960 609 4695 610 4900 611 4852 612 4924 613 5000 614 4799 615 4839 616 4873 617 4919 618 4720 619 4839 620 4863 621 4915 622 4803 623 5023 624 5023 625 4807 626 4961 627 5054 628 4965 629 5119 630 5198 631 4828 632 5013 633 5154 634 4987 635 4902 636 4999 637 4744 638 5182 639 4928 640 5009 641 5193 642 5026 643 5261 644 5041 645 5145 646 5181 647 5077 648 5145 649 5179 650 5077 651 5248 652 5252 653 5015 654 5298 655 5314 656 5351 657 5179 658 5343 659 5259 660 5356 661 5244 662 5077 663 5176 664 5473 665 5366 666 5288 667 5307 668 5452 669 5252 670 5440 671 5364 672 5460 673 5221 674 5352 675 5494 676 5401 677 5587 678 5441 679 5396 680 5490 681 5269 682 5414 683 5329 684 5568 685 5676 686 5734 687 5442 688 5521 689 5509 690 5581 691 5576 692 5735 693 5487 694 5746 695 5828 696 5710 697 5766 698 5646 699 5563 700 5730 701 5644 702 5752 703 5725 704 5726 705 5666 706 5901 707 5641 708 5657 709 5971 710 5823 711 5874 712 5833 713 5838 714 5728 715 5707 716 6154 717 6026 718 5783 719 5769 720 6133 721 5792 722 5887 723 5928 724 5982 725 5968 726 6000 727 6007 728 5707 729 5905 730 6035 731 5978 732 5892 733 6160 734 5900 735 6016 736 6072 737 5943 738 6076 739 6009 740 6013 741 5923 742 6265 743 6239 744 6152 745 6225 746 6262 747 6044 748 6349 749 6318 750 6081 751 6220 752 6315 753 6151 754 6301 755 6028 756 6350 757 6242 758 6246 759 6205 760 6404 761 6301 762 6504 763 6315 764 6211 765 6180 766 6277 767 6409 768 6301 769 6314 770 6401 771 6459 772 6313 773 6215 774 6214 775 6414 776 6600 777 6499 778 6495 779 6490 780 6400 781 6472 782 6554 783 6458 784 6477 785 6595 786 6332 787 6304 788 6660 789 6630 790 6634 791 6621 792 6493 793 6679 794 6766 795 6620 796 6602 797 6642 798 6700 799 6602 800 6823 801 6630 802 6558 803 6616 804 6405 805 6700 806 6661 807 6571 808 6854 809 6671 810 6720 811 6709 812 6836 813 6763 814 6846 815 6672 816 6823 817 6909 818 6805 819 6832 820 7030 821 6932 822 6683 823 6909 824 6910 825 6656 826 6916 827 6921 828 6918 829 7030 830 6792 831 6961 832 7219 833 7027 834 6899 835 7268 836 7110 837 6880 838 6998 839 7255 840 7125 841 7053 842 7093 843 7233 844 7105 845 7093 846 7084 847 7187 848 7094 849 7035 850 7123 851 7178 852 7087 853 7485 854 7329 855 7273 856 7026 857 7399 858 7192 859 7165 860 7427 861 7448 862 7098 863 7360 864 7268 865 7312 866 7146 867 7350 868 7327 869 7179 870 7546 871 7282 872 7423 873 7457 874 7457 875 7470 876 7411 877 7502 878 7390 879 7386 880 7485 881 7435 882 7521 883 7618 884 7399 885 7516 886 7556 887 7634 888 7458 889 7798 890 7736 891 7618 892 7611 893 7617 894 7408 895 7440 896 7561 897 7570 898 7660 899 7616 900 7763 901 7674 902 7792 903 7718 904 7798 905 7785 906 7944 907 7876 908 7683 909 8032 910 7750 911 7981 912 7871 913 7655 914 7839 915 7879 916 7637 917 7768 918 7872 919 7656 920 7840 921 7845 922 7753 923 7966 924 7894 925 7862 926 7769 927 7944 928 7888 929 8105 930 8005 931 7791 932 8076 933 7813 934 8025 935 8128 936 8056 937 8146 938 7994 939 7862 940 7989 941 8287 942 8114 943 8293 944 7686 945 8358 946 8200 947 8169 948 8212 949 8227 950 8008 951 8267 952 8456 953 8316 954 8176 955 8186 956 8326 957 8277 958 8160 959 8362 960 8295 961 8437 962 8155 963 8200 964 8312 965 8417 966 8286 967 8320 968 8546 969 8122 970 8412 971 8301 972 8281 973 8376 974 8416 975 8434 976 8308 977 8660 978 8348 979 8340 980 8476 981 8474 982 8221 983 8667 984 8736 985 8578 986 8574 987 8752 988 8641 989 8854 990 8528 991 8609 992 8631 993 8590 994 8735 995 8407 996 8898 997 8790 998 8416 999 8529 1000 8770