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