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