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