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