1 2 2 5 3 11 4 13 5 29 6 31 7 17 8 19 9 43 10 7 11 37 12 41 13 71 14 47 15 67 16 89 17 3 18 101 19 23 20 109 21 59 22 83 23 103 24 73 25 107 26 157 27 53 28 127 29 149 30 61 31 131 32 139 33 79 34 163 35 191 36 193 37 97 38 113 39 137 40 167 41 211 42 181 43 151 44 197 45 199 46 173 47 223 48 239 49 227 50 179 51 241 52 251 53 229 54 257 55 313 56 233 57 263 58 277 59 271 60 283 61 307 62 347 63 269 64 293 65 281 66 349 67 401 68 397 69 367 70 383 71 431 72 337 73 353 74 379 75 331 76 419 77 359 78 439 79 487 80 311 81 373 82 409 83 457 84 461 85 421 86 317 87 463 88 389 89 467 90 433 91 499 92 443 93 521 94 541 95 479 96 547 97 503 98 557 99 491 100 569 101 523 102 449 103 509 104 601 105 577 106 607 107 571 108 613 109 599 110 617 111 593 112 691 113 643 114 587 115 631 116 647 117 653 118 619 119 661 120 677 121 641 122 683 123 787 124 563 125 701 126 733 127 761 128 743 129 673 130 821 131 659 132 709 133 757 134 719 135 857 136 751 137 797 138 727 139 881 140 769 141 773 142 809 143 823 144 883 145 907 146 829 147 859 148 739 149 811 150 839 151 877 152 1021 153 1009 154 827 155 853 156 919 157 929 158 967 159 887 160 863 161 1019 162 997 163 911 164 941 165 937 166 1013 167 971 168 953 169 1109 170 977 171 983 172 1033 173 1153 174 1087 175 1049 176 947 177 1039 178 1063 179 1069 180 991 181 1051 182 1091 183 1031 184 1231 185 1061 186 1117 187 1171 188 1097 189 1093 190 1103 191 1181 192 1223 193 1163 194 1213 195 1151 196 1249 197 1123 198 1129 199 1237 200 1187 201 1277 202 1201 203 1229 204 1217 205 1291 206 1297 207 1361 208 1193 209 1279 210 1289 211 1399 212 1283 213 1319 214 1259 215 1301 216 1373 217 1321 218 1367 219 1307 220 1439 221 1303 222 1447 223 1381 224 1427 225 1429 226 1489 227 1423 228 1327 229 1433 230 1493 231 1483 232 1487 233 1523 234 1471 235 1409 236 1543 237 1481 238 1453 239 1451 240 1531 241 1499 242 1459 243 1607 244 1559 245 1567 246 1553 247 1579 248 1613 249 1583 250 1601 251 1619 252 1709 253 1549 254 1597 255 1657 256 1609 257 1571 258 1693 259 1621 260 1669 261 1511 262 1627 263 1667 264 1721 265 1777 266 1741 267 1789 268 1699 269 1753 270 1637 271 1733 272 1663 273 1747 274 1811 275 1697 276 1723 277 1823 278 1759 279 1801 280 1787 281 1831 282 1783 283 1889 284 1867 285 1873 286 1949 287 1871 288 1907 289 1973 290 1913 291 1879 292 1987 293 1847 294 1933 295 1877 296 1861 297 2017 298 1901 299 1931 300 1993 301 1979 302 1999 303 2027 304 2003 305 2029 306 2053 307 2039 308 2011 309 2063 310 2069 311 2087 312 1997 313 1951 314 2099 315 2081 316 2113 317 2083 318 2161 319 2143 320 2089 321 2111 322 2129 323 2137 324 2131 325 2221 326 2153 327 2179 328 2237 329 2203 330 2269 331 2239 332 2213 333 2141 334 2207 335 2243 336 2267 337 2377 338 2297 339 2251 340 2333 341 2293 342 2281 343 2347 344 2411 345 2273 346 2393 347 2309 348 2287 349 2311 350 2339 351 2381 352 2399 353 2341 354 2383 355 2371 356 2351 357 2423 358 2417 359 2357 360 2447 361 2389 362 2531 363 2441 364 2593 365 2437 366 2551 367 2503 368 2543 369 2591 370 2459 371 2467 372 2521 373 2477 374 2557 375 2617 376 2663 377 2609 378 2647 379 2539 380 2549 381 2659 382 2657 383 2579 384 2473 385 2683 386 2687 387 2689 388 2707 389 2677 390 2671 391 2693 392 2699 393 2711 394 2633 395 2719 396 2731 397 2777 398 2749 399 2789 400 2713 401 2833 402 2843 403 2909 404 2767 405 2741 406 2857 407 2621 408 2837 409 2791 410 2953 411 2801 412 2729 413 2887 414 2803 415 2927 416 2861 417 2917 418 2819 419 2903 420 2797 421 2753 422 2957 423 2879 424 2999 425 2851 426 2939 427 3001 428 2963 429 3023 430 3019 431 3109 432 2897 433 3049 434 3067 435 2971 436 2969 437 3061 438 3037 439 3011 440 3079 441 3041 442 3119 443 3089 444 3083 445 3137 446 3121 447 3169 448 3163 449 3167 450 3257 451 3229 452 3191 453 3251 454 3187 455 3253 456 3203 457 3323 458 3181 459 3209 460 3271 461 3217 462 3301 463 3221 464 3299 465 3511 466 3313 467 3373 468 3259 469 3359 470 3307 471 3347 472 3329 473 3319 474 3371 475 3433 476 3461 477 3457 478 3407 479 3331 480 3391 481 3413 482 3343 483 3361 484 3463 485 3449 486 3467 487 3533 488 3571 489 3491 490 3517 491 3607 492 3389 493 3557 494 3469 495 3539 496 3637 497 3541 498 3581 499 3499 500 3527 501 3529 502 3623 503 3613 504 3593 505 3547 506 3583 507 3631 508 3617 509 3559 510 3643 511 3709 512 3677 513 3671 514 3673 515 3659 516 3863 517 3797 518 3719 519 3697 520 3727 521 3739 522 3691 523 3767 524 3833 525 3761 526 3847 527 3821 528 3877 529 3823 530 3803 531 3701 532 3733 533 3889 534 3967 535 3779 536 3881 537 3943 538 3793 539 3947 540 3853 541 3911 542 3923 543 3917 544 3929 545 3907 546 3931 547 3769 548 4001 549 4019 550 3851 551 4079 552 4003 553 3989 554 4027 555 4013 556 4093 557 4007 558 4051 559 4057 560 4111 561 4049 562 4021 563 4073 564 4099 565 4133 566 3919 567 4219 568 4091 569 4357 570 4139 571 4129 572 4201 573 4177 574 4159 575 4231 576 4153 577 4127 578 4157 579 4211 580 4229 581 4241 582 4259 583 4217 584 4243 585 4273 586 4261 587 4253 588 4283 589 4297 590 4339 591 4363 592 4409 593 4327 594 4517 595 4289 596 4349 597 4421 598 4373 599 4271 600 4441 601 4337 602 4463 603 4391 604 4423 605 4447 606 4457 607 4519 608 4483 609 4397 610 4507 611 4493 612 4583 613 4481 614 4603 615 4549 616 4591 617 4561 618 4513 619 4657 620 4639 621 4651 622 4451 623 4691 624 4547 625 4523 626 4621 627 4673 628 4649 629 4663 630 4643 631 4723 632 4637 633 4567 634 4861 635 4597 636 4721 637 4733 638 4679 639 4903 640 4703 641 4729 642 4751 643 4759 644 4793 645 4789 646 4813 647 4801 648 4787 649 4877 650 4799 651 4817 652 4783 653 4919 654 4987 655 4969 656 4943 657 4999 658 4871 659 4889 660 4931 661 4951 662 4957 663 5059 664 4933 665 5009 666 5003 667 4831 668 4993 669 4967 670 4973 671 5021 672 5023 673 4937 674 5087 675 5039 676 5179 677 5011 678 5113 679 4909 680 5099 681 5119 682 5051 683 5107 684 5077 685 5261 686 5167 687 5081 688 5309 689 5101 690 5147 691 5197 692 5171 693 5281 694 5189 695 5209 696 5227 697 5273 698 5279 699 5297 700 5333 701 5233 702 5231 703 5303 704 5399 705 5417 706 5323 707 5413 708 5237 709 5351 710 5153 711 5347 712 5437 713 5441 714 5431 715 5471 716 5477 717 5479 718 5521 719 5407 720 5419 721 5387 722 5531 723 5381 724 5519 725 5393 726 5443 727 5483 728 5449 729 5507 730 5557 731 5689 732 5527 733 5647 734 5563 735 5569 736 5639 737 5503 738 5683 739 5623 740 5701 741 5641 742 5573 743 5651 744 5581 745 5693 746 5711 747 5717 748 5783 749 5653 750 5501 751 5659 752 5669 753 5741 754 5591 755 5807 756 5749 757 5791 758 5779 759 5827 760 5839 761 5843 762 5801 763 5657 764 5849 765 5851 766 5857 767 5869 768 5737 769 5879 770 5987 771 5927 772 5881 773 5743 774 5861 775 5821 776 5813 777 5923 778 5897 779 5903 780 5867 781 6053 782 5953 783 6121 784 6029 785 6113 786 5981 787 6043 788 5939 789 6011 790 6007 791 6047 792 6073 793 6067 794 6131 795 6091 796 6101 797 6143 798 6163 799 6079 800 6089 801 6197 802 6217 803 6151 804 6199 805 6229 806 6211 807 6203 808 6173 809 6247 810 6277 811 6133 812 6221 813 6257 814 6263 815 6379 816 6271 817 6299 818 6037 819 6269 820 6317 821 6301 822 6287 823 6311 824 6329 825 6397 826 6367 827 6337 828 6343 829 6451 830 6361 831 6359 832 6469 833 6553 834 6353 835 6473 836 6449 837 6421 838 6389 839 6607 840 6491 841 6547 842 6521 843 6373 844 6323 845 6637 846 6659 847 6563 848 6481 849 6653 850 6569 851 6529 852 6619 853 6577 854 6551 855 6691 856 6427 857 6571 858 6679 859 6701 860 6803 861 6827 862 6581 863 6673 864 6917 865 6661 866 6689 867 6709 868 6761 869 6599 870 6791 871 6793 872 6733 873 6703 874 6719 875 6871 876 6947 877 6781 878 6869 879 6823 880 6857 881 6737 882 6883 883 6959 884 6829 885 6911 886 6763 887 6997 888 6779 889 6967 890 6833 891 6961 892 6971 893 6949 894 6977 895 7027 896 7001 897 6863 898 7019 899 6991 900 7129 901 7069 902 6983 903 6841 904 7043 905 7039 906 7121 907 7013 908 7057 909 7079 910 7151 911 7103 912 7211 913 7207 914 6907 915 7159 916 7229 917 6899 918 7253 919 7213 920 7187 921 7219 922 7127 923 7321 924 7109 925 7237 926 7333 927 7243 928 7297 929 7247 930 7477 931 7177 932 7331 933 7411 934 7283 935 7417 936 7193 937 7433 938 7393 939 7369 940 7451 941 7309 942 7459 943 7351 944 7507 945 7481 946 7307 947 7529 948 7517 949 7349 950 7489 951 7537 952 7487 953 7523 954 7577 955 7457 956 7499 957 7547 958 7561 959 7589 960 7603 961 7541 962 7649 963 7559 964 7573 965 7549 966 7669 967 7591 968 7607 969 7639 970 7643 971 7717 972 7681 973 7691 974 7687 975 7583 976 7741 977 7673 978 7699 979 7703 980 7867 981 7621 982 7757 983 7823 984 7759 985 7723 986 7817 987 7727 988 7907 989 7789 990 7753 991 7901 992 7879 993 7829 994 7841 995 7853 996 7793 997 7933 998 7951 999 7883 1000 7919 1001 8069 1002 8011 1003 7873 1004 8009 1005 7949 1006 8087 1007 8017 1008 8059 1009 8233 1010 7993 1011 7877 1012 8053 1013 7927 1014 7937 1015 8093 1016 8081 1017 8111 1018 7963 1019 8089 1020 8209 1021 8237 1022 8171 1023 8167 1024 8179 1025 8191 1026 8101 1027 8123 1028 8219 1029 8117 1030 8039 1031 8231 1032 8297 1033 8353 1034 8243 1035 8273 1036 8293 1037 8161 1038 8419 1039 8263 1040 8287 1041 8291 1042 8329 1043 8363 1044 8311 1045 8147 1046 8377 1047 8221 1048 8429 1049 8317 1050 8423 1051 8387 1052 8389 1053 8369 1054 8573 1055 8269 1056 8431 1057 8447 1058 8627 1059 8513 1060 8467 1061 8527 1062 8537 1063 8521 1064 8443 1065 8597 1066 8501 1067 8539 1068 8563 1069 8647 1070 8669 1071 8581 1072 8461 1073 8543 1074 8719 1075 8737 1076 8747 1077 8629 1078 8599 1079 8677 1080 8641 1081 8609 1082 8663 1083 8681 1084 8693 1085 8623 1086 8779 1087 8731 1088 8707 1089 8713 1090 8753 1091 8867 1092 8819 1093 8699 1094 8821 1095 8861 1096 8971 1097 8741 1098 8839 1099 8783 1100 8689 1101 8761 1102 8887 1103 8849 1104 8807 1105 8863 1106 8929 1107 8831 1108 8923 1109 9049 1110 8941 1111 8893 1112 8933 1113 9001 1114 8837 1115 8803 1116 8951 1117 8963 1118 9091 1119 9043 1120 9059 1121 8969 1122 8999 1123 9007 1124 9067 1125 9209 1126 9187 1127 9109 1128 9029 1129 9103 1130 9157 1131 9173 1132 9239 1133 9323 1134 9227 1135 9137 1136 9041 1137 9127 1138 9013 1139 9281 1140 9181 1141 9011 1142 9161 1143 9199 1144 9371 1145 9221 1146 9257 1147 9203 1148 9241 1149 9133 1150 9293 1151 9151 1152 9337 1153 9377 1154 9413 1155 9343 1156 9311 1157 9419 1158 9403 1159 9319 1160 9283 1161 9433 1162 9431 1163 9391 1164 9341 1165 9397 1166 9437 1167 9349 1168 9439 1169 9473 1170 9511 1171 9421 1172 9533 1173 9463 1174 9461 1175 9479 1176 9467 1177 9547 1178 9733 1179 9521 1180 9619 1181 9551 1182 9491 1183 9277 1184 9539 1185 9721 1186 9497 1187 9623 1188 9601 1189 9677 1190 9643 1191 9719 1192 9781 1193 9749 1194 9649 1195 9629 1196 9833 1197 9689 1198 9661 1199 9767 1200 9871 1201 9743 1202 9851 1203 9631 1204 9857 1205 9769 1206 9817 1207 9587 1208 9613 1209 9697 1210 9679 1211 9829 1212 9803 1213 9887 1214 10039 1215 9839 1216 9787 1217 9791 1218 9739 1219 9883 1220 9811 1221 10037 1222 9973 1223 10133 1224 9859 1225 9929 1226 9923 1227 10099 1228 10067 1229 9901 1230 9941 1231 9907 1232 10111 1233 10007 1234 10009 1235 9931 1236 9949 1237 9967 1238 10069 1239 10093 1240 10399 1241 10091 1242 10061 1243 10103 1244 10139 1245 10159 1246 10223 1247 10193 1248 10211 1249 10301 1250 10259 1251 10177 1252 10151 1253 10079 1254 10169 1255 10273 1256 10247 1257 10141 1258 10253 1259 10271 1260 10243 1261 10313 1262 10321 1263 10331 1264 10163 1265 10457 1266 10333 1267 10181 1268 10289 1269 10303 1270 10267 1271 10391 1272 10357 1273 10369 1274 10459 1275 10513 1276 10433 1277 10453 1278 10487 1279 10499 1280 10427 1281 10343 1282 10429 1283 10337 1284 10477 1285 10531 1286 10601 1287 10529 1288 10597 1289 10463 1290 10711 1291 10663 1292 10567 1293 10501 1294 10559 1295 10607 1296 10613 1297 10733 1298 10867 1299 10771 1300 10589 1301 10627 1302 10657 1303 10631 1304 10651 1305 10831 1306 10639 1307 10837 1308 10799 1309 10753 1310 10729 1311 10667 1312 10723 1313 10859 1314 10937 1315 10691 1316 10781 1317 10861 1318 10739 1319 11027 1320 10709 1321 10789 1322 10687 1323 11059 1324 10853 1325 10889 1326 10891 1327 10939 1328 11071 1329 10847 1330 10949 1331 10957 1332 10883 1333 10903 1334 10973 1335 10979 1336 11093 1337 10987 1338 11087 1339 10909 1340 11131 1341 11057 1342 11083 1343 11003 1344 11119 1345 11243 1346 11113 1347 11069 1348 11161 1349 11149 1350 11177 1351 11117 1352 11257 1353 11159 1354 11261 1355 11239 1356 11299 1357 10993 1358 11171 1359 11047 1360 11279 1361 11273 1362 11317 1363 11173 1364 11383 1365 11287 1366 11351 1367 11411 1368 11197 1369 11393 1370 11353 1371 11213 1372 11251 1373 11399 1374 11329 1375 11311 1376 11321 1377 11471 1378 11437 1379 11423 1380 11369 1381 11503 1382 11497 1383 11467 1384 11519 1385 11443 1386 11579 1387 11587 1388 11527 1389 11549 1390 11489 1391 11551 1392 11681 1393 11483 1394 11491 1395 11447 1396 11593 1397 11597 1398 11677 1399 11621 1400 11789 1401 11657 1402 11689 1403 11617 1404 11701 1405 11743 1406 11813 1407 11777 1408 11717 1409 11633 1410 11821 1411 11699 1412 11731 1413 11719 1414 11833 1415 11783 1416 11779 1417 11839 1418 11897 1419 11827 1420 11863 1421 11831 1422 11801 1423 11807 1424 11887 1425 11903 1426 11909 1427 11867 1428 11927 1429 12101 1430 11969 1431 11941 1432 11939 1433 11959 1434 11971 1435 11981 1436 11953 1437 11933 1438 12037 1439 11923 1440 11987 1441 12007 1442 12109 1443 12157 1444 12073 1445 12011 1446 12161 1447 12097 1448 12197 1449 12119 1450 12041 1451 12143 1452 12227 1453 12107 1454 12043 1455 12203 1456 12049 1457 12149 1458 12211 1459 12071 1460 12289 1461 12263 1462 12239 1463 12113 1464 12281 1465 12241 1466 12323 1467 12343 1468 12163 1469 12347 1470 12253 1471 12277 1472 12301 1473 12329 1474 12373 1475 12401 1476 12251 1477 12269 1478 12377 1479 12379 1480 12491 1481 12517 1482 12437 1483 12421 1484 12473 1485 12433 1486 12479 1487 12547 1488 12527 1489 12409 1490 12487 1491 12413 1492 12583 1493 12497 1494 12511 1495 12457 1496 12541 1497 12671 1498 12451 1499 12553 1500 12577