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