1 1 2 7 3 11 4 5 5 23 6 11 7 35 8 17 9 43 10 59 11 59 12 35 13 83 14 41 15 91 16 103 17 119 18 119 19 65 20 143 21 143 22 77 23 163 24 77 25 95 26 203 27 101 28 215 29 107 30 191 31 125 32 259 33 275 34 263 35 299 36 299 37 311 38 161 39 331 40 343 41 359 42 347 43 383 44 191 45 395 46 169 47 181 48 221 49 455 50 227 51 463 52 479 53 467 54 499 55 511 56 523 57 539 58 539 59 275 60 563 61 551 62 551 63 305 64 623 65 311 66 599 67 659 68 659 69 695 70 347 71 703 72 347 73 731 74 743 75 377 76 763 77 377 78 395 79 389 80 803 81 839 82 827 83 863 84 863 85 437 86 883 87 437 88 455 89 923 90 461 91 437 92 467 93 485 94 479 95 497 96 1003 97 479 98 1043 99 983 100 1079 101 1079 102 1111 103 1123 104 1139 105 1139 106 1139 107 1171 108 1183 109 1199 110 1199 111 1211 112 611 113 1235 114 589 115 1247 116 1283 117 641 118 1291 119 1303 120 1319 121 631 122 671 123 1351 124 671 125 1367 126 689 127 1403 128 707 129 1451 130 1463 131 737 132 731 133 1499 134 755 135 749 136 767 137 1511 138 1559 139 767 140 1619 141 1607 142 1643 143 821 144 1655 145 1643 146 1643 147 851 148 1715 149 857 150 1691 151 875 152 1763 153 881 154 797 155 905 156 899 157 1823 158 917 159 935 160 1879 161 1891 162 1871 163 965 164 1939 165 1951 166 971 167 1979 168 967 169 1007 170 2023 171 2039 172 2027 173 2063 174 2063 175 2063 176 2099 177 2087 178 2123 179 2123 180 2075 181 1085 182 2183 183 1091 184 2191 185 2203 186 1097 187 2231 188 2243 189 2159 190 2303 191 2291 192 1151 193 2327 194 2359 195 2371 196 1181 197 1171 198 1211 199 2431 200 2443 201 2459 202 2459 203 1207 204 2483 205 2455 206 2555 207 1277 208 2563 209 2579 210 2579 211 1295 212 2603 213 1301 214 1277 215 2639 216 2639 217 2399 218 2719 219 2731 220 1361 221 2699 222 2783 223 2783 224 1421 225 2855 226 1427 227 2863 228 1427 229 1445 230 2903 231 2903 232 1429 233 2927 234 2963 235 1481 236 2975 237 1487 238 2983 239 1469 240 1481 241 1511 242 1501 243 3083 244 1547 245 3103 246 1547 247 1565 248 1559 249 1577 250 3131 251 1595 252 3199 253 3215 254 1607 255 3223 256 3239 257 3239 258 3239 259 1547 260 3311 261 1661 262 3335 263 1537 264 1691 265 3395 266 3383 267 1679 268 3443 269 3431 270 1721 271 3479 272 3491 273 3503 274 3455 275 3551 276 1781 277 3575 278 1759 279 3587 280 1781 281 1811 282 1775 283 3659 284 3719 285 1865 286 3743 287 1871 288 3755 289 3743 290 1859 291 3799 292 3811 293 3763 294 3863 295 1877 296 3899 297 3803 298 3943 299 1967 300 3971 301 1991 302 3995 303 1997 304 1991 305 4019 306 4019 307 4055 308 4043 309 4043 310 4091 311 4123 312 2039 313 4163 314 2081 315 4175 316 4163 317 2069 318 4223 319 2057 320 4259 321 4259 322 2135 323 4283 324 4271 325 2141 326 4259 327 2047 328 2201 329 4411 330 2201 331 2165 332 4475 333 2237 334 2231 335 2195 336 4535 337 2267 338 2261 339 4559 340 4571 341 2291 342 2267 343 4619 344 4523 345 4663 346 4679 347 4679 348 2345 349 4699 350 4679 351 4739 352 2375 353 4763 354 4763 355 2387 356 4783 357 2369 358 4819 359 4831 360 4811 361 2435 362 4879 363 2417 364 2447 365 4931 366 2471 367 4811 368 4943 369 5027 370 2519 371 2537 372 5083 373 5099 374 5099 375 5015 376 2549 377 5183 378 2537 379 2597 380 2615 381 2591 382 5231 383 5279 384 5315 385 2657 386 2651 387 5339 388 5351 389 2681 390 5375 391 2687 392 5383 393 2687 394 2705 395 5423 396 5423 397 5423 398 5459 399 5447 400 2729 401 2747 402 5471 403 5519 404 2747 405 5579 406 5579 407 2795 408 5603 409 2747 410 5603 411 2831 412 5671 413 2831 414 5699 415 2855 416 5659 417 2867 418 5759 419 5791 420 5803 421 2897 422 5819 423 2897 424 5843 425 2951 426 5911 427 5923 428 5939 429 2789 430 5999 431 5987 432 2999 433 3017 434 6011 435 3035 436 3029 437 3019 438 6119 439 3037 440 3077 441 6163 442 2999 443 6203 444 6239 445 3065 446 6131 447 3161 448 6335 449 3139 450 6359 451 3185 452 3161 453 6403 454 3197 455 3215 456 3209 457 6359 458 6503 459 3251 460 6515 461 3229 462 3089 463 6599 464 6599 465 6611 466 6623 467 3317 468 6643 469 6659 470 3301 471 3341 472 3317 473 6719 474 6707 475 6743 476 3317 477 6779 478 3335 479 6811 480 3323 481 3377 482 3437 483 3455 484 6923 485 3461 486 6935 487 6839 488 3479 489 3469 490 7019 491 7019 492 7055 493 3527 494 7063 495 7079 496 7079 497 7079 498 7115 499 3529 500 7127 501 7163 502 7151 503 7151 504 7211 505 3611 506 7231 507 3611 508 7259 509 7271 510 3587 511 3629 512 7343 513 3671 514 7319 515 7379 516 3695 517 3689 518 7403 519 3707 520 7451 521 7463 522 7379 523 7519 524 7535 525 7523 526 7523 527 3791 528 7591 529 7543 530 7643 531 7631 532 7631 533 3845 534 7703 535 7691 536 7691 537 3875 538 3869 539 7715 540 3905 541 7819 542 7835 543 3917 544 7843 545 7859 546 3901 547 3941 548 3857 549 7835 550 3959 551 8003 552 4001 553 8011 554 8023 555 8039 556 8039 557 7955 558 8099 559 8099 560 4001 561 8143 562 4049 563 8183 564 8183 565 4069 566 4055 567 8255 568 4127 569 8263 570 8243 571 4151 572 8315 573 8255 574 4045 575 8387 576 8419 577 8435 578 8423 579 8459 580 8447 581 8483 582 8471 583 8503 584 8519 585 8507 586 8543 587 8531 588 8563 589 4277 590 8399 591 8639 592 8675 593 8663 594 4337 595 8711 596 8711 597 8683 598 8779 599 4367 600 4379 601 8843 602 8783 603 8879 604 4445 605 8899 606 8911 607 8863 608 8963 609 8951 610 8951 611 9011 612 4511 613 9035 614 4517 615 4391 616 9095 617 4519 618 9119 619 4511 620 4571 621 9179 622 9191 623 9143 624 4565 625 9275 626 4637 627 9283 628 9299 629 9299 630 9311 631 9311 632 9343 633 4649 634 4661 635 9343 636 9443 637 9443 638 4727 639 9403 640 4739 641 4627 642 4781 643 9575 644 4787 645 9583 646 9599 647 4771 648 4811 649 9599 650 9467 651 9707 652 9739 653 4847 654 9743 655 9803 656 9803 657 4889 658 9863 659 4931 660 9871 661 4931 662 9899 663 9899 664 9935 665 4967 666 9911 667 9971 668 9983 669 4997 670 10003 671 10019 672 10007 673 10043 674 4967 675 5009 676 5039 677 10055 678 5075 679 10159 680 5057 681 10199 682 10199 683 10211 684 10223 685 4937 686 10291 687 10271 688 5165 689 5159 690 10343 691 5177 692 5167 693 10355 694 5225 695 10463 696 5231 697 5105 698 5231 699 10543 700 10559 701 5225 702 10591 703 10603 704 10583 705 10631 706 10631 707 5345 708 10507 709 10759 710 10771 711 10783 712 5387 713 10811 714 5411 715 10835 716 5389 717 10859 718 5435 719 10883 720 10883 721 10799 722 10939 723 10955 724 5477 725 10903 726 11003 727 5501 728 5477 729 11039 730 11039 731 5525 732 10919 733 11111 734 11123 735 5567 736 5561 737 11147 738 5351 739 5567 740 11279 741 11279 742 5645 743 11303 744 5651 745 11315 746 11303 747 11303 748 11363 749 5687 750 5681 751 11387 752 11419 753 5627 754 5735 755 11483 756 11483 757 11303 758 5777 759 5771 760 11567 761 11599 762 11611 763 5801 764 11639 765 5797 766 5837 767 11683 768 11699 769 11699 770 5855 771 11719 772 11735 773 11723 774 11759 775 5825 776 11791 777 5813 778 5921 779 5897 780 11843 781 5771 782 11959 783 5897 784 6005 785 11959 786 6017 787 12071 788 6041 789 12091 790 12071 791 12131 792 12143 793 12143 794 12179 795 12167 796 6071 797 6101 798 12227 799 12263 800 12251 801 6131 802 6121 803 12311 804 6041 805 12395 806 6197 807 6191 808 12419 809 6215 810 6209 811 12395 812 12479 813 12511 814 12523 815 12539 816 12539 817 12539 818 6257 819 12599 820 12587 821 12619 822 12631 823 12643 824 6317 825 12671 826 12671 827 12703 828 12719 829 12719 830 12731 831 12743 832 12743 833 6377 834 6265 835 12839 836 12755 837 12899 838 12839 839 6467 840 6461 841 12947 842 12787 843 6509 844 12995 845 6545 846 13103 847 13091 848 13123 849 13139 850 13139 851 6575 852 13099 853 6587 854 6577 855 13175 856 6581 857 13303 858 13319 859 6631 860 13343 861 13343 862 13379 863 13367 864 13403 865 13403 866 13403 867 13403 868 6731 869 6605 870 13523 871 6707 872 13559 873 13547 874 13583 875 13571 876 6713 877 6821 878 13655 879 6827 880 6821 881 6785 882 13711 883 13723 884 13739 885 6841 886 6827 887 6887 888 6905 889 13819 890 13639 891 13895 892 13883 893 13919 894 13919 895 6965 896 13939 897 13951 898 6971 899 13979 900 6995 901 6971 902 14023 903 7007 904 6997 905 7037 906 14051 907 7027 908 14123 909 6947 910 14203 911 7079 912 14239 913 14255 914 14159 915 7139 916 14255 917 14339 918 14371 919 14351 920 7205 921 14423 922 14423 923 14423 924 7217 925 14471 926 7241 927 14491 928 14311 929 14531 930 14579 931 14615 932 7279 933 14627 934 14663 935 7277 936 14699 937 14639 938 7237 939 14723 940 14819 941 7361 942 14803 943 14899 944 14915 945 14855 946 7475 947 14959 948 14975 949 14963 950 7487 951 14999 952 15031 953 15043 954 7517 955 7535 956 15079 957 15095 958 15083 959 15119 960 7531 961 7571 962 15151 963 15163 964 15179 965 7561 966 7601 967 15179 968 15179 969 7637 970 15283 971 7559 972 7667 973 7661 974 15359 975 7685 976 7679 977 7697 978 15371 979 15431 980 7721 981 15419 982 7711 983 7751 984 15515 985 15323 986 7787 987 7661 988 15631 989 15643 990 7799 991 7811 992 15671 993 15731 994 7871 995 15755 996 7877 997 15703 998 15799 999 7877 1000 7907