0 1 1 4 2 9 3 21 4 10 5 50 6 27 7 24 8 36 9 41 10 25 11 42 12 54 13 51 14 147 15 115 16 34 17 100 18 61 19 40 20 133 21 87 22 55 23 132 24 121 25 100 26 102 27 144 28 46 29 171 30 167 31 52 32 89 33 126 34 82 35 318 36 122 37 148 38 121 39 236 40 85 41 177 42 144 43 145 44 216 45 205 46 115 47 299 48 216 49 115 50 206 51 300 52 94 53 211 54 246 55 154 56 192 57 399 58 145 59 240 60 278 61 175 62 224 63 216 64 133 65 440 66 177 67 268 68 226 69 675 70 175 71 451 72 244 73 175 74 397 75 309 76 127 77 294 78 306 79 196 80 345 81 369 82 184 83 491 84 530 85 205 86 237 87 344 88 187 89 561 90 769 91 220 92 334 93 336 94 217 95 750 96 267 97 205 98 341 99 451 100 202 101 412 102 299 103 250 104 784 105 954 106 157 107 674 108 366 109 265 110 491 111 477 112 184 113 791 114 489 115 286 116 362 117 459 118 196 119 727 120 605 121 304 122 449 123 530 124 280 125 1065 126 432 127 184 128 356 129 660 130 250 131 917 132 454 133 280 134 549 135 615 136 232 137 369 138 501 139 352 140 931 141 472 142 265 143 546 144 621 145 274 146 477 147 394 148 322 149 951 150 618 151 537 152 509 153 816 154 358 155 990 156 447 157 385 158 571 159 897 160 376 161 442 162 549 163 490 164 954 165 810 166 247 167 469 168 576 169 325 170 685 171 422 172 382 173 561 174 1057 175 439 176 472 177 699 178 376 179 1146 180 820 181 807 182 624 183 696 184 391 185 1059 186 502 187 319 188 621 189 1737 190 400 191 517 192 534 193 313 194 827 195 1470 196 292 197 675 198 531 199 670 200 824 201 882 202 334 203 696 204 822 205 820 206 562 207 1188 208 376 209 1969 210 1325 211 322 212 594 213 1353 214 355 215 757 216 972 217 364 218 591 219 1245 220 415 221 867 222 890 223 1011 224 1560 225 773 226 307 227 904 228 726 229 451 230 1653 231 692 232 439 233 1147 234 961 235 580 236 932 237 1104 238 391 239 2390 240 1035 241 694 242 649 243 1107 244 574 245 1775 246 867 247 412 248 716 249 1909 250 421 251 727 252 849 253 535 254 1336 255 1500 256 544 257 1514 258 861 259 658 260 1298 261 1032 262 454 263 1176 264 1296 265 1512 266 857 267 1644 268 511 269 982 270 1230 271 670 272 1204 273 841 274 658 275 1350 276 1002 277 847 278 631 279 2484 280 625 281 1062 282 629 283 520 284 1475 285 2052 286 487 287 1044 288 626 289 580 290 1521 291 1287 292 664 293 2051 294 1712 295 784 296 1157 297 1134 298 610 299 1352 300 1995 301 547 302 759 303 776 304 646 305 1510 306 827 307 589 308 1146 309 1893 310 637 311 1392 312 894 313 787 314 1845 315 2862 316 652 317 1154 318 751 319 802 320 1380 321 1452 322 529 323 1426 324 1770 325 625 326 747 327 1009 328 736 329 2975 330 1473 331 826 332 1194 333 1006 334 694 335 3325 336 937 337 817 338 1316 339 2599 340 787 341 1232 342 1379 343 511 344 1137 345 1560 346 577 347 964 348 946 349 877 350 2256 351 1102 352 727 353 1136 354 1440 355 895 356 1142 357 1224 358 556 359 1749 360 1640 361 649 362 904 363 1386 364 742 365 2075 366 1337 367 757 368 1146 369 1548 370 673 371 1147 372 1074 373 1492 374 1633 375 1545 376 901 377 1479 378 1296 379 985 380 1630 381 1535 382 724 383 2056 384 3361 385 895 386 1557 387 1490 388 721 389 2819 390 1576 391 667 392 1344 393 1877 394 982 395 2263 396 1062 397 778 398 1416 399 2303 400 745 401 1861 402 1509 403 676 404 2234 405 2872 406 667 407 1554 408 1196 409 709 410 1720 411 1107 412 694 413 1386 414 1872 415 1036 416 1157 417 2614 418 661 419 2436 420 2650 421 1617 422 979 423 1416 424 796 425 1751 426 1477 427 1060 428 1151 429 2106 430 751 431 1741 432 939 433 796 434 3127 435 2110 436 706 437 1719 438 1211 439 1096 440 3927 441 1512 442 703 443 1301 444 1780 445 883 446 1207 447 2384 448 706 449 3440 450 2050 451 730 452 1674 453 1611 454 928 455 4134 456 1452 457 937 458 1101 459 2091 460 1081 461 1527 462 1384 463 736 464 2001 465 1885 466 862 467 1730 468 1836 469 937 470 1921 471 2037 472 844 473 1426 474 2038 475 1000 476 1582 477 1899 478 811 479 2417 480 2070 481 1357 482 1929 483 1586 484 850 485 3142 486 1297 487 1948 488 1261 489 4535 490 1135 491 2417 492 1119 493 841 494 3127 495 2255 496 817 497 1704 498 1711 499 1246 500 2060 501 1307 502 739 503 2266 504 2894 505 1261 506 1357 507 1974 508 736 509 3291 510 3507 511 1084 512 1424 513 1266 514 997 515 2203 516 1387 517 889 518 1776 519 3405 520 1000 521 1582 522 1419 523 736 524 3742 525 3604 526 847 527 1864 528 1416 529 1090 530 1996 531 1782 532 874 533 2301 534 2197 535 961 536 1812 537 1519 538 886 539 6094 540 2460 541 1858 542 1339 543 1356 544 946 545 3442 546 1682 547 1513 548 1266 549 2501 550 1051 551 2957 552 2004 553 901 554 1725 555 2225 556 862 557 1629 558 1591 559 1222 560 4504 561 1977 562 769 563 2806 564 2539 565 1798 566 2267 567 1944 568 766 569 4077 570 2445 571 862 572 1534 573 3056 574 1309 575 2369 576 1252 577 1192 578 1706 579 3137 580 1195 581 1992 582 1599 583 1603 584 2095 585 3295 586 877 587 2384 588 1576 589 1240 590 2400 591 2025 592 1099 593 1881 594 5345 595 1336 596 1522 597 1854 598 1081 599 2959 600 2472 601 1309 602 1789 603 2646 604 1105 605 2970 606 1552 607 1438 608 2036 609 4928 610 1165 611 1602 612 1619 613 2344 614 3004 615 6108 616 982 617 3993 618 1686 619 1546 620 2329 621 2829 622 1114 623 2136 624 2425 625 2500 626 2442 627 1994 628 1534 629 4021 630 3689 631 1144 632 1469 633 1626 634 1279 635 3340 636 2377 637 1363 638 1711 639 2911 640 1192 641 2072 642 1769 643 946 644 3682 645 3090 646 1102 647 4004 648 2196 649 1621 650 4900 651 2232 652 934 653 1896 654 2907 655 1240 656 1492 657 2349 658 1081 659 4203 660 2491 661 2293 662 2672 663 2566 664 1579 665 5250 666 1487 667 1465 668 1486 669 3624 670 1240 671 2562 672 1874 673 1630 674 2743 675 2319 676 922 677 1919 678 2026 679 1396 680 2509 681 2877 682 1144 683 2371 684 2507 685 1471 686 2352 687 1844 688 1210 689 3887 690 2273 691 1933 692 2459 693 2076 694 1270 695 2155 696 1647 697 1564 698 1646 699 5299 700 1432 701 2222 702 1889 703 1408 704 3106 705 2997 706 1132 707 2424 708 2796 709 1921 710 2879 711 2182 712 1513 713 3036 714 8981 715 1270 716 2022 717 2074 718 1258 719 5003 720 4216 721 1477 722 1564 723 3171 724 1234 725 2959 726 1947 727 1603 728 2331 729 4581 730 1231 731 2207 732 2674 733 1303 734 6055 735 4280 736 997 737 2459 738 2101 739 1630 740 3018 741 2352 742 1219 743 3866 744 3016 745 1549 746 2077 747 1954 748 1231 749 6678 750 3090 751 1456 752 1934 753 2181 754 1450 755 6168 756 2547 757 1375 758 1896 759 3726 760 1600 761 3634 762 3309 763 1441 764 3874 765 3485 766 1564 767 3009 768 2136 769 1681 770 6037 771 2612 772 1189 773 3628 774 2980 775 1738 776 2407 777 2389 778 1525 779 3037 780 3894 781 2059 782 2599 783 3096 784 1522 785 3202 786 2467 787 1294 788 2126 789 3837 790 1519 791 3277 792 2124 793 1525 794 3061 795 2994 796 1072 797 4109 798 2571 799 1531 800 3296 801 3392 802 1468 803 3655 804 4603 805 2002 806 2327 807 2424 808 1396 809 3652 810 3690 811 2200 812 2714 813 2201 814 2035 815 3649 816 2392 817 1702 818 3156 819 4920 820 1375 821 2792 822 1899 823 2302 824 3445 825 7446 826 1357 827 4149 828 1966 829 1711 830 3043 831 2787 832 1369 833 2856 834 2586 835 1735 836 1962 837 3024 838 1291 839 4657 840 5300 841 1357 842 1959 843 3186 844 1624 845 5503 846 2567 847 2110 848 2376 849 4899 850 1696 851 3772 852 2514 853 2332 854 5007 855 3769 856 1420 857 2109 858 2161 859 1732 860 5840 861 2657 862 1504 863 4301 864 3026 865 1573 866 3025 867 2674 868 1426 869 4266 870 4031 871 1675 872 2364 873 2626 874 1708 875 4639 876 2422 877 2167 878 2696 879 4618 880 1639 881 2842 882 2364 883 2061 884 3562 885 3600 886 1807 887 5009 888 3196 889 1921 890 4105 891 2617 892 1474 893 4011 894 3095 895 1951 896 2852 897 2614 898 1741 899 4770 900 3092 901 1582 902 2779 903 3096 904 1921 905 3513 906 2277 907 1825 908 2206 909 7482 910 1855 911 2257 912 2449 913 2275 914 3701 915 4530 916 1507 917 3144 918 2411 919 1588 920 3467 921 2847 922 1819 923 3621 924 6831 925 1774 926 2232 927 2529 928 1426 929 6833 930 7763 931 1387 932 2194 933 2701 934 2053 935 4520 936 2682 937 3969 938 3171 939 3650 940 1675 941 2697 942 2719 943 2116 944 6007 945 8087 946 2101 947 2029 948 3607 949 1825 950 3914 951 4257 952 1564 953 3937 954 4346 955 1738 956 2567 957 3654 958 1471 959 9303 960 3601 961 1612 962 3439 963 2546 964 1762 965 9566 966 2652 967 1795 968 2596 969 4449 970 1741 971 3707 972 3414 973 2167 974 4287 975 4017 976 1672 977 3829 978 2241 979 2497 980 6517 981 2397 982 1849 983 6396 984 4128 985 1681 986 2917 987 3384 988 1486 989 3737 990 4419 991 1996 992 2514 993 3306 994 1945 995 5162 996 3422 997 1990 998 2231 999 4005 1000 2260