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