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