0 1 1 2 2 6 3 9 4 16 5 17 6 22 7 25 8 31 9 34 10 37 11 43 12 47 13 49 14 56 15 56 16 60 17 65 18 72 19 74 20 79 21 79 22 83 23 90 24 97 25 97 26 102 27 101 28 108 29 114 30 122 31 119 32 125 33 123 34 133 35 139 36 145 37 142 38 148 39 148 40 158 41 162 42 168 43 164 44 173 45 172 46 183 47 184 48 191 49 186 50 198 51 197 52 206 53 207 54 214 55 211 56 223 57 220 58 229 59 229 60 239 61 235 62 248 63 242 64 252 65 251 66 264 67 260 68 271 69 265 70 275 71 276 72 289 73 283 74 294 75 287 76 300 77 300 78 314 79 305 80 317 81 309 82 325 83 325 84 337 85 328 86 340 87 334 88 350 89 348 90 360 91 350 92 365 93 358 94 375 95 370 96 383 97 372 98 390 99 383 100 398 101 393 102 406 103 397 104 415 105 406 106 421 107 415 108 431 109 421 110 440 111 428 112 444 113 437 114 456 115 446 116 463 117 451 118 467 119 462 120 481 121 469 122 486 123 473 124 492 125 486 126 506 127 491 128 509 129 495 130 517 131 511 132 529 133 514 134 532 135 520 136 542 137 534 138 552 139 536 140 557 141 544 142 567 143 556 144 575 145 558 146 582 147 569 148 590 149 579 150 598 151 583 152 607 153 592 154 613 155 601 156 623 157 607 158 632 159 614 160 636 161 623 162 648 163 632 164 655 165 637 166 659 167 648 168 673 169 655 170 678 171 659 172 684 173 672 174 698 175 677 176 701 177 681 178 709 179 697 180 721 181 700 182 724 183 706 184 734 185 720 186 744 187 722 188 749 189 730 190 759 191 742 192 767 193 744 194 774 195 755 196 782 197 765 198 790 199 769 200 799 201 778 202 805 203 787 204 815 205 793 206 824 207 800 208 828 209 809 210 840 211 818 212 847 213 823 214 851 215 834 216 865 217 841 218 870 219 845 220 876 221 858 222 890 223 863 224 893 225 867 226 901 227 883 228 913 229 886 230 916 231 892 232 926 233 906 234 936 235 908 236 941 237 916 238 951 239 928 240 959 241 930 242 966 243 941 244 974 245 951 246 982 247 955 248 991 249 964 250 997 251 973 252 1007 253 979 254 1016 255 986 256 1020 257 995 258 1032 259 1004 260 1039 261 1009 262 1043 263 1020 264 1057 265 1027 266 1062 267 1031 268 1068 269 1044 270 1082 271 1049 272 1085 273 1053 274 1093 275 1069 276 1105 277 1072 278 1108 279 1078 280 1118 281 1092 282 1128 283 1094 284 1133 285 1102 286 1143 287 1114 288 1151 289 1116 290 1158 291 1127 292 1166 293 1137 294 1174 295 1141 296 1183 297 1150 298 1189 299 1159 300 1199 301 1165 302 1208 303 1172 304 1212 305 1181 306 1224 307 1190 308 1231 309 1195 310 1235 311 1206 312 1249 313 1213 314 1254 315 1217 316 1260 317 1230 318 1274 319 1235 320 1277 321 1239 322 1285 323 1255 324 1297 325 1258 326 1300 327 1264 328 1310 329 1278 330 1320 331 1280 332 1325 333 1288 334 1335 335 1300 336 1343 337 1302 338 1350 339 1313 340 1358 341 1323 342 1366 343 1327 344 1375 345 1336 346 1381 347 1345 348 1391 349 1351 350 1400 351 1358 352 1404 353 1367 354 1416 355 1376 356 1423 357 1381 358 1427 359 1392 360 1441 361 1399 362 1446 363 1403 364 1452 365 1416 366 1466 367 1421 368 1469 369 1425 370 1477 371 1441 372 1489 373 1444 374 1492 375 1450 376 1502 377 1464 378 1512 379 1466 380 1517 381 1474 382 1527 383 1486 384 1535 385 1488 386 1542 387 1499 388 1550 389 1509 390 1558 391 1513 392 1567 393 1522 394 1573 395 1531 396 1583 397 1537 398 1592 399 1544 400 1596 401 1553 402 1608 403 1562 404 1615 405 1567 406 1619 407 1578 408 1633 409 1585 410 1638 411 1589 412 1644 413 1602 414 1658 415 1607 416 1661 417 1611 418 1669 419 1627 420 1681 421 1630 422 1684 423 1636 424 1694 425 1650 426 1704 427 1652 428 1709 429 1660 430 1719 431 1672 432 1727 433 1674 434 1734 435 1685 436 1742 437 1695 438 1750 439 1699 440 1759 441 1708 442 1765 443 1717 444 1775 445 1723 446 1784 447 1730 448 1788 449 1739 450 1800 451 1748 452 1807 453 1753 454 1811 455 1764 456 1825 457 1771 458 1830 459 1775 460 1836 461 1788 462 1850 463 1793 464 1853 465 1797 466 1861 467 1813 468 1873 469 1816 470 1876 471 1822 472 1886 473 1836 474 1896 475 1838 476 1901 477 1846 478 1911 479 1858 480 1919 481 1860 482 1926 483 1871 484 1934 485 1881 486 1942 487 1885 488 1951 489 1894 490 1957 491 1903 492 1967 493 1909 494 1976 495 1916 496 1980 497 1925 498 1992 499 1934 500 1999 501 1939 502 2003 503 1950 504 2017 505 1957 506 2022 507 1961 508 2028 509 1974 510 2042 511 1979 512 2045 513 1983 514 2053 515 1999 516 2065 517 2002 518 2068 519 2008 520 2078 521 2022 522 2088 523 2024 524 2093 525 2032 526 2103 527 2044 528 2111 529 2046 530 2118 531 2057 532 2126 533 2067 534 2134 535 2071 536 2143 537 2080 538 2149 539 2089 540 2159 541 2095 542 2168 543 2102 544 2172 545 2111 546 2184 547 2120 548 2191 549 2125 550 2195 551 2136 552 2209 553 2143 554 2214 555 2147 556 2220 557 2160 558 2234 559 2165 560 2237 561 2169 562 2245 563 2185 564 2257 565 2188 566 2260 567 2194 568 2270 569 2208 570 2280 571 2210 572 2285 573 2218 574 2295 575 2230 576 2303 577 2232 578 2310 579 2243 580 2318 581 2253 582 2326 583 2257 584 2335 585 2266 586 2341 587 2275 588 2351 589 2281 590 2360 591 2288 592 2364 593 2297 594 2376 595 2306 596 2383 597 2311 598 2387 599 2322 600 2401 601 2329 602 2406 603 2333 604 2412 605 2346 606 2426 607 2351 608 2429 609 2355 610 2437 611 2371 612 2449 613 2374 614 2452 615 2380 616 2462 617 2394 618 2472 619 2396 620 2477 621 2404 622 2487 623 2416 624 2495 625 2418 626 2502 627 2429 628 2510 629 2439 630 2518 631 2443 632 2527 633 2452 634 2533 635 2461 636 2543 637 2467 638 2552 639 2474 640 2556 641 2483 642 2568 643 2492 644 2575 645 2497 646 2579 647 2508 648 2593 649 2515 650 2598 651 2519 652 2604 653 2532 654 2618 655 2537 656 2621 657 2541 658 2629 659 2557 660 2641 661 2560 662 2644 663 2566 664 2654 665 2580 666 2664 667 2582 668 2669 669 2590 670 2679 671 2602 672 2687 673 2604 674 2694 675 2615 676 2702 677 2625 678 2710 679 2629 680 2719 681 2638 682 2725 683 2647 684 2735 685 2653 686 2744 687 2660 688 2748 689 2669 690 2760 691 2678 692 2767 693 2683 694 2771 695 2694 696 2785 697 2701 698 2790 699 2705 700 2796 701 2718 702 2810 703 2723 704 2813 705 2727 706 2821 707 2743 708 2833 709 2746 710 2836 711 2752 712 2846 713 2766 714 2856 715 2768 716 2861 717 2776 718 2871 719 2788 720 2879 721 2790 722 2886 723 2801 724 2894 725 2811 726 2902 727 2815 728 2911 729 2824 730 2917 731 2833 732 2927 733 2839 734 2936 735 2846 736 2940 737 2855 738 2952 739 2864 740 2959 741 2869 742 2963 743 2880 744 2977 745 2887 746 2982 747 2891 748 2988 749 2904 750 3002 751 2909 752 3005 753 2913 754 3013 755 2929 756 3025 757 2932 758 3028 759 2938 760 3038 761 2952 762 3048 763 2954 764 3053 765 2962 766 3063 767 2974 768 3071 769 2976 770 3078 771 2987 772 3086 773 2997 774 3094 775 3001 776 3103 777 3010 778 3109 779 3019 780 3119 781 3025 782 3128 783 3032 784 3132 785 3041 786 3144 787 3050 788 3151 789 3055 790 3155 791 3066 792 3169 793 3073 794 3174 795 3077 796 3180 797 3090 798 3194 799 3095 800 3197 801 3099 802 3205 803 3115 804 3217 805 3118 806 3220 807 3124 808 3230 809 3138 810 3240 811 3140 812 3245 813 3148 814 3255 815 3160 816 3263 817 3162 818 3270 819 3173 820 3278 821 3183 822 3286 823 3187 824 3295 825 3196 826 3301 827 3205 828 3311 829 3211 830 3320 831 3218 832 3324 833 3227 834 3336 835 3236 836 3343 837 3241 838 3347 839 3252 840 3361 841 3259 842 3366 843 3263 844 3372 845 3276 846 3386 847 3281 848 3389 849 3285 850 3397 851 3301 852 3409 853 3304 854 3412 855 3310 856 3422 857 3324 858 3432 859 3326 860 3437 861 3334 862 3447 863 3346 864 3455 865 3348 866 3462 867 3359 868 3470 869 3369 870 3478 871 3373 872 3487 873 3382 874 3493 875 3391 876 3503 877 3397 878 3512 879 3404 880 3516 881 3413 882 3528 883 3422 884 3535 885 3427 886 3539 887 3438 888 3553 889 3445 890 3558 891 3449 892 3564 893 3462 894 3578 895 3467 896 3581 897 3471 898 3589 899 3487 900 3601 901 3490 902 3604 903 3496 904 3614 905 3510 906 3624 907 3512 908 3629 909 3520 910 3639 911 3532 912 3647 913 3534 914 3654 915 3545 916 3662 917 3555 918 3670 919 3559 920 3679 921 3568 922 3685 923 3577 924 3695 925 3583 926 3704 927 3590 928 3708 929 3599 930 3720 931 3608 932 3727 933 3613 934 3731 935 3624 936 3745 937 3631 938 3750 939 3635 940 3756 941 3648 942 3770 943 3653 944 3773 945 3657 946 3781 947 3673 948 3793 949 3676 950 3796 951 3682 952 3806 953 3696 954 3816 955 3698 956 3821 957 3706 958 3831 959 3718 960 3839 961 3720 962 3846 963 3731 964 3854 965 3741 966 3862 967 3745 968 3871 969 3754 970 3877 971 3763 972 3887 973 3769 974 3896 975 3776 976 3900 977 3785 978 3912 979 3794 980 3919 981 3799 982 3923 983 3810 984 3937 985 3817 986 3942 987 3821 988 3948 989 3834 990 3962 991 3839 992 3965 993 3843 994 3973 995 3859 996 3985 997 3862 998 3988 999 3868 1000 3998