1 0 2 0 3 0 4 17 5 19 6 31 7 53 8 29 9 31 10 0 11 83 12 41 13 43 14 67 15 71 16 97 17 53 18 173 19 223 20 349 21 337 22 67 23 337 24 71 25 109 26 113 27 79 28 359 29 239 30 89 31 0 32 139 33 97 34 193 35 101 36 103 37 157 38 109 39 367 40 113 41 383 42 443 43 293 44 761 45 127 46 1021 47 131 48 199 49 137 50 139 51 211 52 353 53 149 54 151 55 647 56 659 57 311 58 239 59 163 60 1117 61 251 62 337 63 173 64 593 65 683 66 181 67 619 68 541 69 1439 70 643 71 191 72 383 73 197 74 199 75 1723 76 503 77 311 78 211 79 1013 80 1123 81 2287 82 223 83 337 84 229 85 457 86 233 87 1021 88 811 89 239 90 241 91 1609 92 1297 93 2267 94 1657 95 251 96 379 97 257 98 1367 99 1499 100 1867 101 4327 102 269 103 271 104 409 105 683 106 281 107 283 108 1109 109 1777 110 1129 111 2447 112 293 113 2617 114 2767 115 743 116 1889 117 307 118 1637 119 311 120 1373 121 317 122 2693 123 1103 124 2161 125 487 126 491 127 331 128 499 129 337 130 673 131 1009 132 1181 133 2161 134 349 135 4463 136 353 137 1223 138 3361 139 2423 140 1597 141 367 142 2137 143 3967 144 373 145 3037 146 2887 147 379 148 571 149 953 150 389 151 967 152 2467 153 983 154 401 155 997 156 5197 157 3659 158 409 159 1619 160 2411 161 3001 162 2243 163 419 164 631 165 1259 166 3677 167 1481 168 431 169 433 170 2339 171 2143 172 439 173 2999 174 443 175 887 176 449 177 2423 178 2003 179 4969 180 461 181 463 182 1381 183 701 184 937 185 2089 186 1873 187 2113 188 1193 189 2137 190 487 191 2857 192 491 193 2887 194 4507 195 3847 196 499 197 751 198 1499 199 1009 200 509 201 2017 202 769 203 773 204 1033 205 521 206 523 207 787 208 1571 209 2351 210 12289 211 2113 212 2383 213 5189 214 3187 215 547 216 3217 217 2441 218 829 219 557 220 2207 221 6659 222 4373 223 569 224 571 225 3359 226 2549 227 577 228 5303 229 4517 230 3433 231 877 232 881 233 5147 234 593 235 2063 236 3229 237 599 238 601 239 10663 240 7247 241 607 242 4177 243 4483 244 919 245 617 246 619 247 3659 248 1553 249 941 250 631 251 5813 252 953 253 2833 254 641 255 643 256 2239 257 647 258 3203 259 3529 260 653 261 5737 262 4513 263 659 264 991 265 1979 266 5527 267 1993 268 2657 269 1009 270 677 271 2687 272 2029 273 683 274 7607 275 4057 276 6367 277 691 278 1039 279 1733 280 701 281 1747 282 6833 283 709 284 7873 285 3169 286 2833 287 2843 288 4937 289 18719 290 2161 291 727 292 6047 293 3967 294 2549 295 1103 296 739 297 3659 298 743 299 1117 300 4057 301 751 302 4447 303 6271 304 1511 305 761 306 3023 307 3407 308 769 309 8209 310 773 311 2693 312 3083 313 2711 314 2719 315 2341 316 787 317 10253 318 4297 319 1583 320 797 321 3167 322 1201 323 3187 324 1609 325 809 326 811 327 6763 328 8329 329 2843 330 821 331 823 332 4079 333 827 334 829 335 3299 336 5741 337 6961 338 8969 339 7001 340 5399 341 3769 342 8273 343 7487 344 853 345 7121 346 857 347 859 348 1291 349 2153 350 1301 351 3877 352 3461 353 8117 354 3911 355 881 356 883 357 1327 358 5683 359 1777 360 5717 361 7879 362 4003 363 2687 364 1801 365 4919 366 907 367 3163 368 911 369 1823 370 1373 371 919 372 1381 373 15473 374 929 375 8191 376 1399 377 937 378 1873 379 941 380 6949 381 12781 382 947 383 4703 384 5179 385 953 386 5669 387 5683 388 1439 389 3823 390 6661 391 967 392 3373 393 971 394 1459 395 977 396 17351 397 1471 398 3907 399 3917 400 2953 401 991 402 3457 403 5903 404 14947 405 1499 406 10771 407 6451 408 1009 409 2017 410 1013 411 3533 412 6529 413 1021 414 3559 415 3061 416 12011 417 3583 418 1031 419 1033 420 5641 421 5653 422 1039 423 16607 424 7219 425 1049 426 1051 427 11321 428 6257 429 4201 430 4211 431 1061 432 1063 433 5807 434 20483 435 1069 436 8969 437 7949 438 9007 439 15199 440 12671 441 1621 442 7499 443 1087 444 3253 445 1091 446 7027 447 1097 448 6521 449 3833 450 1103 451 6563 452 6577 453 1109 454 11447 455 1669 456 1117 457 4447 458 8297 459 1123 460 9967 461 1129 462 5051 463 6173 464 4513 465 4523 466 2843 467 5107 468 2857 469 10159 470 1151 471 5153 472 1733 473 13577 474 3469 475 1163 476 6353 477 4643 478 9227 479 1171 480 1759 481 6991 482 6427 483 1181 484 6451 485 1777 486 4139 487 2377 488 1193 489 9431 490 12919 491 8887 492 12973 493 5981 494 7177 495 22741 496 2423 497 1217 498 10789 499 4253 500 1223 501 2447 502 1229 503 1231 504 9133 505 3083 506 14537 507 15749 508 22787 509 5573 510 1249 511 11689 512 7451 513 14149 514 6863 515 1259 516 4397 517 3779 518 5039 519 3793 520 7559 521 6947 522 6959 523 1277 524 1279 525 5101 526 3203 527 1289 528 1291 529 5779 530 1297 531 2593 532 1301 533 1303 534 5839 535 3911 536 2617 537 11003 538 4583 539 9767 540 9787 541 7867 542 1327 543 11779 544 8563 545 7927 546 11197 547 10567 548 11887 549 11257 550 13879 551 2017 552 11317 553 21683 554 2029 555 12037 556 2713 557 1361 558 4751 559 6781 560 4091 561 6131 562 1373 563 4793 564 4801 565 8209 566 4817 567 4139 568 5519 569 4153 570 21701 571 7607 572 11717 573 9689 574 1399 575 5581 576 6977 577 4903 578 1409 579 4919 580 7717 581 14639 582 4943 583 2129 584 1423 585 4261 586 1427 587 1429 588 7817 589 1433 590 7841 591 12781 592 5021 593 5743 594 14947 595 1447 596 23339 597 1451 598 2179 599 5077 600 1459 601 17231 602 5101 603 2927 604 4391 605 1471 606 14519 607 12391 608 9521 609 1481 610 1483 611 17509 612 1489 613 9601 614 1493 615 5953 616 24809 617 1499 618 2251 619 11903 620 8971 621 4513 622 1511 623 2269 624 2273 625 6047 626 2281 627 6067 628 3049 629 9851 630 1531 631 5347 632 13649 633 10667 634 2309 635 1543 636 6917 637 1549 638 6173 639 1553 640 6961 641 5431 642 1559 643 16921 644 16189 645 11633 646 1567 647 15497 648 1571 649 6269 650 11717 651 1579 652 4729 653 1583 654 8663 655 6323 656 11813 657 8699 658 2389 659 1597 660 6367 661 1601 662 5591 663 18191 664 1607 665 1609 666 22937 667 1613 668 9629 669 9643 670 11251 671 26987 672 1627 673 13693 674 17683 675 8923 676 13751 677 1637 678 9769 679 17011 680 6551 681 50441 682 6571 683 10657 684 4133 685 8243 686 1663 687 7451 688 1667 689 1669 690 6659 691 18947 692 12451 693 13291 694 5861 695 3361 696 15817 697 16661 698 11731 699 12577 700 1693 701 13441 702 1697 703 1699 704 11821 705 16843 706 2557 707 1709 708 14401 709 7673 710 4283 711 1721 712 1723 713 8573 714 2591 715 3457 716 1733 717 6053 718 23041 719 23911 720 1741 721 12109 722 9547 723 1747 724 12157 725 13033 726 10459 727 2633 728 1759 729 10499 730 5279 731 7039 732 19207 733 2659 734 1777 735 7963 736 11483 737 1783 738 6229 739 1787 740 1789 741 52501 742 9811 743 10709 744 15139 745 30829 746 1801 747 31771 748 36109 749 26647 750 21433 751 1811 752 2719 753 6337 754 7247 755 2731 756 9973 757 15377 758 21647 759 1831 760 6397 761 27061 762 3671 763 5507 764 10987 765 5521 766 1847 767 13759 768 19211 769 10139 770 10151 771 16561 772 1861 773 19333 774 5581 775 1867 776 72893 777 1871 778 16703 779 1877 780 1879 781 8429 782 7507 783 3769 784 1889 785 6599 786 7547 787 2843 788 3793 789 1901 790 21599 791 2857 792 2861 793 11393 794 1913 795 21737 796 6691 797 10501 798 10513 799 15263 800 23743 801 15299 802 13417 803 1931 804 3863 805 2903 806 7727 807 8699 808 11593 809 3889 810 1949 811 1951 812 9721 813 6827 814 25097 815 5869 816 17497 817 14627 818 6869 819 8831 820 1973 821 7873 822 14717 823 1979 824 2971 825 5939 826 1987 827 5953 828 6949 829 13859 830 1997 831 1999 832 6983 833 2003 834 10973 835 12967 836 19891 837 2011 838 24847 839 16993 840 7043 841 6047 842 11069 843 3037 844 2029 845 4057 846 15131 847 7103 848 8123 849 18191 850 9157 851 5107 852 18257 853 27277 854 2053 855 31319 856 22367 857 12289 858 8221 859 5153 860 2069 861 5167 862 22531 863 12377 864 9311 865 2081 866 2083 867 12437 868 2087 869 2089 870 11447 871 16619 872 11471 873 48049 874 54059 875 19793 876 9439 877 33161 878 2111 879 2113 880 18869 881 15767 882 32327 883 3181 884 5303 885 2129 886 2131 887 8501 888 29453 889 4271 890 2141 891 2143 892 6421 893 14929 894 36923 895 11777 896 2153 897 11801 898 11813 899 12893 900 2161 901 17189 902 16139 903 32051 904 20441 905 31063 906 3259 907 10837 908 2179 909 3271 910 9791 911 8719 912 38707 913 30269 914 8753 915 16361 916 32503 917 2203 918 3307 919 20773 920 7717 921 2213 922 21929 923 23039 924 2221 925 4441 926 6661 927 51071 928 16607 929 14423 930 4463 931 2237 932 2239 933 6709 934 2243 935 10069 936 3371 937 2251 938 19001 939 7873 940 14591 941 3389 942 15739 943 6781 944 2267 945 2269 946 9059 947 2273 948 24781 949 12473 950 13613 951 2281 952 18149 953 60107 954 2287 955 38329 956 21601 957 2293 958 22769 959 2297 960 32933 961 9181 962 22853 963 2309 964 2311 965 9221 966 24077 967 9241 968 33191 969 13859 970 13873 971 9277 972 3491 973 4657 974 2333 975 28859 976 8161 977 2339 978 3511 979 7019 980 2347 981 11699 982 2351 983 17539 984 12899 985 2357 986 12923 987 3541 988 7079 989 4729 990 12973 991 2371 992 3559 993 2377 994 10667 995 2381 996 2383 997 20129 998 2389 999 30713 1000 2393