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