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