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