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