1 1 2 2 3 3 4 5 5 7 6 9 7 10 8 11 9 13 10 17 11 19 12 22 13 23 14 25 15 29 16 31 17 34 18 37 19 41 20 43 21 46 22 47 23 49 24 53 25 55 26 58 27 59 28 61 29 67 30 71 31 73 32 79 33 82 34 83 35 85 36 89 37 91 38 94 39 97 40 101 41 103 42 106 43 107 44 109 45 113 46 115 47 118 48 121 49 127 50 131 51 133 52 137 53 139 54 142 55 145 56 149 57 151 58 157 59 163 60 166 61 167 62 169 63 171 64 173 65 178 66 179 67 181 68 187 69 191 70 193 71 197 72 199 73 202 74 205 75 211 76 214 77 217 78 223 79 226 80 227 81 229 82 233 83 235 84 239 85 241 86 247 87 251 88 253 89 257 90 259 91 262 92 263 93 265 94 269 95 271 96 274 97 277 98 281 99 283 100 289 101 293 102 295 103 298 104 301 105 307 106 311 107 313 108 317 109 319 110 331 111 334 112 337 113 343 114 346 115 347 116 349 117 353 118 355 119 358 120 359 121 361 122 367 123 373 124 379 125 382 126 383 127 389 128 391 129 394 130 397 131 401 132 403 133 409 134 415 135 419 136 421 137 427 138 431 139 433 140 439 141 443 142 445 143 449 144 451 145 454 146 457 147 461 148 463 149 466 150 467 151 469 152 478 153 479 154 481 155 487 156 491 157 493 158 499 159 502 160 503 161 505 162 509 163 511 164 514 165 517 166 521 167 523 168 526 169 529 170 535 171 538 172 541 173 547 174 553 175 557 176 559 177 562 178 563 179 565 180 569 181 571 182 577 183 583 184 586 185 587 186 589 187 593 188 599 189 601 190 607 191 613 192 617 193 619 194 622 195 631 196 634 197 641 198 643 199 647 200 649 201 653 202 655 203 659 204 661 205 667 206 673 207 677 208 679 209 683 210 685 211 691 212 694 213 697 214 701 215 703 216 706 217 709 218 718 219 719 220 721 221 727 222 733 223 739 224 743 225 745 226 751 227 757 228 761 229 763 230 766 231 769 232 773 233 778 234 781 235 787 236 793 237 797 238 799 239 802 240 809 241 811 242 817 243 821 244 823 245 827 246 829 247 835 248 838 249 839 250 841 251 853 252 857 253 859 254 862 255 863 256 865 257 871 258 877 259 881 260 883 261 886 262 887 263 889 264 895 265 898 266 901 267 907 268 911 269 913 270 919 271 922 272 929 273 931 274 934 275 937 276 941 277 943 278 947 279 949 280 953 281 955 282 958 283 961 284 967 285 971 286 973 287 977 288 979 289 982 290 983 291 985 292 991 293 997 294 1003 295 1006 296 1009 297 1013 298 1018 299 1019 300 1021 301 1027 302 1031 303 1033 304 1039 305 1042 306 1049 307 1051 308 1057 309 1061 310 1063 311 1069 312 1081 313 1087 314 1091 315 1093 316 1097 317 1099 318 1103 319 1109 320 1111 321 1114 322 1117 323 1123 324 1126 325 1129 326 1135 327 1138 328 1141 329 1147 330 1151 331 1153 332 1159 333 1163 334 1165 335 1171 336 1174 337 1177 338 1181 339 1186 340 1187 341 1189 342 1193 343 1195 344 1198 345 1201 346 1207 347 1213 348 1217 349 1219 350 1223 351 1229 352 1231 353 1234 354 1237 355 1243 356 1249 357 1251 358 1255 359 1259 360 1261 361 1267 362 1273 363 1277 364 1279 365 1282 366 1283 367 1285 368 1289 369 1291 370 1294 371 1297 372 1301 373 1303 374 1306 375 1307 376 1315 377 1318 378 1319 379 1321 380 1327 381 1333 382 1339 383 1345 384 1351 385 1354 386 1357 387 1361 388 1363 389 1366 390 1367 391 1369 392 1373 393 1381 394 1387 395 1393 396 1399 397 1402 398 1405 399 1409 400 1411 401 1417 402 1423 403 1427 404 1429 405 1433 406 1438 407 1439 408 1441 409 1447 410 1451 411 1453 412 1459 413 1465 414 1471 415 1477 416 1481 417 1483 418 1486 419 1487 420 1489 421 1493 422 1499 423 1501 424 1507 425 1511 426 1513 427 1522 428 1523 429 1531 430 1537 431 1543 432 1546 433 1549 434 1553 435 1555 436 1559 437 1561 438 1567 439 1571 440 1579 441 1583 442 1585 443 1591 444 1594 445 1597 446 1601 447 1603 448 1607 449 1609 450 1613 451 1618 452 1619 453 1621 454 1627 455 1633 456 1637 457 1639 458 1642 459 1651 460 1654 461 1657 462 1663 463 1667 464 1669 465 1678 466 1681 467 1687 468 1693 469 1697 470 1699 471 1709 472 1711 473 1714 474 1717 475 1721 476 1723 477 1726 478 1733 479 1735 480 1741 481 1747 482 1753 483 1759 484 1762 485 1765 486 1774 487 1777 488 1783 489 1787 490 1789 491 1795 492 1801 493 1807 494 1811 495 1819 496 1822 497 1823 498 1831 499 1837 500 1843 501 1847 502 1849 503 1858 504 1861 505 1867 506 1871 507 1873 508 1877 509 1879 510 1882 511 1889 512 1891 513 1894 514 1897 515 1901 516 1903 517 1906 518 1907 519 1909 520 1913 521 1915 522 1921 523 1927 524 1931 525 1933 526 1939 527 1942 528 1945 529 1949 530 1951 531 1954 532 1957 533 1963 534 1966 535 1969 536 1973 537 1979 538 1981 539 1987 540 1993 541 1997 542 1999 543 2003 544 2005 545 2011 546 2017 547 2026 548 2027 549 2029 550 2038 551 2039 552 2041 553 2047 554 2053 555 2059 556 2062 557 2063 558 2069 559 2071 560 2077 561 2081 562 2083 563 2087 564 2089 565 2095 566 2098 567 2099 568 2101 569 2111 570 2113 571 2119 572 2122 573 2129 574 2131 575 2137 576 2141 577 2143 578 2149 579 2153 580 2155 581 2161 582 2167 583 2173 584 2179 585 2182 586 2191 587 2194 588 2197 589 2203 590 2206 591 2207 592 2209 593 2213 594 2215 595 2218 596 2221 597 2227 598 2237 599 2239 600 2243 601 2245 602 2251 603 2257 604 2263 605 2267 606 2269 607 2273 608 2281 609 2287 610 2293 611 2297 612 2302 613 2305 614 2309 615 2311 616 2317 617 2323 618 2326 619 2329 620 2333 621 2335 622 2339 623 2341 624 2347 625 2351 626 2353 627 2357 628 2359 629 2362 630 2371 631 2374 632 2377 633 2381 634 2383 635 2386 636 2389 637 2393 638 2395 639 2399 640 2401 641 2407 642 2411 643 2413 644 2417 645 2419 646 2423 647 2434 648 2437 649 2441 650 2443 651 2446 652 2447 653 2449 654 2455 655 2458 656 2459 657 2461 658 2467 659 2473 660 2477 661 2479 662 2491 663 2497 664 2503 665 2509 666 2515 667 2518 668 2521 669 2531 670 2533 671 2539 672 2543 673 2545 674 2549 675 2551 676 2554 677 2557 678 2563 679 2566 680 2569 681 2578 682 2579 683 2581 684 2587 685 2591 686 2593 687 2599 688 2602 689 2605 690 2609 691 2611 692 2614 693 2617 694 2621 695 2623 696 2629 697 2633 698 2638 699 2641 700 2647 701 2653 702 2657 703 2659 704 2663 705 2671 706 2677 707 2683 708 2687 709 2689 710 2693 711 2699 712 2701 713 2707 714 2711 715 2713 716 2719 717 2722 718 2729 719 2731 720 2734 721 2741 722 2743 723 2746 724 2749 725 2753 726 2761 727 2767 728 2773 729 2777 730 2779 731 2785 732 2789 733 2791 734 2797 735 2801 736 2803 737 2809 738 2815 739 2818 740 2819 741 2827 742 2833 743 2837 744 2839 745 2843 746 2845 747 2851 748 2854 749 2857 750 2861 751 2863 752 2866 753 2869 754 2878 755 2879 756 2881 757 2887 758 2893 759 2897 760 2899 761 2902 762 2903 763 2909 764 2911 765 2917 766 2923 767 2927 768 2929 769 2935 770 2939 771 2941 772 2947 773 2953 774 2957 775 2959 776 2962 777 2963 778 2965 779 2969 780 2971 781 2974 782 2977 783 2983 784 2986 785 2995 786 2998 787 2999 788 3001 789 3007 790 3011 791 3013 792 3019 793 3022 794 3023 795 3031 796 3037 797 3041 798 3043 799 3046 800 3049 801 3061 802 3067 803 3073 804 3079 805 3083 806 3085 807 3089 808 3091 809 3097 810 3103 811 3106 812 3109 813 3118 814 3119 815 3121 816 3127 817 3133 818 3137 819 3139 820 3142 821 3151 822 3163 823 3166 824 3167 825 3169 826 3181 827 3187 828 3191 829 3193 830 3199 831 3202 832 3203 833 3205 834 3209 835 3214 836 3217 837 3221 838 3223 839 3226 840 3229 841 3235 842 3238 843 3241 844 3247 845 3251 846 3253 847 3257 848 3259 849 3265 850 3271 851 3274 852 3277 853 3295 854 3299 855 3301 856 3307 857 3313 858 3319 859 3323 860 3329 861 3331 862 3334 863 3337 864 3343 865 3347 866 3349 867 3359 868 3361 869 3371 870 3373 871 3379 872 3385 873 3389 874 3391 875 3394 876 3397 877 3403 878 3407 879 3409 880 3411 881 3413 882 3415 883 3418 884 3421 885 3427 886 3433 887 3439 888 3442 889 3449 890 3457 891 3461 892 3463 893 3466 894 3467 895 3469 896 3481 897 3487 898 3491 899 3493 900 3499 901 3505 902 3511 903 3517 904 3523 905 3527 906 3529 907 3533 908 3539 909 3541 910 3547 911 3557 912 3559 913 3571 914 3574 915 3581 916 3583 917 3589 918 3593 919 3595 920 3601 921 3607 922 3613 923 3617 924 3622 925 3623 926 3631 927 3637 928 3643 929 3646 930 3649 931 3659 932 3661 933 3667 934 3671 935 3673 936 3677 937 3679 938 3691 939 3694 940 3697 941 3701 942 3709 943 3715 944 3719 945 3721 946 3727 947 3733 948 3739 949 3742 950 3751 951 3754 952 3761 953 3763 954 3767 955 3769 956 3778 957 3779 958 3781 959 3787 960 3793 961 3797 962 3799 963 3802 964 3803 965 3805 966 3811 967 3814 968 3817 969 3821 970 3823 971 3826 972 3829 973 3833 974 3841 975 3847 976 3851 977 3853 978 3859 979 3862 980 3863 981 3865 982 3871 983 3877 984 3881 985 3883 986 3889 987 3898 988 3901 989 3907 990 3911 991 3917 992 3919 993 3923 994 3929 995 3931 996 3937 997 3943 998 3946 999 3947 1000 3949