0 1
1 3
2 5
3 7
4 9
5 11
6 13
7 5
8 17
9 19
10 21
11 23
12 25
13 27
14 29
15 31
16 11
17 7
18 37
19 13
20 41
21 43
22 3
23 47
24 49
25 17
26 53
27 55
28 57
29 59
30 61
31 9
32 65
33 67
34 23
35 71
36 73
37 75
38 11
39 79
40 81
41 83
42 17
43 29
44 89
45 13
46 31
47 19
48 97
49 11
50 101
51 103
52 35
53 107
54 109
55 37
56 113
57 115
58 39
59 119
60 121
61 41
62 125
63 127
64 43
65 131
66 133
67 9
68 137
69 139
70 47
71 13
72 29
73 49
74 149
75 151
76 17
77 31
78 157
79 53
80 23
81 163
82 3
83 167
84 169
85 171
86 173
87 5
88 59
89 179
90 181
91 183
92 37
93 17
94 27
95 191
96 193
97 1
98 197
99 199
100 67
101 203
102 41
103 69
104 19
105 211
106 71
107 43
108 217
109 219
110 17
111 223
112 45
113 227
114 229
115 7
116 233
117 47
118 237
119 239
120 241
121 243
122 49
123 19
124 83
125 251
126 253
127 85
128 257
129 37
130 29
131 263
132 265
133 89
134 269
135 271
136 1
137 275
138 277
139 31
140 281
141 283
142 19
143 41
144 289
145 97
146 293
147 59
148 33
149 23
150 301
151 101
152 305
153 307
154 103
155 311
156 313
157 35
158 317
159 319
160 107
161 19
162 25
163 109
164 329
165 331
166 111
167 67
168 337
169 113
170 341
171 343
172 23
173 347
174 349
175 117
176 353
177 355
178 1
179 359
180 361
181 121
182 365
183 367
184 41
185 53
186 373
187 125
188 377
189 379
190 127
191 383
192 1
193 129
194 389
195 23
196 131
197 79
198 397
199 1
200 401
201 403
202 27
203 37
204 409
205 137
206 59
207 83
208 139
209 419
210 421
211 47
212 5
213 61
214 13
215 431
216 433
217 29
218 23
219 439
220 7
221 443
222 89
223 149
224 449
225 41
226 151
227 13
228 457
229 3
230 461
231 463
232 31
233 467
234 67
235 157
236 43
237 5
238 53
239 479
240 481
241 23
242 97
243 487
244 489
245 491
246 29
247 99
248 71
249 499
250 167
251 503
252 505
253 507
254 509
255 73
256 27
257 515
258 517
259 173
260 521
261 523
262 25
263 31
264 529
265 177
266 41
267 107
268 179
269 77
270 541
271 543
272 109
273 547
274 549
275 29
276 79
277 185
278 557
279 43
280 33
281 563
282 565
283 81
284 569
285 571
286 191
287 25
288 577
289 193
290 83
291 583
292 1
293 587
294 31
295 197
296 593
297 17
298 199
299 599
300 601
301 201
302 605
303 607
304 29
305 47
306 613
307 205
308 617
309 619
310 9
311 89
312 625
313 1
314 629
315 631
316 211
317 127
318 7
319 71
320 641
321 643
322 43
323 647
324 59
325 93
326 653
327 131
328 657
329 659
330 661
331 17
332 1
333 29
334 669
335 61
336 673
337 27
338 677
339 97
340 227
341 683
342 137
343 229
344 689
345 691
346 21
347 139
348 697
349 233
350 701
351 37
352 141
353 707
354 709
355 711
356 31
357 13
358 239
359 719
360 721
361 723
362 29
363 727
364 729
365 731
366 733
367 49
368 737
369 739
370 247
371 743
372 149
373 83
374 107
375 751
376 251
377 151
378 757
379 11
380 761
381 109
382 17
383 767
384 769
385 257
386 773
387 155
388 37
389 779
390 781
391 29
392 157
393 787
394 263
395 791
396 793
397 53
398 797
399 799
400 89
401 803
402 7
403 269
404 809
405 811
406 271
407 163
408 817
409 91
410 821
411 823
412 55
413 827
414 829
415 277
416 833
417 167
418 93
419 839
420 841
421 281
422 169
423 121
424 283
425 37
426 853
427 19
428 857
429 859
430 41
431 863
432 173
433 289
434 79
435 67
436 97
437 25
438 877
439 293
440 881
441 883
442 59
443 887
444 889
445 9
446 893
447 179
448 1
449 31
450 53
451 301
452 181
453 907
454 101
455 911
456 83
457 61
458 917
459 919
460 307
461 71
462 37
463 103
464 929
465 931
466 311
467 1
468 937
469 313
470 941
471 41
472 1
473 947
474 73
475 317
476 953
477 191
478 1
479 137
480 961
481 107
482 193
483 967
484 19
485 971
486 139
487 1
488 977
489 979
490 327
491 983
492 197
493 329
494 43
495 991
496 331
497 199
498 997
499 333
500 77
501 59
502 67
503 1007
504 1009
505 337
506 1013
507 7
508 113
509 1019
510 1021
511 11
512 205
513 1027
514 343
515 1031
516 1033
517 3
518 61
519 1039
520 347
521 149
522 209
523 349
524 1049
525 1051
526 351
527 211
528 151
529 353
530 1061
531 1063
532 71
533 1067
534 1069
535 1
536 37
537 215
538 359
539 1079
540 1081
541 361
542 1
543 1087
544 121
545 1091
546 1093
547 73
548 1097
549 157
550 367
551 1103
552 13
553 123
554 1109
555 101
556 53
557 223
558 1117
559 373
560 59
561 1123
562 25
563 161
564 1129
565 13
566 103
567 227
568 379
569 67
570 163
571 381
572 229
573 37
574 383
575 1151
576 1153
577 1
578 1157
579 61
580 387
581 1163
582 233
583 389
584 167
585 1171
586 391
587 47
588 107
589 131
590 1181
591 169
592 79
593 1187
594 41
595 397
596 1193
597 239
598 3
599 109
600 1201
601 401
602 241
603 1207
604 1
605 173
606 1213
607 81
608 1217
609 1219
610 407
611 1223
612 7
613 409
614 1229
615 1231
616 137
617 1
618 1237
619 59
620 1241
621 1243
622 83
623 43
624 1249
625 139
626 179
627 1255
628 419
629 1259
630 97
631 421
632 1265
633 181
634 47
635 41
636 67
637 425
638 1277
639 1279
640 61
641 1283
642 257
643 11
644 1289
645 1291
646 431
647 37
648 1297
649 433
650 1301
651 1303
652 5
653 1307
654 187
655 23
656 101
657 1315
658 439
659 1319
660 1321
661 21
662 1325
663 1327
664 443
665 1331
666 43
667 89
668 191
669 103
670 149
671 1343
672 269
673 449
674 71
675 193
676 41
677 1355
678 1357
679 151
680 1361
681 47
682 65
683 1367
684 1369
685 457
686 1373
687 125
688 153
689 1379
690 1381
691 461
692 277
693 73
694 463
695 1391
696 1393
697 1
698 127
699 1399
700 467
701 1403
702 281
703 469
704 1409
705 1411
706 157
707 283
708 1417
709 43
710 49
711 1423
712 5
713 1427
714 1429
715 53
716 1433
717 41
718 479
719 1439
720 131
721 13
722 289
723 1447
724 23
725 1451
726 1453
727 97
728 47
729 1459
730 1461
731 19
732 293
733 1467
734 1469
735 1471
736 491
737 295
738 1477
739 3
740 1481
741 1483
742 27
743 1487
744 1489
745 497
746 1493
747 299
748 499
749 1499
750 1501
751 501
752 1505
753 137
754 503
755 1511
756 89
757 1515
758 41
759 49
760 1521
761 1523
762 1525
763 509
764 139
765 1531
766 219
767 307
768 53
769 1539
770 1541
771 1543
772 103
773 1
774 1549
775 47
776 1553
777 1555
778 173
779 1559
780 223
781 521
782 1565
783 1567
784 523
785 1571
786 11
787 525
788 1577
789 1579
790 1
791 1583
792 317
793 529
794 1589
795 43
796 531
797 1
798 1597
799 41
800 1601
801 1603
802 535
803 1607
804 1609
805 179
806 1613
807 95
808 49
809 1619
810 1621
811 1623
812 125
813 1627
814 1629
815 233
816 71
817 109
818 1637
819 149
820 1641
821 53
822 47
823 1647
824 97
825 127
826 19
827 331
828 1657
829 79
830 151
831 1663
832 3
833 1667
834 1669
835 557
836 1673
837 335
838 129
839 73
840 1681
841 9
842 337
843 1687
844 563
845 1691
846 1693
847 339
848 1697
849 1699
850 1701
851 1703
852 1
853 569
854 1709
855 1711
856 571
857 343
858 101
859 191
860 1721
861 1723
862 5
863 157
864 247
865 577
866 1733
867 347
868 193
869 47
870 1741
871 83
872 349
873 1747
874 53
875 1751
876 1753
877 195
878 251
879 1759
880 587
881 43
882 1765
883 19
884 1769
885 1
886 197
887 1775
888 1777
889 593
890 1781
891 1783
892 17
893 1787
894 1789
895 597
896 163
897 359
898 599
899 257
900 1801
901 601
902 1805
903 1807
904 603
905 1811
906 7
907 55
908 79
909 1819
910 607
911 1823
912 1825
913 29
914 59
915 1831
916 611
917 367
918 167
919 613
920 263
921 97
922 3
923 1847
924 1849
925 617
926 1853
927 265
928 619
929 169
930 1861
931 27
932 1865
933 1867
934 89
935 1871
936 1873
937 625
938 1877
939 1879
940 1
941 269
942 29
943 17
944 1889
945 61
946 631
947 379
948 271
949 211
950 1901
951 173
952 127
953 1907
954 83
955 7
956 1913
957 383
958 213
959 101
960 1921
961 641
962 1
963 47
964 643
965 1931
966 1933
967 1
968 149
969 277
970 647
971 1943
972 389
973 177
974 1949
975 1951
976 279
977 17
978 103
979 653
980 53
981 151
982 393
983 281
984 179
985 1971
986 1973
987 79
988 659
989 1979
990 283
991 661
992 397
993 1987
994 51
995 181
996 1993
997 1
998 1997
999 1999
1000 87
1001 2003
1002 401
1003 2007
1004 7
1005 2011
1006 61
1007 31
1008 2017
1009 2019
1010 47
1011 289
1012 405
1013 2027
1014 2029
1015 677
1016 107
1017 1
1018 97
1019 2039
1020 2041
1021 227
1022 409
1023 89
1024 683
1025 293
1026 2053
1027 137
1028 11
1029 2059
1030 687
1031 2063
1032 413
1033 689
1034 2069
1035 109
1036 691
1037 415
1038 2077
1039 63
1040 2081
1041 2083
1042 139
1043 2087
1044 2089
1045 1
1046 91
1047 419
1048 233
1049 2099
1050 191
1051 701
1052 421
1053 49
1054 3
1055 2111
1056 2113
1057 423
1058 2117
1059 2119
1060 101
1061 193
1062 25
1063 2127
1064 2129
1065 2131
1066 2133
1067 61
1068 2137
1069 713
1070 2141
1071 2143
1072 13
1073 113
1074 307
1075 717
1076 2153
1077 431
1078 719
1079 127
1080 2161
1081 2163
1082 433
1083 197
1084 2169
1085 2171
1086 53
1087 29
1088 2177
1089 2179
1090 2181
1091 59
1092 437
1093 2187
1094 199
1095 2191
1096 1
1097 439
1098 2197
1099 733
1100 2201
1101 2203
1102 49
1103 2207
1104 2209
1105 67
1106 2213
1107 443
1108 739
1109 317
1110 2221
1111 19
1112 89
1113 131
1114 743
1115 2231
1116 29
1117 149
1118 2237
1119 2239
1120 83
1121 2243
1122 449
1123 107
1124 173
1125 2251
1126 751
1127 1
1128 61
1129 251
1130 133
1131 2263
1132 151
1133 2267
1134 2269
1135 757
1136 2273
1137 35
1138 23
1139 53
1140 2281
1141 761
1142 457
1143 2287
1144 763
1145 2291
1146 2293
1147 1
1148 2297
1149 209
1150 59
1151 49
1152 461
1153 769
1154 2309
1155 2311
1156 257
1157 463
1158 331
1159 773
1160 211
1161 2323
1162 155
1163 179
1164 2329
1165 1
1166 2333
1167 467
1168 19
1169 2339
1170 2341
1171 71
1172 67
1173 2347
1174 87
1175 2351
1176 181
1177 157
1178 2357
1179 2359
1180 787
1181 2363
1182 1
1183 263
1184 2369
1185 2371
1186 791
1187 475
1188 2377
1189 61
1190 2381
1191 2383
1192 53
1193 217
1194 2389
1195 797
1196 2393
1197 479
1198 17
1199 2399
1200 2401
1201 89
1202 1
1203 2407
1204 73
1205 2411
1206 2413
1207 23
1208 2417
1209 59
1210 269
1211 2423
1212 97
1213 809
1214 347
1215 17
1216 811
1217 487
1218 2437
1219 271
1220 2441
1221 349
1222 163
1223 2447
1224 2449
1225 19
1226 223
1227 491
1228 3
1229 2459
1230 2461
1231 821
1232 493
1233 2467
1234 823
1235 353
1236 2473
1237 1
1238 2477
1239 67
1240 827
1241 191
1242 71
1243 829
1244 2489
1245 53
1246 277
1247 499
1248 227
1249 17
1250 61
1251 2503
1252 835
1253 2507
1254 193
1255 279
1256 359
1257 2515
1258 839
1259 229
1260 2521
1261 841
1262 2525
1263 361
1264 281
1265 2531
1266 2533
1267 13
1268 59
1269 2539
1270 11
1271 2543
1272 509
1273 283
1274 2549
1275 2551
1276 23
1277 365
1278 2557
1279 853
1280 197
1281 233
1282 5
1283 2567
1284 367
1285 857
1286 2573
1287 2575
1288 859
1289 2579
1290 89
1291 1
1292 1
1293 199
1294 863
1295 2591
1296 2593
1297 173
1298 53
1299 2599
1300 289
1301 137
1302 2605
1303 79
1304 2609
1305 373
1306 67
1307 2615
1308 2617
1309 291
1310 2621
1311 61
1312 125
1313 71
1314 239
1315 877
1316 2633
1317 31
1318 293
1319 1
1320 139
1321 881
1322 529
1323 2647
1324 883
1325 241
1326 379
1327 59
1328 2657
1329 2659
1330 887
1331 2663
1332 1
1333 127
1334 157
1335 2671
1336 297
1337 535
1338 2677
1339 1
1340 383
1341 2683
1342 179
1343 2687
1344 2689
1345 1
1346 2693
1347 11
1348 31
1349 2699
1350 73
1351 53
1352 541
1353 2707
1354 1
1355 2711
1356 2713
1357 181
1358 11
1359 2719
1360 907
1361 389
1362 545
1363 101
1364 2729
1365 2731
1366 911
1367 547
1368 1
1369 913
1370 2741
1371 211
1372 61
1373 67
1374 2749
1375 131
1376 2753
1377 5
1378 919
1379 2759
1380 2761
1381 307
1382 395
1383 2767
1384 71
1385 163
1386 59
1387 925
1388 2777
1389 397
1390 103
1391 121
1392 557
1393 929
1394 2789
1395 2791
1396 7
1397 1
1398 2797
1399 311
1400 2801
1401 2803
1402 5
1403 401
1404 2809
1405 937
1406 97
1407 2815
1408 313
1409 2819
1410 31
1411 941
1412 2825
1413 257
1414 1
1415 149
1416 2833
1417 3
1418 2837
1419 167
1420 947
1421 2843
1422 569
1423 73
1424 37
1425 2851
1426 317
1427 2855
1428 2857
1429 953
1430 2861
1431 409
1432 955
1433 61
1434 151
1435 1
1436 13
1437 125
1438 137
1439 2879
1440 67
1441 961
1442 577
1443 2887
1444 107
1445 413
1446 263
1447 193
1448 2897
1449 223
1450 967
1451 2903
1452 83
1453 323
1454 2909
1455 71
1456 971
1457 11
1458 2917
1459 139
1460 127
1461 2923
1462 15
1463 2927
1464 101
1465 977
1466 419
1467 587
1468 979
1469 2939
1470 2941
1471 981
1472 19
1473 421
1474 983
1475 227
1476 2953
1477 197
1478 2957
1479 2959
1480 1
1481 2963
1482 593
1483 1
1484 2969
1485 2971
1486 991
1487 85
1488 229
1489 993
1490 2981
1491 2983
1492 199
1493 103
1494 427
1495 997
1496 73
1497 599
1498 999
1499 2999
1500 3001
1501 11
1502 3005
1503 97
1504 1003
1505 3011
1506 131
1507 335
1508 431
1509 3019
1510 19
1511 3023
1512 3025
1513 1009
1514 233
1515 433
1516 337
1517 607
1518 3037
1519 1013
1520 3041
1521 3043
1522 1
1523 277
1524 3049
1525 339
1526 71
1527 5
1528 1019
1529 19
1530 3061
1531 1021
1532 3065
1533 3067
1534 1
1535 3071
1536 439
1537 25
1538 3077
1539 3079
1540 79
1541 3083
1542 617
1543 147
1544 3089
1545 281
1546 1031
1547 619
1548 3097
1549 1033
1550 443
1551 107
1552 45
1553 239
1554 3109
1555 1037
1556 283
1557 445
1558 1039
1559 3119
1560 3121
1561 347
1562 3125
1563 59
1564 149
1565 101
1566 241
1567 19
1568 3137
1569 73
1570 1047
1571 449
1572 629
1573 1049
1574 67
1575 137
1576 1051
1577 631
1578 11
1579 81
1580 109
1581 3163
1582 211
1583 3167
1584 3169
1585 151
1586 3173
1587 127
1588 353
1589 3179
1590 3181
1591 1061
1592 1
1593 3187
1594 1063
1595 3191
1596 103
1597 71
1598 3197
1599 457
1600 1067
1601 3203
1602 641
1603 1069
1604 3209
1605 247
1606 1
1607 643
1608 3217
1609 37
1610 3221
1611 3223
1612 1
1613 461
1614 3229
1615 359
1616 61
1617 647
1618 83
1619 79
1620 463
1621 23
1622 649
1623 191
1624 361
1625 3251
1626 3253
1627 1
1628 3257
1629 3259
1630 1087
1631 251
1632 653
1633 363
1634 467
1635 3271
1636 1091
1637 131
1638 113
1639 1093
1640 193
1641 67
1642 73
1643 173
1644 23
1645 1097
1646 3293
1647 659
1648 157
1649 3299
1650 3301
1651 367
1652 661
1653 3307
1654 1103
1655 1
1656 3313
1657 1
1658 107
1659 3319
1660 9
1661 3323
1662 1
1663 1109
1664 3329
1665 3331
1666 101
1667 23
1668 71
1669 1
1670 257
1671 3343
1672 223
1673 3347
1674 197
1675 1117
1676 479
1677 61
1678 373
1679 3359
1680 3361
1681 59
1682 673
1683 37
1684 1123
1685 3371
1686 3373
1687 5
1688 307
1689 109
1690 23
1691 199
1692 677
1693 1129
1694 3389
1695 3391
1696 29
1697 97
1698 79
1699 1133
1700 179
1701 3403
1702 227
1703 3407
1704 487
1705 1137
1706 3413
1707 683
1708 67
1709 263
1710 3421
1711 163
1712 137
1713 3427
1714 1143
1715 73
1716 3433
1717 229
1718 491
1719 181
1720 37
1721 3443
1722 1
1723 383
1724 3449
1725 29
1726 1151
1727 691
1728 3457
1729 1153
1730 3461
1731 3463
1732 33
1733 3467
1734 3469
1735 89
1736 3473
1737 139
1738 61
1739 497
1740 3481
1741 27
1742 697
1743 3487
1744 1163
1745 3491
1746 499
1747 233
1748 269
1749 3499
1750 389
1751 113
1752 701
1753 167
1754 3509
1755 3511
1756 1171
1757 37
1758 3517
1759 391
1760 503
1761 271
1762 1
1763 3527
1764 3529
1765 107
1766 3533
1767 101
1768 393
1769 3539
1770 3541
1771 1181
1772 709
1773 3547
1774 13
1775 67
1776 17
1777 79
1778 3557
1779 3559
1780 1187
1781 509
1782 23
1783 1189
1784 83
1785 3571
1786 1191
1787 1
1788 511
1789 1193
1790 3581
1791 3583
1792 239
1793 3587
1794 3589
1795 9
1796 3593
1797 719
1798 109
1799 61
1800 277
1801 1201
1802 103
1803 3607
1804 401
1805 3611
1806 3613
1807 241
1808 3617
1809 1
1810 1207
1811 3623
1812 145
1813 3
1814 3629
1815 3631
1816 173
1817 727
1818 3637
1819 1213
1820 3641
1821 3643
1822 243
1823 521
1824 3649
1825 1217
1826 281
1827 17
1828 23
1829 3659
1830 523
1831 407
1832 733
1833 3667
1834 1223
1835 3671
1836 3673
1837 7
1838 3677
1839 283
1840 409
1841 3683
1842 737
1843 1229
1844 17
1845 3691
1846 1231
1847 739
1848 3697
1849 137
1850 3701
1851 529
1852 19
1853 3707
1854 3709
1855 1237
1856 79
1857 743
1858 1
1859 3719
1860 3721
1861 1241
1862 149
1863 3727
1864 1243
1865 41
1866 3733
1867 83
1868 3737
1869 3739
1870 1247
1871 3743
1872 107
1873 1249
1874 163
1875 121
1876 139
1877 751
1878 289
1879 179
1880 3761
1881 71
1882 251
1883 3767
1884 3769
1885 419
1886 49
1887 755
1888 1259
1889 3779
1890 3781
1891 97
1892 757
1893 541
1894 421
1895 223
1896 3793
1897 1
1898 3797
1899 3799
1900 181
1901 3803
1902 761
1903 3
1904 293
1905 3811
1906 41
1907 109
1908 347
1909 1273
1910 3821
1911 3823
1912 5
1913 3827
1914 547
1915 1277
1916 3833
1917 1
1918 1279
1919 349
1920 167
1921 1
1922 769
1923 3847
1924 1283
1925 3851
1926 3853
1927 257
1928 551
1929 227
1930 1
1931 3863
1932 773
1933 1289
1934 73
1935 79
1936 1291
1937 775
1938 3877
1939 431
1940 3881
1941 3883
1942 37
1943 13
1944 3889
1945 1297
1946 229
1947 779
1948 433
1949 557
1950 83
1951 1301
1952 781
1953 3907
1954 1303
1955 3911
1956 43
1957 87
1958 3917
1959 3919
1960 1307
1961 3923
1962 157
1963 11
1964 3929
1965 3931
1966 19
1967 787
1968 3937
1969 101
1970 563
1971 3943
1972 263
1973 3947
1974 3949
1975 439
1976 67
1977 113
1978 1319
1979 3959
1980 233
1981 1321
1982 1
1983 3967
1984 9
1985 3971
1986 3973
1987 1
1988 3977
1989 173
1990 1327
1991 569
1992 797
1993 443
1994 3989
1995 307
1996 1331
1997 1
1998 571
1999 1333
2000 4001