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