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