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