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