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