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