1 5 2 7 3 13 4 13 5 31 6 19 7 29 8 97 9 37 10 31 11 67 12 37 13 53 14 43 15 61 16 97 17 103 18 73 19 229 20 61 21 127 22 67 23 139 24 73 25 101 26 79 27 109 28 113 29 233 30 181 31 373 32 97 33 199 34 103 35 211 36 109 37 149 38 229 39 157 40 241 41 739 42 127 43 173 44 353 45 181 46 139 47 283 48 193 49 197 50 151 51 307 52 157 53 743 54 163 55 331 56 337 57 229 58 233 59 709 60 181 61 367 62 373 63 379 64 193 65 521 66 199 67 269 68 409 69 277 70 211 71 569 72 433 73 293 74 223 75 601 76 229 77 463 78 313 79 317 80 241 81 487 82 9349 83 499 84 337 85 1021 86 1033 87 349 88 353 89 1069 90 271 91 547 92 277 93 373 94 283 95 571 96 577 97 389 98 1373 99 397 100 401 101 607 102 307 103 619 104 313 105 421 106 3181 107 643 108 433 109 2617 110 331 111 1999 112 337 113 1583 114 457 115 461 116 349 117 937 118 709 119 953 120 2161 121 727 122 367 123 739 124 373 125 751 126 379 127 509 128 769 129 1033 130 521 131 787 132 397 133 1597 134 1609 135 541 136 409 137 823 138 829 139 557 140 421 141 1129 142 569 143 859 144 433 145 1741 146 439 147 883 148 593 149 1193 150 601 151 907 152 457 153 613 154 463 155 1861 156 937 157 3769 158 2213 159 3181 160 641 161 967 162 487 163 653 164 2297 165 661 166 499 167 2339 168 673 169 677 170 1021 171 2053 172 1033 173 1039 174 523 175 701 176 1409 177 709 178 1069 179 1433 180 541 181 1087 182 547 183 733 184 3313 185 1481 186 1117 187 1123 188 1129 189 757 190 571 191 2293 192 577 193 773 194 1553 195 1171 196 3529 197 3547 198 2377 199 797 200 601 201 1609 202 607 203 2437 204 613 205 821 206 619 207 829 208 1249 209 2927 210 631 211 8863 212 1697 213 853 214 643 215 1291 216 1297 217 1303 218 2617 219 877 220 661 221 1327 222 1777 223 2677 224 673 225 1801 226 2713 227 5449 228 4561 229 2749 230 691 231 4159 232 929 233 1399 234 937 235 941 236 709 237 1423 238 953 239 1913 240 3361 241 1447 242 727 243 1459 244 733 245 1471 246 739 247 1483 248 1489 249 997 250 751 251 4519 252 757 253 1013 254 3049 255 1021 256 769 257 1543 258 1033 259 3109 260 2081 261 1567 262 787 263 1579 264 2113 265 1061 266 1597 267 1069 268 1609 269 2153 270 811 271 1627 272 5441 273 1093 274 823 275 3301 276 829 277 1109 278 1669 279 1117 280 3361 281 3373 282 1129 283 1699 284 853 285 2281 286 859 287 1723 288 1153 289 3469 290 1741 291 1747 292 877 293 1759 294 883 295 1181 296 1777 297 1783 298 1193 299 2393 300 1201 301 3613 302 907 303 1213 304 1217 305 1831 306 919 307 1229 308 3697 309 1237 310 1861 311 1867 312 937 313 1879 314 3769 315 2521 316 3793 317 9511 318 6361 319 1277 320 4481 321 3853 322 967 323 3877 324 1297 325 1301 326 2609 327 2617 328 7873 329 2633 330 991 331 1987 332 997 333 1999 334 8017 335 2011 336 1009 337 6067 338 2029 339 2713 340 1021 341 2729 342 2053 343 1373 344 1033 345 1381 346 1039 347 2083 348 2089 349 8377 350 1051 351 10531 352 1409 353 4943 354 1063 355 2131 356 1069 357 1429 358 1433 359 10771 360 2161 361 10831 362 1087 363 1453 364 1093 365 6571 366 7321 367 2203 368 5153 369 2953 370 1481 371 2969 372 1117 373 1493 374 1123 375 2251 376 1129 377 5279 378 2269 379 4549 380 2281 381 2287 382 2293 383 4597 384 1153 385 2311 386 3089 387 1549 388 1553 389 9337 390 1171 391 2347 392 3137 393 5503 394 4729 395 2371 396 2377 397 2383 398 2389 399 1597 400 1201 401 3209 402 1609 403 1613 404 1213 405 1621 406 2437 407 3257 408 8161 409 1637 410 1231 411 2467 412 1237 413 4957 414 1657 415 12451 416 1249 417 1669 418 12541 419 5867 420 2521 421 17683 422 25321 423 1693 424 1697 425 2551 426 1279 427 1709 428 10273 429 3433 430 1291 431 3449 432 1297 433 1733 434 1303 435 1741 436 2617 437 7867 438 1753 439 13171 440 1321 441 2647 442 1327 443 2659 444 1777 445 2671 446 2677 447 1789 448 2689 449 3593 450 1801 451 2707 452 2713 453 2719 454 5449 455 2731 456 8209 457 13711 458 2749 459 3673 460 1381 461 2767 462 3697 463 5557 464 5569 465 1861 466 1399 467 2803 468 1873 469 1877 470 3761 471 3769 472 1889 473 9461 474 1423 475 1901 476 1429 477 6679 478 1913 479 3833 480 8641 481 2887 482 1447 483 1933 484 1453 485 3881 486 1459 487 1949 488 5857 489 5869 490 1471 491 3929 492 2953 493 1973 494 1483 495 2971 496 1489 497 6959 498 1993 499 1997 500 3001 501 15031 502 12049 503 3019 504 2017 505 9091 506 3037 507 2029 508 3049 509 4073 510 1531 511 3067 512 12289 513 2053 514 1543 515 7211 516 1549 517 2069 518 3109 519 4153 520 2081 521 16673 522 1567 523 6277 524 9433 525 4201 526 1579 527 3163 528 2113 529 12697 530 3181 531 3187 532 1597 533 6397 534 2137 535 2141 536 1609 537 4297 538 2153 539 6469 540 1621 541 9739 542 1627 543 3259 544 6529 545 3271 546 6553 547 16411 548 6577 549 7687 550 3301 551 3307 552 1657 553 2213 554 1663 555 2221 556 1669 557 3343 558 11161 559 2237 560 3361 561 6733 562 3373 563 7883 564 1693 565 3391 566 1699 567 2269 568 2273 569 6829 570 2281 571 27409 572 3433 573 2293 574 1723 575 18401 576 3457 577 2309 578 3469 579 6949 580 1741 581 4649 582 1747 583 2333 584 1753 585 2341 586 1759 587 8219 588 3529 589 2357 590 3541 591 3547 592 1777 593 3559 594 1783 595 2381 596 1789 597 2389 598 2393 599 4793 600 1801 601 3607 602 3613 603 7237 604 2417 605 3631 606 3637 607 3643 608 7297 609 2437 610 1831 611 4889 612 3673 613 14713 614 7369 615 3691 616 3697 617 4937 618 2473 619 2477 620 1861 621 3727 622 1867 623 3739 624 1873 625 11251 626 1879 627 8779 628 3769 629 7549 630 2521 631 7573 632 3793 633 8863 634 15217 635 5081 636 12721 637 2549 638 8933 639 2557 640 7681 641 3847 642 3853 643 7717 644 1933 645 7741 646 3877 647 9059 648 2593 649 7789 650 1951 651 3907 652 2609 653 3919 654 2617 655 2621 656 7873 657 3943 658 2633 659 5273 660 5281 661 3967 662 1987 663 9283 664 1993 665 9311 666 1999 667 4003 668 8017 669 2677 670 2011 671 4027 672 2017 673 2693 674 5393 675 4051 676 2029 677 5417 678 2713 679 48889 680 5441 681 5449 682 2729 683 4099 684 2053 685 2741 686 8233 687 2749 688 2753 689 8269 690 5521 691 8293 692 4153 693 4159 694 2083 695 12511 696 2089 697 2789 698 8377 699 2797 700 2801 701 12619 702 9829 703 4219 704 2113 705 4231 706 33889 707 4243 708 2833 709 2837 710 2131 711 5689 712 2137 713 21391 714 2143 715 2861 716 4297 717 5737 718 64621 719 8629 720 2161 721 4327 722 21661 723 4339 724 2897 725 5801 726 2179 727 2909 728 8737 729 2917 730 8761 731 5849 732 5857 733 21991 734 2203 735 5881 736 13249 737 4423 738 2953 739 2957 740 2221 741 4447 742 2969 743 22291 744 5953 745 8941 746 2239 747 4483 748 22441 749 10487 750 2251 751 4507 752 4513 753 4519 754 9049 755 13591 756 2269 757 13627 758 4549 759 3037 760 2281 761 4567 762 2287 763 9157 764 2293 765 3061 766 4597 767 4603 768 10753 769 18457 770 2311 771 13879 772 3089 773 4639 774 10837 775 4651 776 4657 777 3109 778 9337 779 9349 780 2341 781 23431 782 2347 783 9397 784 3137 785 9421 786 9433 787 4723 788 4729 789 11047 790 2371 791 6329 792 2377 793 4759 794 2383 795 3181 796 2389 797 4783 798 4789 799 23971 800 4801 801 9613 802 3209 803 11243 804 3217 805 3221 806 6449 807 3229 808 9697 809 6473 810 4861 811 9733 812 2437 813 3253 814 3257 815 6521 816 6529 817 4903 818 4909 819 6553 820 19681 821 6569 822 2467 823 19753 824 2473 825 3301 826 4957 827 11579 828 3313 829 9949 830 11621 831 4987 832 3329 833 4999 834 2503 835 5011 836 6689 837 5023 838 20113 839 10069 840 2521 841 10093 842 6737 843 3373 844 15193 845 6761 846 2539 847 3389 848 10177 849 6793 850 2551 851 5107 852 2557 853 3413 854 6833 855 6841 856 10273 857 6857 858 3433 859 25771 860 10321 861 5167 862 3449 863 5179 864 2593 865 3461 866 5197 867 3469 868 5209 869 10429 870 6961 871 5227 872 2617 873 10477 874 15733 875 7001 876 10513 877 15787 878 28097 879 3517 880 5281 881 15859 882 2647 883 3533 884 12377 885 3541 886 2659 887 5323 888 10657 889 3557 890 2671 891 5347 892 2677 893 12503 894 2683 895 3581 896 2689 897 7177 898 3593 899 7193 900 12601 901 5407 902 2707 903 3613 904 2713 905 5431 906 2719 907 5443 908 5449 909 3637 910 2731 911 29153 912 7297 913 5479 914 16453 915 7321 916 2749 917 5503 918 3673 919 3677 920 5521 921 5527 922 2767 923 12923 924 3697 925 3701 926 5557 927 3709 928 5569 929 7433 930 2791 931 11173 932 2797 933 3733 934 2803 935 7481 936 7489 937 5623 938 11257 939 13147 940 3761 941 5647 942 3769 943 5659 944 2833 945 7561 946 11353 947 5683 948 3793 949 3797 950 2851 951 58963 952 2857 953 11437 954 19081 955 3821 956 5737 957 5743 958 3833 959 7673 960 7681 961 17299 962 2887 963 3853 964 28921 965 5791 966 11593 967 23209 968 11617 969 3877 970 3881 971 5827 972 2917 973 5839 974 7793 975 5851 976 5857 977 7817 978 5869 979 3917 980 5881 981 17659 982 3929 983 13763 984 2953 985 11821 986 11833 987 5923 988 29641 989 29671 990 2971 991 17839 992 5953 993 13903 994 23857 995 11941 996 11953 997 3989 998 19961 999 7993 1000 3001