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