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