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