1 2 2 3 3 2 4 3 5 19 6 5 7 13 8 7 9 17 10 19 11 43 12 11 13 103 14 13 15 29 16 31 17 67 18 17 19 37 20 19 21 41 22 43 23 137 24 23 25 149 26 103 27 53 28 83 29 173 30 29 31 61 32 31 33 131 34 67 35 139 36 71 37 73 38 37 39 233 40 79 41 163 42 41 43 257 44 43 45 89 46 137 47 281 48 47 49 97 50 149 51 101 52 103 53 211 54 53 55 109 56 167 57 113 58 173 59 353 60 59 61 487 62 61 63 251 64 127 65 389 66 131 67 401 68 67 69 137 70 139 71 283 72 71 73 1021 74 73 75 149 76 151 77 307 78 233 79 157 80 79 81 647 82 163 83 331 84 83 85 509 86 257 87 173 88 263 89 1423 90 89 91 181 92 367 93 557 94 281 95 379 96 191 97 193 98 97 99 197 100 199 101 1009 102 101 103 617 104 103 105 419 106 211 107 641 108 107 109 653 110 109 111 443 112 223 113 677 114 113 115 229 116 347 117 233 118 353 119 1427 120 239 121 241 122 487 123 491 124 619 125 499 126 251 127 761 128 127 129 257 130 389 131 523 132 131 133 797 134 401 135 269 136 271 137 547 138 137 139 277 140 139 141 281 142 283 143 571 144 431 145 2029 146 1021 147 293 148 443 149 1489 150 149 151 1811 152 151 153 1223 154 307 155 619 156 311 157 313 158 157 159 317 160 479 161 643 162 647 163 977 164 163 165 659 166 331 167 1669 168 167 169 337 170 509 171 683 172 859 173 691 174 173 175 349 176 1231 177 353 178 1423 179 1789 180 179 181 1447 182 181 183 1097 184 367 185 739 186 557 187 373 188 563 189 1511 190 379 191 4201 192 191 193 1543 194 193 195 389 196 587 197 787 198 197 199 397 200 199 201 401 202 1009 203 811 204 1019 205 409 206 617 207 827 208 1039 209 2089 210 419 211 421 212 211 213 1277 214 641 215 859 216 431 217 433 218 653 219 4817 220 439 221 883 222 443 223 1783 224 223 225 449 226 677 227 907 228 227 229 457 230 229 231 461 232 463 233 3727 234 233 235 1409 236 3067 237 947 238 1427 239 1433 240 239 241 3373 242 241 243 971 244 487 245 2939 246 491 247 1481 248 743 249 1493 250 499 251 3011 252 251 253 3541 254 761 255 509 256 1279 257 3083 258 257 259 1553 260 1039 261 521 262 523 263 1051 264 263 265 3709 266 797 267 1601 268 1607 269 1613 270 269 271 541 272 271 273 1091 274 547 275 2749 276 827 277 3323 278 277 279 557 280 839 281 1123 282 281 283 1697 284 283 285 569 286 571 287 1721 288 863 289 577 290 2029 291 1163 292 1459 293 1171 294 293 295 3539 296 887 297 593 298 1489 299 4783 300 599 301 601 302 1811 303 2423 304 607 305 3049 306 1223 307 613 308 307 309 617 310 619 311 3109 312 311 313 1877 314 313 315 1259 316 631 317 1901 318 317 319 1913 320 1279 321 641 322 643 323 1291 324 647 325 1949 326 977 327 653 328 983 329 1973 330 659 331 661 332 331 333 1997 334 1669 335 4019 336 2351 337 673 338 337 339 677 340 1019 341 4091 342 683 343 4801 344 1031 345 2069 346 691 347 2081 348 347 349 2791 350 349 351 701 352 1759 353 3529 354 353 355 709 356 1423 357 1427 358 1789 359 2153 360 359 361 2887 362 1447 363 1451 364 727 365 1459 366 1097 367 733 368 367 369 2213 370 739 371 1483 372 743 373 2237 374 373 375 1499 376 751 377 3769 378 1511 379 757 380 379 381 761 382 4201 383 1531 384 383 385 769 386 1543 387 773 388 1163 389 2333 390 389 391 4691 392 1567 393 1571 394 787 395 1579 396 1187 397 2381 398 397 399 797 400 1999 401 8821 402 401 403 2417 404 2423 405 809 406 811 407 1627 408 1223 409 3271 410 409 411 821 412 823 413 2477 414 827 415 829 416 1663 417 1667 418 2089 419 6703 420 419 421 5051 422 421 423 4229 424 2543 425 1699 426 1277 427 853 428 1283 429 857 430 859 431 1723 432 431 433 3463 434 433 435 2609 436 1307 437 1747 438 4817 439 877 440 439 441 881 442 883 443 2657 444 443 445 3559 446 1783 447 1787 448 2239 449 2693 450 449 451 3607 452 2711 453 1811 454 907 455 2729 456 911 457 2741 458 457 459 2753 460 919 461 5531 462 461 463 2777 464 463 465 929 466 3727 467 1867 468 467 469 937 470 1409 471 941 472 6607 473 2837 474 947 475 11399 476 1427 477 953 478 1433 479 4789 480 479 481 3847 482 3373 483 1931 484 967 485 2909 486 971 487 5843 488 487 489 977 490 2939 491 4909 492 491 493 2957 494 1481 495 1979 496 991 497 1987 498 1493 499 997 500 499 501 2003 502 3011 503 2011 504 503 505 1009 506 3541 507 1013 508 1523 509 9161 510 509 511 1021 512 3583 513 10259 514 3083 515 3089 516 1031 517 1033 518 1553 519 5189 520 1039 521 2083 522 521 523 3137 524 523 525 1049 526 1051 527 6323 528 1583 529 4231 530 3709 531 1061 532 1063 533 2131 534 1601 535 1069 536 1607 537 3221 538 1613 539 8623 540 1619 541 4327 542 541 543 3257 544 1087 545 2179 546 1091 547 1093 548 547 549 1097 550 2749 551 2203 552 1103 553 4423 554 3323 555 1109 556 1667 557 5569 558 557 559 1117 560 2239 561 2243 562 1123 563 2251 564 563 565 1129 566 1697 567 2267 568 3407 569 3413 570 569 571 4567 572 571 573 4583 574 1721 575 3449 576 1151 577 1153 578 577 579 6947 580 4639 581 6971 582 1163 583 4663 584 5839 585 2339 586 1171 587 2347 588 587 589 3533 590 3539 591 1181 592 7103 593 2371 594 593 595 4759 596 1787 597 1193 598 4783 599 3593 600 599 601 1201 602 601 603 2411 604 1811 605 9679 606 2423 607 1213 608 607 609 1217 610 3049 611 7331 612 1223 613 3677 614 613 615 1229 616 1231 617 2467 618 617 619 1237 620 619 621 4967 622 3109 623 6229 624 1871 625 1249 626 1877 627 3761 628 3767 629 7547 630 1259 631 12619 632 631 633 2531 634 1901 635 2539 636 1907 637 3821 638 1913 639 1277 640 1279 641 7691 642 641 643 9001 644 643 645 1289 646 1291 647 3881 648 647 649 1297 650 1949 651 1301 652 1303 653 3917 654 653 655 3929 656 4591 657 6569 658 1973 659 7907 660 659 661 1321 662 661 663 5303 664 1327 665 2659 666 1997 667 4001 668 2003 669 4013 670 4019 671 2683 672 2687 673 9421 674 673 675 2699 676 2027 677 2707 678 677 679 4073 680 2039 681 1361 682 4091 683 2731 684 683 685 5479 686 4801 687 1373 688 2063 689 4133 690 2069 691 1381 692 691 693 4157 694 2081 695 6949 696 2087 697 8363 698 2791 699 5591 700 1399 701 2803 702 701 703 4217 704 2111 705 1409 706 3529 707 4241 708 3539 709 4253 710 709 711 2843 712 1423 713 2851 714 1427 715 1429 716 5011 717 1433 718 2153 719 8627 720 719 721 10093 722 2887 723 4337 724 1447 725 4349 726 1451 727 1453 728 727 729 4373 730 1459 731 7309 732 2927 733 4397 734 733 735 2939 736 1471 737 4421 738 2213 739 8867 740 739 741 1481 742 1483 743 2971 744 743 745 1489 746 2237 747 1493 748 2243 749 4493 750 1499 751 6007 752 751 753 3011 754 3769 755 3019 756 1511 757 10597 758 757 759 7589 760 6079 761 13697 762 761 763 15259 764 4583 765 7649 766 1531 767 3067 768 6143 769 6151 770 769 771 3083 772 1543 773 4637 774 773 775 1549 776 5431 777 1553 778 2333 779 4673 780 1559 781 6247 782 4691 783 6263 784 1567 785 9419 786 1571 787 4721 788 787 789 4733 790 1579 791 3163 792 1583 793 6343 794 2381 795 6359 796 6367 797 3187 798 797 799 1597 800 2399 801 1601 802 8821 803 4817 804 1607 805 1609 806 2417 807 1613 808 2423 809 8089 810 809 811 1621 812 811 813 3251 814 1627 815 3259 816 2447 817 9803 818 3271 819 1637 820 2459 821 8209 822 821 823 4937 824 823 825 3299 826 2477 827 3307 828 827 829 1657 830 829 831 3323 832 1663 833 3331 834 1667 835 1669 836 3343 837 3347 838 6703 839 8389 840 839 841 10091 842 5051 843 3371 844 2531 845 10139 846 4229 847 1693 848 2543 849 1697 850 1699 851 10211 852 3407 853 6823 854 853 855 1709 856 7703 857 13711 858 857 859 5153 860 859 861 1721 862 1723 863 8629 864 863 865 5189 866 3463 867 1733 868 4339 869 8689 870 2609 871 1741 872 5231 873 3491 874 1747 875 3499 876 6131 877 1753 878 877 879 5273 880 1759 881 19381 882 881 883 5297 884 883 885 3539 886 2657 887 3547 888 887 889 1777 890 3559 891 7127 892 1783 893 3571 894 1787 895 1789 896 2687 897 5381 898 2693 899 5393 900 2699 901 1801 902 3607 903 5417 904 2711 905 9049 906 1811 907 5441 908 907 909 14543 910 2729 911 3643 912 911 913 5477 914 2741 915 3659 916 1831 917 5501 918 2753 919 7351 920 919 921 9209 922 5531 923 3691 924 1847 925 16649 926 2777 927 14831 928 4639 929 5573 930 929 931 1861 932 3727 933 22391 934 1867 935 3739 936 1871 937 1873 938 937 939 1877 940 1879 941 16937 942 941 943 5657 944 6607 945 1889 946 2837 947 22727 948 947 949 5693 950 11399 951 1901 952 4759 953 5717 954 953 955 7639 956 3823 957 1913 958 4789 959 40277 960 2879 961 7687 962 3847 963 3851 964 5783 965 9649 966 1931 967 1933 968 967 969 5813 970 2909 971 17477 972 971 973 35027 974 5843 975 1949 976 1951 977 3907 978 977 979 25453 980 2939 981 3923 982 4909 983 3931 984 983 985 7879 986 2957 987 1973 988 2963 989 11867 990 1979 991 7927 992 991 993 9929 994 1987 995 9949 996 6971 997 1993 998 997 999 1997 1000 1999