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