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