1 2 2 1 3 1 4 1 5 9 6 11 7 11 8 13 9 13 10 11 11 13 12 35 13 37 14 41 15 43 16 43 17 43 18 47 19 47 20 49 21 53 22 53 23 55 24 55 25 53 26 55 27 59 28 61 29 65 30 67 31 121 32 125 33 127 34 133 35 131 36 137 37 139 38 141 39 145 40 147 41 149 42 155 43 153 44 159 45 163 46 169 47 165 48 161 49 165 50 171 51 175 52 177 53 183 54 181 55 183 56 185 57 187 58 193 59 195 60 199 61 205 62 203 63 197 64 201 65 207 66 211 67 205 68 207 69 343 70 211 71 215 72 217 73 363 74 367 75 371 76 377 77 381 78 383 79 389 80 391 81 391 82 399 83 399 84 407 85 411 86 417 87 421 88 423 89 429 90 437 91 443 92 441 93 443 94 449 95 451 96 457 97 461 98 459 99 467 100 459 101 463 102 463 103 467 104 471 105 479 106 483 107 483 108 487 109 491 110 499 111 503 112 507 113 513 114 521 115 519 116 519 117 527 118 533 119 537 120 541 121 549 122 547 123 553 124 557 125 559 126 559 127 561 128 561 129 563 130 567 131 571 132 577 133 579 134 583 135 589 136 591 137 597 138 593 139 593 140 591 141 599 142 599 143 607 144 613 145 621 146 621 147 617 148 623 149 631 150 637 151 633 152 639 153 647 154 653 155 643 156 649 157 651 158 651 159 653 160 659 161 663 162 667 163 663 164 669 165 673 166 677 167 679 168 683 169 681 170 687 171 691 172 699 173 699 174 707 175 711 176 711 177 719 178 719 179 727 180 731 181 1085 182 729 183 737 184 743 185 747 186 751 187 753 188 757 189 761 190 1129 191 1139 192 1141 193 1145 194 1147 195 1153 196 1159 197 1163 198 1163 199 1171 200 1177 201 1183 202 1193 203 1199 204 1199 205 1201 206 1195 207 1205 208 1213 209 1219 210 1229 211 1235 212 1243 213 1253 214 1261 215 1261 216 1271 217 1277 218 1255 219 1261 220 1267 221 1271 222 1265 223 1267 224 1265 225 1273 226 1283 227 1291 228 1297 229 1301 230 1309 231 1319 232 1325 233 1325 234 1327 235 1337 236 1345 237 1355 238 1363 239 1369 240 1369 241 1369 242 1373 243 1373 244 1379 245 1387 246 1393 247 1397 248 1405 249 1409 250 1417 251 1415 252 1423 253 1429 254 1439 255 1447 256 1453 257 1463 258 1469 259 1471 260 1463 261 1469 262 1477 263 1487 264 1475 265 1483 266 1493 267 1495 268 1495 269 1505 270 1507 271 1511 272 1517 273 1523 274 1529 275 1523 276 1529 277 1537 278 1547 279 1547 280 1549 281 1549 282 1553 283 1549 284 1547 285 1553 286 1561 287 1571 288 1579 289 1589 290 1591 291 1591 292 1597 293 1603 294 1597 295 1607 296 1603 297 1613 298 1603 299 1609 300 1613 301 1619 302 1627 303 1637 304 1645 305 1649 306 1655 307 1657 308 1667 309 1669 310 1667 311 1669 312 1675 313 1675 314 1685 315 1693 316 1703 317 1705 318 1705 319 1715 320 1711 321 1721 322 1727 323 1735 324 1745 325 1747 326 1751 327 1745 328 1733 329 1741 330 1747 331 1751 332 1747 333 1757 334 1765 335 1769 336 1765 337 1775 338 1783 339 1787 340 1793 341 1799 342 1807 343 1807 344 1817 345 1807 346 1813 347 1823 348 1829 349 1837 350 1843 351 1841 352 1847 353 1855 354 1865 355 1871 356 1879 357 1885 358 1885 359 1891 360 1897 361 1895 362 1903 363 1909 364 1909 365 1913 366 1919 367 1927 368 1913 369 1907 370 1909 371 1913 372 1921 373 1927 374 1937 375 1943 376 1933 377 1933 378 1943 379 1939 380 1943 381 1951 382 1951 383 1949 384 1951 385 1961 386 1969 387 1973 388 1979 389 1985 390 1993 391 2003 392 2011 393 2017 394 2021 395 2029 396 2039 397 2045 398 2047 399 2057 400 2059 401 2063 402 2071 403 2069 404 2071 405 2071 406 2081 407 2087 408 2095 409 2105 410 2101 411 2099 412 2107 413 2113 414 2117 415 2123 416 2131 417 2125 418 2129 419 2131 420 2137 421 2143 422 2147 423 2149 424 2149 425 2147 426 2155 427 2161 428 2167 429 2177 430 2161 431 2171 432 2173 433 2177 434 2185 435 2183 436 2191 437 2195 438 2195 439 2201 440 2201 441 2209 442 2215 443 3093 444 3097 445 3109 446 3107 447 3095 448 3105 449 3117 450 3119 451 3127 452 3137 453 3139 454 3147 455 3153 456 3163 457 3169 458 3161 459 3173 460 3183 461 3195 462 3197 463 3183 464 3195 465 3203 466 3211 467 3219 468 3229 469 3237 470 3249 471 3251 472 3261 473 3263 474 3275 475 3279 476 3291 477 3289 478 3301 479 3299 480 3307 481 3301 482 3299 483 3305 484 3315 485 3327 486 3337 487 3349 488 3341 489 3347 490 3349 491 3357 492 3361 493 3373 494 3383 495 3391 496 3403 497 3411 498 3415 499 3427 500 3429 501 3433 502 3445 503 3449 504 3449 505 3457 506 3467 507 3475 508 3481 509 3489 510 3497 511 3495 512 3497 513 3509 514 3519 515 3519 516 3527 517 3537 518 3543 519 3547 520 3553 521 3561 522 3569 523 3561 524 3569 525 3581 526 3585 527 3585 528 3595 529 3603 530 3599 531 3611 532 3615 533 3615 534 3625 535 3637 536 3641 537 3641 538 3651 539 3657 540 3653 541 3663 542 3671 543 3683 544 3693 545 3701 546 3713 547 3715 548 3725 549 3719 550 3711 551 3713 552 3725 553 3735 554 3743 555 3751 556 3763 557 3771 558 3763 559 3775 560 3783 561 3781 562 3789 563 3791 564 3803 565 3811 566 3813 567 3811 568 3823 569 3833 570 3841 571 3841 572 3851 573 3863 574 3859 575 3849 576 3853 577 3861 578 3873 579 3877 580 3889 581 3893 582 3905 583 3909 584 3917 585 3929 586 3933 587 3945 588 3949 589 3957 590 3963 591 3947 592 3951 593 3963 594 3967 595 3973 596 3981 597 3985 598 3981 599 3989 600 3991 601 3993 602 4005 603 4001 604 4009 605 4019 606 4027 607 4035 608 4031 609 4043 610 4047 611 4047 612 4055 613 4065 614 4077 615 4087 616 4077 617 4089 618 4091 619 4099 620 4097 621 4103 622 4111 623 4119 624 4115 625 4113 626 4125 627 4135 628 4143 629 4155 630 4163 631 4171 632 4175 633 4183 634 4185 635 4187 636 4183 637 4195 638 4203 639 4213 640 4209 641 4215 642 4205 643 4215 644 4227 645 4237 646 4245 647 4257 648 4259 649 4269 650 4269 651 4253 652 4257 653 4265 654 4267 655 4267 656 4275 657 4279 658 4281 659 4293 660 4303 661 4311 662 4317 663 4325 664 4329 665 4341 666 4351 667 4351 668 4359 669 4367 670 4377 671 4385 672 4397 673 4401 674 4413 675 4411 676 4413 677 4419 678 4415 679 4425 680 4433 681 4435 682 4447 683 4455 684 4463 685 4471 686 4457 687 4465 688 4465 689 4475 690 4481 691 4485 692 4491 693 4493 694 4489 695 4499 696 4511 697 4521 698 4511 699 4513 700 4521 701 4533 702 4531 703 4539 704 4547 705 4547 706 4551 707 4551 708 4561 709 4545 710 4553 711 4561 712 4569 713 4575 714 4583 715 4593 716 4605 717 4607 718 4615 719 4625 720 4637 721 4645 722 4637 723 4645 724 4657 725 4667 726 4663 727 4675 728 4685 729 4687 730 4699 731 4707 732 4717 733 4705 734 4713 735 4721 736 4731 737 4737 738 4741 739 4723 740 4721 741 4733 742 4741 743 4751 744 4763 745 4773 746 4785 747 4789 748 4789 749 4797 750 4807 751 4813 752 4817 753 4825 754 4819 755 4829 756 4841 757 4849 758 4833 759 4843 760 4849 761 4853 762 4861 763 4869 764 4875 765 4883 766 4885 767 4895 768 4903 769 4915 770 4923 771 4933 772 4941 773 4953 774 4957 775 4969 776 4967 777 4975 778 4969 779 4979 780 4981 781 4981 782 4967 783 4975 784 4969 785 4979 786 4975 787 4981 788 4989 789 4999 790 5007 791 5007 792 5015 793 5023 794 5027 795 5039 796 5043 797 5045 798 5051 799 5055 800 5067 801 5071 802 5077 803 5079 804 5083 805 5073 806 5085 807 5095 808 5101 809 5109 810 5119 811 5125 812 5121 813 5125 814 5133 815 5141 816 5153 817 5161 818 5165 819 5167 820 5179 821 5183 822 5191 823 5199 824 5207 825 5213 826 5221 827 5225 828 5233 829 5245 830 5253 831 5261 832 5269 833 5273 834 5279 835 5269 836 5277 837 5269 838 5281 839 5277 840 5287 841 5293 842 5297 843 5281 844 5287 845 5283 846 5293 847 5305 848 5309 849 5317 850 5329 851 5337 852 5347 853 5343 854 5349 855 5351 856 5347 857 5345 858 5353 859 5365 860 5367 861 5375 862 5379 863 5391 864 5395 865 5407 866 5415 867 5419 868 5419 869 5429 870 5419 871 5431 872 5429 873 5441 874 5445 875 5457 876 5461 877 5455 878 5465 879 5477 880 5487 881 5493 882 5491 883 5499 884 5507 885 5519 886 5521 887 5519 888 5525 889 5535 890 5543 891 5527 892 5539 893 5543 894 5555 895 5563 896 5573 897 5581 898 5589 899 5595 900 5603 901 5613 902 5615 903 5623 904 5629 905 5631 906 5641 907 5641 908 5643 909 5647 910 5637 911 5645 912 5647 913 5655 914 5667 915 5659 916 5665 917 5661 918 5665 919 5673 920 5673 921 5683 922 5695 923 5703 924 5707 925 5713 926 5721 927 5731 928 5739 929 5723 930 5723 931 5727 932 5739 933 5741 934 5745 935 5757 936 5755 937 5767 938 5763 939 5753 940 5749 941 5757 942 5755 943 5751 944 5759 945 5771 946 5767 947 5777 948 5785 949 5797 950 5801 951 5807 952 5811 953 5819 954 5827 955 5833 956 5843 957 5851 958 5863 959 5867 960 5879 961 5881 962 5891 963 5899 964 5907 965 5919 966 5921 967 5931 968 5931 969 5927 970 5937 971 5945 972 5939 973 5949 974 5955 975 5963 976 5973 977 5979 978 5989 979 5989 980 5997 981 6007 982 6007 983 6009 984 6019 985 6031 986 6015 987 6025 988 6015 989 6023 990 6031 991 6033 992 6035 993 6035 994 6043 995 6053 996 6065 997 6075 998 6071 999 6079 1000 6081