1 2 2 3 3 5 4 7 5 11 6 13 7 31 8 41 9 43 10 53 11 61 12 79 13 97 14 101 15 109 16 113 17 137 18 139 19 179 20 191 21 197 22 229 23 233 24 239 25 251 26 271 27 281 28 311 29 313 30 331 31 337 32 347 33 353 34 367 35 373 36 379 37 383 38 401 39 409 40 433 41 443 42 463 43 487 44 499 45 503 46 521 47 541 48 547 49 563 50 577 51 587 52 593 53 599 54 631 55 641 56 647 57 653 58 661 59 673 60 677 61 683 62 701 63 727 64 733 65 739 66 757 67 769 68 787 69 809 70 811 71 857 72 883 73 919 74 929 75 937 76 941 77 983 78 991 79 1013 80 1033 81 1039 82 1049 83 1051 84 1063 85 1103 86 1117 87 1123 88 1129 89 1151 90 1171 91 1181 92 1187 93 1213 94 1217 95 1237 96 1249 97 1259 98 1291 99 1301 100 1303 101 1307 102 1319 103 1321 104 1367 105 1381 106 1409 107 1427 108 1439 109 1451 110 1453 111 1459 112 1481 113 1487 114 1531 115 1543 116 1549 117 1553 118 1559 119 1571 120 1579 121 1583 122 1607 123 1613 124 1619 125 1621 126 1669 127 1693 128 1709 129 1721 130 1723 131 1733 132 1741 133 1747 134 1753 135 1783 136 1787 137 1811 138 1847 139 1861 140 1867 141 1879 142 1889 143 1907 144 1933 145 1951 146 1973 147 1987 148 1993 149 2017 150 2053 151 2063 152 2089 153 2111 154 2129 155 2143 156 2207 157 2213 158 2239 159 2243 160 2269 161 2281 162 2309 163 2339 164 2341 165 2347 166 2357 167 2377 168 2383 169 2389 170 2393 171 2411 172 2417 173 2423 174 2473 175 2521 176 2531 177 2549 178 2551 179 2557 180 2591 181 2609 182 2621 183 2633 184 2647 185 2657 186 2659 187 2663 188 2671 189 2683 190 2687 191 2693 192 2707 193 2711 194 2731 195 2741 196 2749 197 2767 198 2777 199 2789 200 2791 201 2797 202 2819 203 2857 204 2909 205 2927 206 2939 207 2953 208 2999 209 3001 210 3011 211 3023 212 3049 213 3061 214 3067 215 3089 216 3109 217 3167 218 3169 219 3181 220 3187 221 3191 222 3221 223 3229 224 3257 225 3259 226 3301 227 3313 228 3329 229 3331 230 3361 231 3391 232 3407 233 3413 234 3449 235 3461 236 3463 237 3467 238 3469 239 3491 240 3511 241 3527 242 3529 243 3541 244 3547 245 3559 246 3571 247 3581 248 3583 249 3593 250 3617 251 3623 252 3631 253 3659 254 3671 255 3697 256 3719 257 3727 258 3733 259 3779 260 3793 261 3797 262 3803 263 3821 264 3847 265 3851 266 3853 267 3863 268 3877 269 3889 270 3917 271 3929 272 3931 273 3943 274 3947 275 4001 276 4003 277 4019 278 4027 279 4051 280 4073 281 4099 282 4129 283 4133 284 4139 285 4153 286 4157 287 4159 288 4211 289 4217 290 4229 291 4241 292 4253 293 4259 294 4271 295 4273 296 4339 297 4349 298 4357 299 4363 300 4373 301 4397 302 4421 303 4463 304 4483 305 4507 306 4517 307 4519 308 4523 309 4547 310 4561 311 4567 312 4583 313 4597 314 4643 315 4651 316 4657 317 4673 318 4703 319 4721 320 4733 321 4751 322 4759 323 4787 324 4789 325 4799 326 4801 327 4831 328 4877 329 4903 330 4909 331 4919 332 4933 333 4937 334 4943 335 4957 336 4969 337 4999 338 5003 339 5009 340 5011 341 5021 342 5059 343 5077 344 5099 345 5119 346 5153 347 5167 348 5171 349 5179 350 5189 351 5197 352 5209 353 5231 354 5233 355 5237 356 5279 357 5323 358 5351 359 5387 360 5413 361 5417 362 5471 363 5477 364 5479 365 5501 366 5507 367 5521 368 5557 369 5563 370 5569 371 5573 372 5581 373 5591 374 5639 375 5641 376 5659 377 5669 378 5689 379 5737 380 5741 381 5743 382 5807 383 5813 384 5849 385 5857 386 5861 387 5867 388 5879 389 5881 390 5903 391 5923 392 5927 393 5939 394 5953 395 5981 396 6007 397 6011 398 6029 399 6037 400 6043 401 6073 402 6091 403 6131 404 6143 405 6163 406 6217 407 6221 408 6263 409 6269 410 6277 411 6301 412 6311 413 6329 414 6343 415 6359 416 6361 417 6367 418 6373 419 6397 420 6473 421 6529 422 6547 423 6551 424 6569 425 6571 426 6577 427 6607 428 6619 429 6653 430 6661 431 6679 432 6691 433 6703 434 6761 435 6763 436 6779 437 6833 438 6841 439 6947 440 6949 441 6959 442 6967 443 6971 444 7013 445 7019 446 7043 447 7069 448 7079 449 7109 450 7129 451 7159 452 7177 453 7187 454 7207 455 7211 456 7213 457 7219 458 7243 459 7247 460 7297 461 7321 462 7331 463 7333 464 7349 465 7351 466 7369 467 7411 468 7433 469 7457 470 7481 471 7487 472 7489 473 7507 474 7517 475 7547 476 7549 477 7561 478 7573 479 7583 480 7589 481 7591 482 7603 483 7621 484 7643 485 7649 486 7669 487 7681 488 7691 489 7699 490 7717 491 7723 492 7753 493 7757 494 7817 495 7823 496 7829 497 7841 498 7867 499 7873 500 7877 501 7883 502 7919 503 7933 504 7937 505 7949 506 7951 507 7963 508 7993 509 8011 510 8017 511 8039 512 8053 513 8081 514 8093 515 8101 516 8179 517 8219 518 8231 519 8237 520 8243 521 8269 522 8273 523 8287 524 8291 525 8293 526 8311 527 8353 528 8369 529 8377 530 8387 531 8419 532 8423 533 8447 534 8521 535 8527 536 8537 537 8539 538 8543 539 8581 540 8627 541 8629 542 8663 543 8677 544 8681 545 8689 546 8693 547 8713 548 8737 549 8741 550 8753 551 8761 552 8779 553 8807 554 8819 555 8821 556 8849 557 8887 558 8923 559 8929 560 8941 561 8963 562 8969 563 9029 564 9041 565 9091 566 9103 567 9157 568 9173 569 9181 570 9187 571 9199 572 9209 573 9221 574 9227 575 9257 576 9277 577 9341 578 9343 579 9371 580 9391 581 9421 582 9431 583 9433 584 9437 585 9467 586 9479 587 9491 588 9497 589 9521 590 9601 591 9613 592 9619 593 9623 594 9629 595 9631 596 9661 597 9679 598 9689 599 9733 600 9743 601 9749 602 9767 603 9781 604 9787 605 9833 606 9839 607 9851 608 9857 609 9883 610 9887 611 9901 612 9907 613 9923 614 9929 615 9967 616 9973 617 10061 618 10091 619 10093 620 10103 621 10111 622 10151 623 10159 624 10163 625 10169 626 10211 627 10247 628 10253 629 10259 630 10271 631 10289 632 10301 633 10303 634 10321 635 10331 636 10369 637 10427 638 10429 639 10433 640 10457 641 10459 642 10463 643 10513 644 10531 645 10567 646 10589 647 10597 648 10613 649 10627 650 10631 651 10639 652 10687 653 10691 654 10711 655 10723 656 10733 657 10771 658 10781 659 10789 660 10799 661 10831 662 10837 663 10853 664 10859 665 10861 666 10867 667 10939 668 10949 669 10973 670 10979 671 10987 672 10993 673 11057 674 11083 675 11087 676 11093 677 11113 678 11149 679 11173 680 11197 681 11239 682 11261 683 11287 684 11299 685 11317 686 11351 687 11353 688 11369 689 11393 690 11443 691 11447 692 11489 693 11491 694 11503 695 11527 696 11551 697 11587 698 11593 699 11621 700 11633 701 11657 702 11689 703 11699 704 11701 705 11719 706 11743 707 11777 708 11783 709 11833 710 11867 711 11887 712 11897 713 11903 714 11909 715 11933 716 11939 717 11953 718 11969 719 11971 720 11987 721 12011 722 12037 723 12041 724 12043 725 12071 726 12073 727 12101 728 12113 729 12157 730 12161 731 12197 732 12239 733 12251 734 12263 735 12269 736 12281 737 12289 738 12373 739 12379 740 12391 741 12413 742 12433 743 12437 744 12473 745 12503 746 12541 747 12547 748 12577 749 12601 750 12637 751 12641 752 12647 753 12653 754 12659 755 12671 756 12697 757 12713 758 12721 759 12743 760 12757 761 12781 762 12791 763 12799 764 12809 765 12829 766 12841 767 12907 768 12917 769 12959 770 12973 771 12979 772 12983 773 13001 774 13003 775 13009 776 13043 777 13049 778 13093 779 13099 780 13103 781 13109 782 13159 783 13163 784 13177 785 13183 786 13217 787 13219 788 13229 789 13241 790 13249 791 13297 792 13309 793 13327 794 13367 795 13381 796 13399 797 13411 798 13441 799 13451 800 13457 801 13463 802 13469 803 13487 804 13499 805 13513 806 13537 807 13577 808 13591 809 13597 810 13613 811 13619 812 13633 813 13649 814 13679 815 13681 816 13709 817 13711 818 13721 819 13729 820 13763 821 13781 822 13807 823 13829 824 13859 825 13877 826 13901 827 13903 828 13907 829 13913 830 13921 831 13963 832 13967 833 13997 834 13999 835 14011 836 14033 837 14051 838 14081 839 14083 840 14149 841 14207 842 14249 843 14303 844 14321 845 14323 846 14341 847 14369 848 14389 849 14401 850 14407 851 14423 852 14437 853 14447 854 14449 855 14479 856 14503 857 14533 858 14551 859 14557 860 14591 861 14633 862 14657 863 14669 864 14717 865 14723 866 14731 867 14747 868 14753 869 14767 870 14771 871 14783 872 14797 873 14827 874 14851 875 14879 876 14887 877 14969 878 14983 879 15013 880 15053 881 15061 882 15077 883 15083 884 15107 885 15121 886 15149 887 15173 888 15187 889 15193 890 15199 891 15217 892 15227 893 15241 894 15259 895 15287 896 15289 897 15307 898 15319 899 15329 900 15361 901 15373 902 15377 903 15391 904 15401 905 15413 906 15451 907 15461 908 15467 909 15473 910 15497 911 15511 912 15527 913 15551 914 15601 915 15607 916 15619 917 15629 918 15641 919 15643 920 15649 921 15661 922 15683 923 15731 924 15739 925 15773 926 15787 927 15791 928 15797 929 15803 930 15817 931 15823 932 15881 933 15887 934 15907 935 15913 936 15923 937 15937 938 15959 939 15973 940 15991 941 16007 942 16033 943 16057 944 16061 945 16063 946 16087 947 16091 948 16111 949 16141 950 16189 951 16193 952 16217 953 16267 954 16301 955 16319 956 16333 957 16339 958 16361 959 16411 960 16417 961 16427 962 16433 963 16447 964 16453 965 16481 966 16487 967 16493 968 16561 969 16567 970 16607 971 16619 972 16657 973 16661 974 16673 975 16691 976 16703 977 16729 978 16741 979 16763 980 16811 981 16829 982 16883 983 16889 984 16927 985 16937 986 16963 987 16979 988 16981 989 16993 990 17021 991 17029 992 17093 993 17117 994 17123 995 17137 996 17159 997 17183 998 17203 999 17209 1000 17231