1 0 2 1 3 2 4 3 5 4 6 5 7 7 8 9 9 11 10 13 11 16 12 17 13 19 14 23 15 25 16 29 17 31 18 36 19 37 20 41 21 43 22 47 23 49 24 53 25 59 26 61 27 64 28 67 29 71 30 73 31 79 32 81 33 83 34 89 35 97 36 100 37 101 38 103 39 107 40 109 41 113 42 121 43 127 44 131 45 137 46 139 47 144 48 149 49 151 50 157 51 163 52 167 53 169 54 173 55 179 56 181 57 191 58 193 59 196 60 197 61 199 62 211 63 223 64 225 65 227 66 229 67 233 68 239 69 241 70 251 71 256 72 257 73 263 74 269 75 271 76 277 77 281 78 283 79 289 80 293 81 307 82 311 83 313 84 317 85 324 86 331 87 337 88 347 89 349 90 353 91 359 92 361 93 367 94 373 95 379 96 383 97 389 98 397 99 400 100 401 101 409 102 419 103 421 104 431 105 433 106 439 107 441 108 443 109 449 110 457 111 461 112 463 113 467 114 479 115 484 116 487 117 491 118 499 119 503 120 509 121 521 122 523 123 529 124 541 125 547 126 557 127 563 128 569 129 571 130 576 131 577 132 587 133 593 134 599 135 601 136 607 137 613 138 617 139 619 140 625 141 631 142 641 143 643 144 647 145 653 146 659 147 661 148 673 149 676 150 677 151 683 152 691 153 701 154 709 155 719 156 727 157 729 158 733 159 739 160 743 161 751 162 757 163 761 164 769 165 773 166 784 167 787 168 797 169 809 170 811 171 821 172 823 173 827 174 829 175 839 176 841 177 853 178 857 179 859 180 863 181 877 182 881 183 883 184 887 185 900 186 907 187 911 188 919 189 929 190 937 191 941 192 947 193 953 194 961 195 967 196 971 197 977 198 983 199 991 200 997 201 1009 202 1013 203 1019 204 1021 205 1024 206 1031 207 1033 208 1039 209 1049 210 1051 211 1061 212 1063 213 1069 214 1087 215 1089 216 1091 217 1093 218 1097 219 1103 220 1109 221 1117 222 1123 223 1129 224 1151 225 1153 226 1156 227 1163 228 1171 229 1181 230 1187 231 1193 232 1201 233 1213 234 1217 235 1223 236 1225 237 1229 238 1231 239 1237 240 1249 241 1259 242 1277 243 1279 244 1283 245 1289 246 1291 247 1296 248 1297 249 1301 250 1303 251 1307 252 1319 253 1321 254 1327 255 1361 256 1367 257 1369 258 1373 259 1381 260 1399 261 1409 262 1423 263 1427 264 1429 265 1433 266 1439 267 1444 268 1447 269 1451 270 1453 271 1459 272 1471 273 1481 274 1483 275 1487 276 1489 277 1493 278 1499 279 1511 280 1521 281 1523 282 1531 283 1543 284 1549 285 1553 286 1559 287 1567 288 1571 289 1579 290 1583 291 1597 292 1600 293 1601 294 1607 295 1609 296 1613 297 1619 298 1621 299 1627 300 1637 301 1657 302 1663 303 1667 304 1669 305 1681 306 1693 307 1697 308 1699 309 1709 310 1721 311 1723 312 1733 313 1741 314 1747 315 1753 316 1759 317 1764 318 1777 319 1783 320 1787 321 1789 322 1801 323 1811 324 1823 325 1831 326 1847 327 1849 328 1861 329 1867 330 1871 331 1873 332 1877 333 1879 334 1889 335 1901 336 1907 337 1913 338 1931 339 1933 340 1936 341 1949 342 1951 343 1973 344 1979 345 1987 346 1993 347 1997 348 1999 349 2003 350 2011 351 2017 352 2025 353 2027 354 2029 355 2039 356 2053 357 2063 358 2069 359 2081 360 2083 361 2087 362 2089 363 2099 364 2111 365 2113 366 2116 367 2129 368 2131 369 2137 370 2141 371 2143 372 2153 373 2161 374 2179 375 2203 376 2207 377 2209 378 2213 379 2221 380 2237 381 2239 382 2243 383 2251 384 2267 385 2269 386 2273 387 2281 388 2287 389 2293 390 2297 391 2304 392 2309 393 2311 394 2333 395 2339 396 2341 397 2347 398 2351 399 2357 400 2371 401 2377 402 2381 403 2383 404 2389 405 2393 406 2399 407 2401 408 2411 409 2417 410 2423 411 2437 412 2441 413 2447 414 2459 415 2467 416 2473 417 2477 418 2500 419 2503 420 2521 421 2531 422 2539 423 2543 424 2549 425 2551 426 2557 427 2579 428 2591 429 2593 430 2601 431 2609 432 2617 433 2621 434 2633 435 2647 436 2657 437 2659 438 2663 439 2671 440 2677 441 2683 442 2687 443 2689 444 2693 445 2699 446 2704 447 2707 448 2711 449 2713 450 2719 451 2729 452 2731 453 2741 454 2749 455 2753 456 2767 457 2777 458 2789 459 2791 460 2797 461 2801 462 2803 463 2809 464 2819 465 2833 466 2837 467 2843 468 2851 469 2857 470 2861 471 2879 472 2887 473 2897 474 2903 475 2909 476 2916 477 2917 478 2927 479 2939 480 2953 481 2957 482 2963 483 2969 484 2971 485 2999 486 3001 487 3011 488 3019 489 3023 490 3025 491 3037 492 3041 493 3049 494 3061 495 3067 496 3079 497 3083 498 3089 499 3109 500 3119 501 3121 502 3136 503 3137 504 3163 505 3167 506 3169 507 3181 508 3187 509 3191 510 3203 511 3209 512 3217 513 3221 514 3229 515 3249 516 3251 517 3253 518 3257 519 3259 520 3271 521 3299 522 3301 523 3307 524 3313 525 3319 526 3323 527 3329 528 3331 529 3343 530 3347 531 3359 532 3361 533 3364 534 3371 535 3373 536 3389 537 3391 538 3407 539 3413 540 3433 541 3449 542 3457 543 3461 544 3463 545 3467 546 3469 547 3481 548 3491 549 3499 550 3511 551 3517 552 3527 553 3529 554 3533 555 3539 556 3541 557 3547 558 3557 559 3559 560 3571 561 3581 562 3583 563 3593 564 3600 565 3607 566 3613 567 3617 568 3623 569 3631 570 3637 571 3643 572 3659 573 3671 574 3673 575 3677 576 3691 577 3697 578 3701 579 3709 580 3719 581 3721 582 3727 583 3733 584 3739 585 3761 586 3767 587 3769 588 3779 589 3793 590 3797 591 3803 592 3821 593 3823 594 3833 595 3844 596 3847 597 3851 598 3853 599 3863 600 3877 601 3881 602 3889 603 3907 604 3911 605 3917 606 3919 607 3923 608 3929 609 3931 610 3943 611 3947 612 3967 613 3969 614 3989 615 4001 616 4003 617 4007 618 4013 619 4019 620 4021 621 4027 622 4049 623 4051 624 4057 625 4073 626 4079 627 4091 628 4093 629 4096 630 4099 631 4111 632 4127 633 4129 634 4133 635 4139 636 4153 637 4157 638 4159 639 4177 640 4201 641 4211 642 4217 643 4219 644 4225 645 4229 646 4231 647 4241 648 4243 649 4253 650 4259 651 4261 652 4271 653 4273 654 4283 655 4289 656 4297 657 4327 658 4337 659 4339 660 4349 661 4356 662 4357 663 4363 664 4373 665 4391 666 4397 667 4409 668 4421 669 4423 670 4441 671 4447 672 4451 673 4457 674 4463 675 4481 676 4483 677 4489 678 4493 679 4507 680 4513 681 4517 682 4519 683 4523 684 4547 685 4549 686 4561 687 4567 688 4583 689 4591 690 4597 691 4603 692 4621 693 4624 694 4637 695 4639 696 4643 697 4649 698 4651 699 4657 700 4663 701 4673 702 4679 703 4691 704 4703 705 4721 706 4723 707 4729 708 4733 709 4751 710 4759 711 4761 712 4783 713 4787 714 4789 715 4793 716 4799 717 4801 718 4813 719 4817 720 4831 721 4861 722 4871 723 4877 724 4889 725 4900 726 4903 727 4909 728 4919 729 4931 730 4933 731 4937 732 4943 733 4951 734 4957 735 4967 736 4969 737 4973 738 4987 739 4993 740 4999 741 5003 742 5009 743 5011 744 5021 745 5023 746 5039 747 5041 748 5051 749 5059 750 5077 751 5081 752 5087 753 5099 754 5101 755 5107 756 5113 757 5119 758 5147 759 5153 760 5167 761 5171 762 5179 763 5184 764 5189 765 5197 766 5209 767 5227 768 5231 769 5233 770 5237 771 5261 772 5273 773 5279 774 5281 775 5297 776 5303 777 5309 778 5323 779 5329 780 5333 781 5347 782 5351 783 5381 784 5387 785 5393 786 5399 787 5407 788 5413 789 5417 790 5419 791 5431 792 5437 793 5441 794 5443 795 5449 796 5471 797 5476 798 5477 799 5479 800 5483 801 5501 802 5503 803 5507 804 5519 805 5521 806 5527 807 5531 808 5557 809 5563 810 5569 811 5573 812 5581 813 5591 814 5623 815 5625 816 5639 817 5641 818 5647 819 5651 820 5653 821 5657 822 5659 823 5669 824 5683 825 5689 826 5693 827 5701 828 5711 829 5717 830 5737 831 5741 832 5743 833 5749 834 5776 835 5779 836 5783 837 5791 838 5801 839 5807 840 5813 841 5821 842 5827 843 5839 844 5843 845 5849 846 5851 847 5857 848 5861 849 5867 850 5869 851 5879 852 5881 853 5897 854 5903 855 5923 856 5927 857 5929 858 5939 859 5953 860 5981 861 5987 862 6007 863 6011 864 6029 865 6037 866 6043 867 6047 868 6053 869 6067 870 6073 871 6079 872 6084 873 6089 874 6091 875 6101 876 6113 877 6121 878 6131 879 6133 880 6143 881 6151 882 6163 883 6173 884 6197 885 6199 886 6203 887 6211 888 6217 889 6221 890 6229 891 6241 892 6247 893 6257 894 6263 895 6269 896 6271 897 6277 898 6287 899 6299 900 6301 901 6311 902 6317 903 6323 904 6329 905 6337 906 6343 907 6353 908 6359 909 6361 910 6367 911 6373 912 6379 913 6389 914 6397 915 6400 916 6421 917 6427 918 6449 919 6451 920 6469 921 6473 922 6481 923 6491 924 6521 925 6529 926 6547 927 6551 928 6553 929 6561 930 6563 931 6569 932 6571 933 6577 934 6581 935 6599 936 6607 937 6619 938 6637 939 6653 940 6659 941 6661 942 6673 943 6679 944 6689 945 6691 946 6701 947 6703 948 6709 949 6719 950 6724 951 6733 952 6737 953 6761 954 6763 955 6779 956 6781 957 6791 958 6793 959 6803 960 6823 961 6827 962 6829 963 6833 964 6841 965 6857 966 6863 967 6869 968 6871 969 6883 970 6889 971 6899 972 6907 973 6911 974 6917 975 6947 976 6949 977 6959 978 6961 979 6967 980 6971 981 6977 982 6983 983 6991 984 6997 985 7001 986 7013 987 7019 988 7027 989 7039 990 7043 991 7056 992 7057 993 7069 994 7079 995 7103 996 7109 997 7121 998 7127 999 7129 1000 7151