1 1 2 3 3 5 4 7 5 32 6 11 7 13 8 17 9 19 10 25 11 23 12 224 13 29 14 31 15 128 16 37 17 41 18 43 19 115 20 47 21 119 22 53 23 81 24 928 25 59 26 61 27 256 28 67 29 71 30 73 31 79 32 187 33 83 34 203 35 89 36 209 37 235 38 97 39 101 40 103 41 1696 42 107 43 109 44 121 45 113 46 295 47 287 48 127 49 512 50 131 51 299 52 137 53 139 54 319 55 323 56 149 57 151 58 157 59 1408 60 163 61 415 62 167 63 1376 64 173 65 413 66 391 67 179 68 181 69 1504 70 191 71 193 72 197 73 199 74 3232 75 515 76 901 77 211 78 535 79 2592 80 575 81 223 82 3712 83 227 84 229 85 517 86 233 87 1501 88 239 89 241 90 581 91 251 92 551 93 257 94 583 95 263 96 623 97 269 98 271 99 289 100 277 101 281 102 283 103 1843 104 649 105 293 106 343 107 4768 108 707 109 307 110 667 111 311 112 313 113 317 114 749 115 2816 116 815 117 2656 118 331 119 835 120 337 121 361 122 5536 123 347 124 349 125 353 126 895 127 359 128 779 129 1537 130 367 131 799 132 373 133 379 134 955 135 383 136 3584 137 389 138 869 139 6304 140 397 141 401 142 409 143 913 144 893 145 6784 146 419 147 421 148 3424 149 431 150 433 151 439 152 943 153 443 154 1043 155 449 156 2869 157 1135 158 457 159 461 160 463 161 1003 162 467 163 1007 164 1195 165 479 166 1067 167 487 168 491 169 1079 170 499 171 625 172 503 173 2117 174 529 175 509 176 1133 177 2048 178 1211 179 521 180 523 181 1315 182 1139 183 1177 184 1253 185 8608 186 541 187 17536 188 547 189 4448 190 557 191 1207 192 563 193 1415 194 569 195 571 196 1219 197 577 198 1475 199 9376 200 587 201 1379 202 593 203 1863 204 599 205 601 206 607 207 613 208 617 209 619 210 1555 211 1343 212 631 213 10144 214 1391 215 1357 216 641 217 643 218 1363 219 647 220 5216 221 653 222 1411 223 659 224 661 225 5344 226 4237 227 673 228 677 229 1589 230 1507 231 683 232 1805 233 2941 234 691 235 1735 236 1631 237 701 238 6399 239 5888 240 709 241 5728 242 1673 243 1795 244 719 245 3077 246 727 247 49184 248 733 249 6016 250 739 251 1639 252 743 253 11936 254 751 255 757 256 761 257 1915 258 769 259 1633 260 773 261 12448 262 1643 263 3349 264 787 265 1679 266 797 267 12928 268 1883 269 809 270 811 271 841 272 1751 273 821 274 823 275 827 276 829 277 1837 278 13568 279 2095 280 839 281 1763 282 5377 283 1819 284 853 285 857 286 859 287 1903 288 863 289 7857 290 1829 291 877 292 881 293 883 294 2215 295 887 296 7136 297 1969 298 14848 299 1919 300 1909 301 7264 302 907 303 911 304 3893 305 919 306 1927 307 1943 308 929 309 961 310 2335 311 937 312 941 313 947 314 2219 315 953 316 2033 317 2395 318 2123 319 967 320 971 321 2435 322 977 323 2167 324 983 325 18592 326 991 327 997 328 8032 329 2515 330 1009 331 1013 332 16288 333 1019 334 1021 335 4096 336 29241 337 1031 338 1033 339 4321 340 1039 341 2227 342 2183 343 1049 344 1051 345 2231 346 1061 347 1063 348 1069 349 4573 350 2513 351 3321 352 1087 353 35072 354 1091 355 1093 356 1097 357 6973 358 2323 359 1103 360 2363 361 1109 362 2453 363 17824 364 1117 365 9088 366 1123 367 2815 368 1129 369 2497 370 7009 371 9673 372 2483 373 4717 374 2681 375 2407 376 1151 377 1153 378 2419 379 1163 380 2723 381 2461 382 4981 383 1171 384 2935 385 10976 386 1181 387 19072 388 1187 389 2507 390 2629 391 1193 392 2491 393 1201 394 5017 395 1331 396 1213 397 1217 398 2537 399 1223 400 2603 401 1229 402 1231 403 2599 404 1237 405 9952 406 3807 407 1249 408 2933 409 1259 410 2627 411 5389 412 23968 413 1277 414 1279 415 2827 416 1283 417 3215 418 1289 419 1291 420 3235 421 1297 422 1301 423 1303 424 20896 425 1307 426 2893 427 10624 428 8341 429 3295 430 1319 431 1321 432 1327 433 2839 434 13561 435 1369 436 2773 437 2959 438 3143 439 12231 440 21664 441 2951 442 1361 443 3415 444 1367 445 8683 446 1373 447 22144 448 1381 449 11104 450 2921 451 5933 452 1399 453 22432 454 4293 455 1409 456 3113 457 22688 458 1423 459 3043 460 1427 461 1429 462 3013 463 1433 464 3353 465 3595 466 1439 467 17557 468 1447 469 1451 470 1453 471 5989 472 1459 473 3223 474 11744 475 1471 476 12032 477 3071 478 1481 479 1483 480 3103 481 1487 482 1489 483 1493 484 3173 485 3151 486 1499 487 3263 488 3521 489 3127 490 1511 491 12128 492 3149 493 3247 494 1523 495 3563 496 12256 497 1531 498 14336 499 3509 500 1543 501 24736 502 1549 503 1553 504 9589 505 1559 506 3239 507 1567 508 25216 509 1571 510 3419 511 1579 512 3487 513 1583 514 3383 515 3317 516 25504 517 1597 518 1601 519 3401 520 1607 521 1609 522 3337 523 1613 524 13753 525 1619 526 1621 527 6757 528 1627 529 3427 530 9991 531 1637 532 10033 533 1681 534 4115 535 3473 536 4135 537 1657 538 4175 539 1663 540 27136 541 1667 542 1669 543 13408 544 4195 545 3503 546 3941 547 1693 548 1697 549 1699 550 3983 551 1709 552 3629 553 14569 554 3551 555 1721 556 1723 557 4315 558 15633 559 3817 560 1733 561 1741 562 1747 563 17821 564 1753 565 1759 566 3883 567 3743 568 7261 569 4435 570 1777 571 4475 572 1783 573 1787 574 1789 575 3949 576 7453 577 3713 578 1801 579 9545 580 1849 581 3859 582 1811 583 4535 584 11533 585 3763 586 1823 587 22213 588 3841 589 1831 590 4595 591 7837 592 1847 593 3827 594 11761 595 15104 596 1861 597 14944 598 1867 599 1871 600 1873 601 1877 602 1879 603 30112 604 3901 605 1889 606 4169 607 3979 608 71008 609 1901 610 4063 611 1907 612 3959 613 4213 614 1913 615 3953 616 4487 617 7897 618 12217 619 1931 620 1933 621 4529 622 4279 623 15584 624 1949 625 1951 626 125056 627 4571 628 4117 629 8077 630 4915 631 9877 632 1973 633 4613 634 1979 635 4163 636 1987 637 1993 638 1997 639 1999 640 4267 641 2003 642 16096 643 2011 644 2017 645 4183 646 2027 647 2029 648 4189 649 8653 650 4313 651 5095 652 2039 653 4223 654 8497 655 4781 656 8192 657 2053 658 2401 659 5155 660 2063 661 17561 662 2069 663 9823 664 138272 665 4511 666 2081 667 2083 668 2087 669 2089 670 4393 671 4471 672 2099 673 4343 674 12877 675 2111 676 2113 677 4387 678 5315 679 2129 680 2131 681 4399 682 2137 683 2141 684 2143 685 34432 686 4667 687 2153 688 5033 689 4531 690 2161 691 2209 692 22081 693 5435 694 70144 695 2179 696 5455 697 9077 698 4829 699 18649 700 13579 701 8989 702 2203 703 5515 704 2207 705 4559 706 4873 707 2213 708 6723 709 35488 710 2221 711 9469 712 4601 713 27229 714 2237 715 2239 716 4939 717 2243 718 5615 719 18016 720 2251 721 4811 722 5675 723 4661 724 2267 725 2269 726 2273 727 2281 728 2287 729 20723 730 2293 731 2297 732 4747 733 4883 734 2309 735 2311 736 5411 737 11033 738 4843 739 87136 740 5137 741 2333 742 37504 743 2339 744 2341 745 18784 746 2347 747 2351 748 5831 749 2357 750 4997 751 37792 752 38144 753 2371 754 5935 755 2377 756 4897 757 2381 758 2383 759 20281 760 2389 761 5269 762 2393 763 15523 764 2399 765 9797 766 160544 767 2411 768 5111 769 2417 770 6655 771 2423 772 5663 773 5357 774 623104 775 2437 776 5029 777 2441 778 5129 779 6115 780 2447 781 5219 782 39328 783 2459 784 5063 785 10237 786 2467 787 25021 788 2473 789 2477 790 5789 791 5287 792 5123 793 5221 794 5177 795 5191 796 10229 797 3125 798 2503 799 5267 800 5533 801 5873 802 6295 803 2521 804 40576 805 2531 806 2539 807 5599 808 2543 809 12733 810 2549 811 2551 812 5251 813 2557 814 22528 815 15781 816 6415 817 5999 818 15721 819 5311 820 2579 821 5363 822 20704 823 6041 824 2591 825 2593 826 41632 827 6515 828 2609 829 5753 830 6535 831 2617 832 5497 833 2621 834 21248 835 5567 836 2633 837 6595 838 5543 839 2647 840 5459 841 2657 842 2659 843 5539 844 2663 845 10877 846 13865 847 2671 848 2677 849 11029 850 2683 851 2687 852 2689 853 2693 854 2699 855 8181 856 11509 857 2707 858 2711 859 2713 860 11281 861 2719 862 174208 863 2729 864 2731 865 6835 866 6137 867 2741 868 43936 869 2749 870 5773 871 2753 872 16789 873 2809 874 5699 875 2767 876 5899 877 5771 878 2777 879 6127 880 5723 881 2789 882 2791 883 2797 884 2801 885 2803 886 25353 887 6193 888 5911 889 2819 890 6587 891 2833 892 2837 893 6629 894 6259 895 2843 896 6023 897 22912 898 2851 899 7135 900 2857 901 2861 902 8667 903 6103 904 6227 905 5893 906 23008 907 7195 908 2879 909 6347 910 6049 911 2887 912 7235 913 2897 914 5969 915 5959 916 2903 917 23264 918 2909 919 6797 920 196736 921 2917 922 12013 923 2927 924 6239 925 6457 926 2939 927 6107 928 24064 929 6881 930 6187 931 2953 932 2957 933 6077 934 6523 935 2963 936 7415 937 2969 938 2971 939 7435 940 36181 941 47776 942 6179 943 6157 944 6647 945 7495 946 2999 947 3001 948 3011 949 6539 950 12349 951 3019 952 7555 953 3023 954 6443 955 6677 956 3037 957 3041 958 7615 959 3049 960 7133 961 6511 962 3061 963 3067 964 28672 965 6313 966 3079 967 6319 968 3083 969 7715 970 3089 971 6809 972 105877 973 12629 974 31411 975 6509 976 49792 977 3109 978 6593 979 7795 980 3119 981 3121 982 6439 983 6431 984 3137 985 7855 986 7343 987 19177 988 7895 989 12997 990 3163 991 6583 992 3167 993 3169 994 3181 995 13549 996 3187 997 3191 998 13253 999 6557 1000 51712