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