0 3 1 5 2 7 3 11 4 13 5 17 6 19 7 23 8 41 9 31 10 29 11 37 12 47 13 83 14 43 15 107 16 53 17 151 18 101 19 89 20 71 21 97 22 79 23 59 24 61 25 139 26 173 27 313 28 163 29 127 30 113 31 73 32 311 33 283 34 193 35 157 36 131 37 239 38 103 39 443 40 197 41 541 42 257 43 431 44 229 45 401 46 887 47 241 48 191 49 397 50 353 51 463 52 109 53 421 54 227 55 433 56 631 57 167 58 181 59 409 60 251 61 359 62 137 63 367 64 337 65 1093 66 293 67 1181 68 179 69 373 70 467 71 811 72 269 73 461 74 797 75 853 76 211 77 1021 78 149 79 641 80 479 81 331 82 571 83 757 84 419 85 601 86 947 87 271 88 521 89 547 90 263 91 647 92 457 93 659 94 281 95 859 96 389 97 1163 98 307 99 683 100 317 101 491 102 223 103 1013 104 1171 105 509 106 233 107 1051 108 569 109 739 110 691 111 863 112 593 113 1667 114 499 115 881 116 743 117 661 118 991 119 199 120 761 121 449 122 1259 123 709 124 1151 125 349 126 911 127 613 128 1307 129 1531 130 809 131 1549 132 563 133 1033 134 977 135 643 136 1669 137 523 138 719 139 1783 140 877 141 1097 142 607 143 823 144 617 145 1123 146 1213 147 1433 148 787 149 1597 150 503 151 1913 152 1279 153 557 154 829 155 1031 156 997 157 1201 158 379 159 1847 160 1193 161 1061 162 883 163 1399 164 733 165 587 166 907 167 2099 168 1429 169 599 170 1951 171 1811 172 769 173 1999 174 1481 175 619 176 1493 177 277 178 2393 179 1187 180 1153 181 1019 182 983 183 1579 184 1733 185 487 186 1373 187 1619 188 2141 189 2017 190 1973 191 701 192 67 193 1091 194 1237 195 1103 196 857 197 1901 198 673 199 919 200 2081 201 2341 202 1699 203 2767 204 1109 205 941 206 3797 207 4483 208 2381 209 1381 210 929 211 2447 212 3701 213 2689 214 3089 215 3361 216 1607 217 3167 218 2719 219 347 220 2293 221 3011 222 1873 223 1249 224 1439 225 2161 226 1229 227 1949 228 1471 229 1277 230 1483 231 827 232 3581 233 2011 234 1499 235 1321 236 1039 237 383 238 1283 239 2063 240 577 241 2797 242 1559 243 3301 244 1823 245 1117 246 2819 247 1627 248 2837 249 2143 250 2357 251 2663 252 1621 253 4451 254 2153 255 2437 256 2683 257 2971 258 1931 259 2213 260 1427 261 2749 262 2753 263 3559 264 1721 265 1459 266 2531 267 1741 268 3083 269 1759 270 3371 271 2591 272 1217 273 967 274 677 275 1523 276 1789 277 2089 278 4027 279 1553 280 2087 281 3533 282 1543 283 6947 284 1289 285 2131 286 1301 287 7309 288 1907 289 6763 290 3677 291 3307 292 1657 293 3617 294 1087 295 4813 296 4363 297 3359 298 1409 299 2179 300 821 301 2791 302 3853 303 1601 304 2351 305 4969 306 2069 307 2843 308 1777 309 2549 310 2411 311 3187 312 2741 313 2267 314 2129 315 2281 316 1511 317 2927 318 3433 319 2309 320 4091 321 3613 322 1861 323 7829 324 1567 325 2333 326 2557 327 1367 328 2897 329 1709 330 2251 331 2383 332 937 333 4391 334 953 335 3067 336 1637 337 6451 338 4703 339 4111 340 3709 341 1747 342 2699 343 2789 344 2027 345 1423 346 653 347 3511 348 1361 349 6317 350 2083 351 4937 352 3863 353 7433 354 1063 355 3907 356 2857 357 4283 358 3593 359 5023 360 3257 361 5407 362 3643 363 6521 364 1487 365 3623 366 1867 367 1069 368 2243 369 1447 370 773 371 1453 372 4127 373 4079 374 4523 375 727 376 2657 377 2621 378 2671 379 1877 380 3823 381 2273 382 2311 383 4583 384 2713 385 2677 386 3499 387 2693 388 4679 389 4657 390 1583 391 3109 392 1987 393 2729 394 3181 395 3929 396 2803 397 9901 398 2039 399 3547 400 2053 401 24413 402 2521 403 3121 404 2939 405 2731 406 2953 407 4373 408 4603 409 10939 410 3001 411 4397 412 3019 413 6067 414 971 415 5669 416 5147 417 4861 418 3917 419 4463 420 3517 421 2377 422 2687 423 2389 424 6091 425 3259 426 3557 427 4129 428 4003 429 2003 430 2297 431 6323 432 4909 433 5483 434 3631 435 2459 436 3209 437 2909 438 2347 439 9067 440 1933 441 2477 442 4153 443 3821 444 3727 445 1613 446 3739 447 3413 448 4651 449 5227 450 2423 451 4793 452 3343 453 2999 454 2903 455 3467 456 2917 457 5309 458 3851 459 6247 460 6173 461 5813 462 2503 463 8609 464 3919 465 5381 466 1609 467 3061 468 3023 469 4481 470 4919 471 2617 472 5879 473 8311 474 3539 475 5011 476 7841 477 3607 478 4519 479 6977 480 1663 481 1223 482 2633 483 1231 484 4093 485 4637 486 4597 487 2221 488 2659 489 6143 490 1697 491 8123 492 4177 493 5683 494 4691 495 2239 496 3217 497 1753 498 4721 499 4261 500 9239 501 4789 502 8263 503 5821 504 3251 505 5839 506 4787 507 1297 508 4799 509 7417 510 3803 511 8461 512 4339 513 8999 514 5393 515 3877 516 3347 517 12163 518 4931 519 3373 520 5987 521 3391 522 8093 523 6551 524 5501 525 4999 526 3943 527 1327 528 5009 529 4513 530 3967 531 5591 532 4517 533 1879 534 3461 535 1889 536 2399 537 5119 538 5641 539 6217 540 2963 541 3529 542 7853 543 5179 544 5701 545 839 546 4621 547 3037 548 6827 549 9643 550 6857 551 6367 552 4673 553 5281 554 3583 555 5297 556 6379 557 10331 558 5851 559 4211 560 5869 561 4229 562 4201 563 9311 564 6481 565 7079 566 2543 567 1993 568 2551 569 6553 570 1997 571 17417 572 6607 573 8291 574 4337 575 9463 576 6089 577 4297 578 4951 579 5471 580 1489 581 8969 582 3253 583 10739 584 6197 585 3163 586 2111 587 4933 588 2711 589 4357 590 3313 591 3779 592 5101 593 5573 594 3931 595 6779 596 5737 597 6203 598 1571 599 3221 600 5779 601 5039 602 3389 603 3847 604 6421 605 14149 606 5849 607 5077 608 5867 609 9967 610 7723 611 10607 612 3469 613 5113 614 5939 615 6361 616 2879 617 9461 618 9697 619 6397 620 7243 621 1451 622 7879 623 5827 624 4157 625 5843 626 9181 627 7121 628 7951 629 2113 630 4817 631 5279 632 7993 633 12263 634 9293 635 2137 636 6131 637 7883 638 1049 639 6619 640 8101 641 7283 642 4273 643 4729 644 6863 645 3457 646 8171 647 11239 648 6257 649 9319 650 8231 651 7393 652 3691 653 11981 654 7639 655 8081 656 9631 657 7451 658 5051 659 19991 660 1129 661 4159 662 4447 663 7487 664 2473 665 5507 666 9811 667 23539 668 10529 669 2851 670 5189 671 22993 672 1871 673 10243 674 3911 675 12289 676 9343 677 9613 678 3947 679 6917 680 4643 681 11701 682 14897 683 2861 684 4663 685 11777 686 4001 687 4243 688 4013 689 8389 690 6101 691 6337 692 8887 693 4973 694 4049 695 9851 696 7549 697 30089 698 7603 699 9173 700 5527 701 5689 702 4139 703 7109 704 5563 705 5717 706 6991 707 8563 708 4889 709 7873 710 2777 711 7177 712 5639 713 12899 714 8521 715 4349 716 3527 717 13681 718 2833 719 14423 720 9337 721 16619 722 7207 723 5807 724 7949 725 751 726 5783 727 10211 728 15269 729 8059 730 5081 731 5153 732 13147 733 13241 734 6577 735 6653 736 7331 737 10357 738 8831 739 13339 740 4421 741 5953 742 6661 743 11171 744 5197 745 5233 746 3719 747 8233 748 5231 749 9749 750 9001 751 15031 752 3769 753 3761 754 12073 755 6047 756 2269 757 8329 758 3041 759 4549 760 10651 761 10657 762 6869 763 2287 764 13757 765 6133 766 4591 767 3079 768 3833 769 10009 770 9241 771 12347 772 13901 773 15473 774 6199 775 12401 776 3119 777 7759 778 15581 779 7789 780 9371 781 12497 782 6271 783 7823 784 8641 785 8629 786 4733 787 3137 788 5531 789 11827 790 6343 791 11059 792 3989 793 8699 794 2417 795 8713 796 10391 797 8737 798 8819 799 13553 800 5647 801 13577 802 6473 803 9587 804 7297 805 7193 806 9733 807 16091 808 16229 809 17749 810 5741 811 12101 812 9011 813 2371 814 9839 815 4831 816 3329 817 9743 818 12343 819 8951 820 8269 821 16361 822 1723 823 14737 824 18223 825 4877 826 5861 827 15641 828 4231 829 10691 830 10889 831 12379 832 7589 833 4073 834 13441 835 6599 836 10957 837 7457 838 10141 839 8317 840 6803 841 11699 842 10193 843 8353 844 3463 845 4987 846 6011 847 7541 848 1787 849 6703 850 2647 851 12671 852 6073 853 9281 854 5237 855 6733 856 11243 857 5897 858 3541 859 3331 860 4409 861 5923 862 8731 863 17159 864 4441 865 7669 866 7919 867 4219 868 7933 869 12923 870 5347 871 17299 872 8861 873 5107 874 4507 875 16493 876 7159 877 8627 878 6299 879 6007 880 3673 881 6899 882 4567 883 6029 884 9883 885 7817 886 6359 887 14929 888 13487 889 13183 890 10847 891 19447 892 14449 893 6983 894 4639 895 11471 896 6449 897 11491 898 1979 899 16001 900 9199 901 7019 902 11923 903 22391 904 11057 905 7043 906 6547 907 6151 908 5653 909 10709 910 6581 911 9817 912 8423 913 8011 914 2957 915 13513 916 10303 917 9871 918 12161 919 26437 920 3923 921 7129 922 6701 923 6221 924 5791 925 10859 926 13217 927 5323 928 8597 929 19273 930 10487 931 17443 932 5857 933 10937 934 4007 935 7213 936 4019 937 5351 938 4967 939 4423 940 9677 941 12907 942 12527 943 8219 944 14437 945 6353 946 8783 947 21521 948 7867 949 5419 950 5981 951 5431 952 8849 953 4493 954 8863 955 14057 956 10799 957 6427 958 9859 959 16993 960 2207 961 15091 962 10883 963 8377 964 3191 965 25759 966 10949 967 16127 968 9041 969 12277 970 1303 971 27827 972 9109 973 14243 974 6211 975 17189 976 7211 977 12329 978 3319 979 8429 980 23911 981 5519 982 7247 983 12413 984 13171 985 6529 986 5303 987 2593 988 12227 989 19421 990 13249 991 6571 992 5333 993 12541 994 10321 995 17539 996 13337 997 16573 998 13367 999 16603 1000 9397