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