1 1 2 3 3 5 4 7 5 9 6 11 7 13 8 17 9 19 10 23 11 25 12 29 13 31 14 37 15 41 16 43 17 47 18 49 19 53 20 59 21 61 22 67 23 71 24 73 25 79 26 81 27 83 28 89 29 97 30 101 31 103 32 107 33 109 34 113 35 121 36 127 37 131 38 137 39 139 40 149 41 151 42 157 43 163 44 167 45 169 46 173 47 179 48 181 49 191 50 193 51 197 52 199 53 211 54 223 55 227 56 229 57 233 58 239 59 241 60 251 61 257 62 263 63 269 64 271 65 277 66 281 67 283 68 289 69 293 70 307 71 311 72 313 73 317 74 331 75 337 76 347 77 349 78 353 79 359 80 361 81 367 82 373 83 379 84 383 85 389 86 397 87 401 88 409 89 419 90 421 91 431 92 433 93 439 94 443 95 449 96 457 97 461 98 463 99 467 100 479 101 487 102 491 103 499 104 503 105 509 106 521 107 523 108 529 109 541 110 547 111 557 112 563 113 569 114 571 115 577 116 587 117 593 118 599 119 601 120 607 121 613 122 617 123 619 124 625 125 631 126 641 127 643 128 647 129 653 130 659 131 661 132 673 133 677 134 683 135 691 136 701 137 709 138 719 139 727 140 733 141 739 142 743 143 751 144 757 145 761 146 769 147 773 148 787 149 797 150 809 151 811 152 821 153 823 154 827 155 829 156 839 157 841 158 853 159 857 160 859 161 863 162 877 163 881 164 883 165 887 166 907 167 911 168 919 169 929 170 937 171 941 172 947 173 953 174 961 175 967 176 971 177 977 178 983 179 991 180 997 181 1009 182 1013 183 1019 184 1021 185 1031 186 1033 187 1039 188 1049 189 1051 190 1061 191 1063 192 1069 193 1087 194 1091 195 1093 196 1097 197 1103 198 1109 199 1117 200 1123 201 1129 202 1151 203 1153 204 1163 205 1171 206 1181 207 1187 208 1193 209 1201 210 1213 211 1217 212 1223 213 1229 214 1231 215 1237 216 1249 217 1259 218 1277 219 1279 220 1283 221 1289 222 1291 223 1297 224 1301 225 1303 226 1307 227 1319 228 1321 229 1327 230 1361 231 1367 232 1369 233 1373 234 1381 235 1399 236 1409 237 1423 238 1427 239 1429 240 1433 241 1439 242 1447 243 1451 244 1453 245 1459 246 1471 247 1481 248 1483 249 1487 250 1489 251 1493 252 1499 253 1511 254 1523 255 1531 256 1543 257 1549 258 1553 259 1559 260 1567 261 1571 262 1579 263 1583 264 1597 265 1601 266 1607 267 1609 268 1613 269 1619 270 1621 271 1627 272 1637 273 1657 274 1663 275 1667 276 1669 277 1681 278 1693 279 1697 280 1699 281 1709 282 1721 283 1723 284 1733 285 1741 286 1747 287 1753 288 1759 289 1777 290 1783 291 1787 292 1789 293 1801 294 1811 295 1823 296 1831 297 1847 298 1849 299 1861 300 1867 301 1871 302 1873 303 1877 304 1879 305 1889 306 1901 307 1907 308 1913 309 1931 310 1933 311 1949 312 1951 313 1973 314 1979 315 1987 316 1993 317 1997 318 1999 319 2003 320 2011 321 2017 322 2027 323 2029 324 2039 325 2053 326 2063 327 2069 328 2081 329 2083 330 2087 331 2089 332 2099 333 2111 334 2113 335 2129 336 2131 337 2137 338 2141 339 2143 340 2153 341 2161 342 2179 343 2203 344 2207 345 2209 346 2213 347 2221 348 2237 349 2239 350 2243 351 2251 352 2267 353 2269 354 2273 355 2281 356 2287 357 2293 358 2297 359 2309 360 2311 361 2333 362 2339 363 2341 364 2347 365 2351 366 2357 367 2371 368 2377 369 2381 370 2383 371 2389 372 2393 373 2399 374 2401 375 2411 376 2417 377 2423 378 2437 379 2441 380 2447 381 2459 382 2467 383 2473 384 2477 385 2503 386 2521 387 2531 388 2539 389 2543 390 2549 391 2551 392 2557 393 2579 394 2591 395 2593 396 2609 397 2617 398 2621 399 2633 400 2647 401 2657 402 2659 403 2663 404 2671 405 2677 406 2683 407 2687 408 2689 409 2693 410 2699 411 2707 412 2711 413 2713 414 2719 415 2729 416 2731 417 2741 418 2749 419 2753 420 2767 421 2777 422 2789 423 2791 424 2797 425 2801 426 2803 427 2809 428 2819 429 2833 430 2837 431 2843 432 2851 433 2857 434 2861 435 2879 436 2887 437 2897 438 2903 439 2909 440 2917 441 2927 442 2939 443 2953 444 2957 445 2963 446 2969 447 2971 448 2999 449 3001 450 3011 451 3019 452 3023 453 3037 454 3041 455 3049 456 3061 457 3067 458 3079 459 3083 460 3089 461 3109 462 3119 463 3121 464 3137 465 3163 466 3167 467 3169 468 3181 469 3187 470 3191 471 3203 472 3209 473 3217 474 3221 475 3229 476 3251 477 3253 478 3257 479 3259 480 3271 481 3299 482 3301 483 3307 484 3313 485 3319 486 3323 487 3329 488 3331 489 3343 490 3347 491 3359 492 3361 493 3371 494 3373 495 3389 496 3391 497 3407 498 3413 499 3433 500 3449 501 3457 502 3461 503 3463 504 3467 505 3469 506 3481 507 3491 508 3499 509 3511 510 3517 511 3527 512 3529 513 3533 514 3539 515 3541 516 3547 517 3557 518 3559 519 3571 520 3581 521 3583 522 3593 523 3607 524 3613 525 3617 526 3623 527 3631 528 3637 529 3643 530 3659 531 3671 532 3673 533 3677 534 3691 535 3697 536 3701 537 3709 538 3719 539 3721 540 3727 541 3733 542 3739 543 3761 544 3767 545 3769 546 3779 547 3793 548 3797 549 3803 550 3821 551 3823 552 3833 553 3847 554 3851 555 3853 556 3863 557 3877 558 3881 559 3889 560 3907 561 3911 562 3917 563 3919 564 3923 565 3929 566 3931 567 3943 568 3947 569 3967 570 3989 571 4001 572 4003 573 4007 574 4013 575 4019 576 4021 577 4027 578 4049 579 4051 580 4057 581 4073 582 4079 583 4091 584 4093 585 4099 586 4111 587 4127 588 4129 589 4133 590 4139 591 4153 592 4157 593 4159 594 4177 595 4201 596 4211 597 4217 598 4219 599 4229 600 4231 601 4241 602 4243 603 4253 604 4259 605 4261 606 4271 607 4273 608 4283 609 4289 610 4297 611 4327 612 4337 613 4339 614 4349 615 4357 616 4363 617 4373 618 4391 619 4397 620 4409 621 4421 622 4423 623 4441 624 4447 625 4451 626 4457 627 4463 628 4481 629 4483 630 4489 631 4493 632 4507 633 4513 634 4517 635 4519 636 4523 637 4547 638 4549 639 4561 640 4567 641 4583 642 4591 643 4597 644 4603 645 4621 646 4637 647 4639 648 4643 649 4649 650 4651 651 4657 652 4663 653 4673 654 4679 655 4691 656 4703 657 4721 658 4723 659 4729 660 4733 661 4751 662 4759 663 4783 664 4787 665 4789 666 4793 667 4799 668 4801 669 4813 670 4817 671 4831 672 4861 673 4871 674 4877 675 4889 676 4903 677 4909 678 4919 679 4931 680 4933 681 4937 682 4943 683 4951 684 4957 685 4967 686 4969 687 4973 688 4987 689 4993 690 4999 691 5003 692 5009 693 5011 694 5021 695 5023 696 5039 697 5041 698 5051 699 5059 700 5077 701 5081 702 5087 703 5099 704 5101 705 5107 706 5113 707 5119 708 5147 709 5153 710 5167 711 5171 712 5179 713 5189 714 5197 715 5209 716 5227 717 5231 718 5233 719 5237 720 5261 721 5273 722 5279 723 5281 724 5297 725 5303 726 5309 727 5323 728 5329 729 5333 730 5347 731 5351 732 5381 733 5387 734 5393 735 5399 736 5407 737 5413 738 5417 739 5419 740 5431 741 5437 742 5441 743 5443 744 5449 745 5471 746 5477 747 5479 748 5483 749 5501 750 5503 751 5507 752 5519 753 5521 754 5527 755 5531 756 5557 757 5563 758 5569 759 5573 760 5581 761 5591 762 5623 763 5639 764 5641 765 5647 766 5651 767 5653 768 5657 769 5659 770 5669 771 5683 772 5689 773 5693 774 5701 775 5711 776 5717 777 5737 778 5741 779 5743 780 5749 781 5779 782 5783 783 5791 784 5801 785 5807 786 5813 787 5821 788 5827 789 5839 790 5843 791 5849 792 5851 793 5857 794 5861 795 5867 796 5869 797 5879 798 5881 799 5897 800 5903 801 5923 802 5927 803 5939 804 5953 805 5981 806 5987 807 6007 808 6011 809 6029 810 6037 811 6043 812 6047 813 6053 814 6067 815 6073 816 6079 817 6089 818 6091 819 6101 820 6113 821 6121 822 6131 823 6133 824 6143 825 6151 826 6163 827 6173 828 6197 829 6199 830 6203 831 6211 832 6217 833 6221 834 6229 835 6241 836 6247 837 6257 838 6263 839 6269 840 6271 841 6277 842 6287 843 6299 844 6301 845 6311 846 6317 847 6323 848 6329 849 6337 850 6343 851 6353 852 6359 853 6361 854 6367 855 6373 856 6379 857 6389 858 6397 859 6421 860 6427 861 6449 862 6451 863 6469 864 6473 865 6481 866 6491 867 6521 868 6529 869 6547 870 6551 871 6553 872 6561 873 6563 874 6569 875 6571 876 6577 877 6581 878 6599 879 6607 880 6619 881 6637 882 6653 883 6659 884 6661 885 6673 886 6679 887 6689 888 6691 889 6701 890 6703 891 6709 892 6719 893 6733 894 6737 895 6761 896 6763 897 6779 898 6781 899 6791 900 6793 901 6803 902 6823 903 6827 904 6829 905 6833 906 6841 907 6857 908 6863 909 6869 910 6871 911 6883 912 6889 913 6899 914 6907 915 6911 916 6917 917 6947 918 6949 919 6959 920 6961 921 6967 922 6971 923 6977 924 6983 925 6991 926 6997 927 7001 928 7013 929 7019 930 7027 931 7039 932 7043 933 7057 934 7069 935 7079 936 7103 937 7109 938 7121 939 7127 940 7129 941 7151 942 7159 943 7177 944 7187 945 7193 946 7207 947 7211 948 7213 949 7219 950 7229 951 7237 952 7243 953 7247 954 7253 955 7283 956 7297 957 7307 958 7309 959 7321 960 7331 961 7333 962 7349 963 7351 964 7369 965 7393 966 7411 967 7417 968 7433 969 7451 970 7457 971 7459 972 7477 973 7481 974 7487 975 7489 976 7499 977 7507 978 7517 979 7523 980 7529 981 7537 982 7541 983 7547 984 7549 985 7559 986 7561 987 7573 988 7577 989 7583 990 7589 991 7591 992 7603 993 7607 994 7621 995 7639 996 7643 997 7649 998 7669 999 7673 1000 7681