0 0 1 1 2 3 3 6 4 7 5 12 6 12 7 13 8 21 9 30 10 25 11 36 12 30 13 28 14 28 15 29 16 45 17 62 18 49 19 68 20 54 21 48 22 46 23 46 24 47 25 72 26 62 27 58 28 57 29 86 30 73 31 104 32 84 33 75 34 109 35 144 36 108 37 91 38 129 39 168 40 124 41 103 42 145 43 188 44 138 45 114 46 103 47 150 48 123 49 172 50 136 51 119 52 171 53 224 54 166 55 138 56 125 57 182 58 149 59 208 60 164 61 143 62 205 63 268 64 198 65 164 66 148 67 141 68 209 69 278 70 209 71 280 72 212 73 179 74 253 75 328 76 240 77 197 78 275 79 354 80 257 81 338 82 251 83 334 84 251 85 336 86 254 87 214 88 195 89 284 90 232 91 207 92 299 93 392 94 290 95 240 96 216 97 205 98 303 99 402 100 301 101 402 102 303 103 406 104 307 105 412 106 312 107 263 108 371 109 480 110 350 111 286 112 255 113 368 114 298 115 264 116 248 117 241 118 359 119 478 120 359 121 480 122 362 123 304 124 276 125 263 126 389 127 516 128 386 129 322 130 291 131 422 132 343 133 476 134 372 135 321 136 457 137 594 138 435 139 574 140 427 141 568 142 426 143 356 144 322 145 306 146 299 147 446 148 371 149 520 150 410 151 356 152 330 153 318 154 313 155 468 156 390 157 352 158 334 159 326 160 323 161 484 162 404 163 365 164 529 165 694 166 513 167 680 168 508 169 423 170 593 171 764 172 554 173 450 174 399 175 574 176 463 177 640 178 498 179 428 180 394 181 378 182 371 183 554 184 461 185 646 186 509 187 696 188 536 189 457 190 647 191 838 192 611 193 804 194 596 195 493 196 689 197 886 198 641 199 840 200 620 201 511 202 713 203 916 204 662 205 536 206 474 207 444 208 430 209 424 210 422 211 422 212 423 213 636 214 532 215 481 216 697 217 914 218 675 219 894 220 667 221 888 222 666 223 556 224 502 225 476 226 464 227 459 228 687 229 916 230 688 231 575 232 807 233 1040 234 754 235 612 236 542 237 508 238 492 239 485 240 725 241 966 242 725 243 968 244 728 245 609 246 855 247 1102 248 799 249 1048 250 774 251 638 252 571 253 824 254 666 255 588 256 550 257 532 258 524 259 521 260 781 261 1042 262 783 263 1046 264 787 265 1052 266 792 267 663 268 931 269 1200 270 870 271 706 272 625 273 898 274 723 275 998 276 775 277 1052 278 804 279 681 280 961 281 1242 282 903 283 1186 284 877 285 1162 286 867 287 1154 288 865 289 1154 290 867 291 1158 292 871 293 1164 294 876 295 733 296 1029 297 1326 298 961 299 1260 300 930 301 766 302 685 303 988 304 798 305 704 306 658 307 636 308 626 309 622 310 621 311 932 312 778 313 702 314 665 315 980 316 806 317 720 318 678 319 658 320 649 321 970 322 807 323 1130 324 889 325 1214 326 933 327 1260 328 958 329 808 330 734 331 698 332 681 333 1014 334 841 335 1176 336 924 337 799 338 1137 339 1476 340 1078 341 880 342 782 343 734 344 711 345 1056 346 874 347 784 348 740 349 719 350 1069 351 1420 352 1062 353 884 354 796 355 753 356 1109 357 1466 358 1091 359 1450 360 1085 361 1446 362 1085 363 1448 364 1088 365 909 366 1275 367 1642 368 1189 369 1558 370 1149 371 1520 372 1132 373 939 374 1313 375 1688 376 1220 377 987 378 1365 379 1744 380 1252 381 1007 382 1389 383 1772 384 1270 385 1020 386 896 387 835 388 1223 389 1612 390 1196 391 989 392 1381 393 1774 394 1281 395 1676 396 1234 397 1014 398 905 399 1304 400 1052 401 927 402 1329 403 1732 404 1270 405 1040 406 926 407 870 408 843 409 1252 410 1036 411 929 412 1341 413 1754 414 1291 415 1706 416 1269 417 1686 418 1261 419 1680 420 1260 421 1051 422 1473 423 1896 424 1372 425 1111 426 1537 427 1964 428 1410 429 1134 430 997 431 1428 432 1146 433 1006 434 937 435 1372 436 1122 437 998 438 937 439 1376 440 1128 441 1005 442 1447 443 1890 444 1389 445 1834 446 1363 447 1810 448 1353 449 1802 450 1351 451 1802 452 1353 453 1806 454 1357 455 1812 456 1362 457 1138 458 1027 459 1486 460 1203 461 1664 462 1294 463 1110 464 1019 465 1484 466 1208 467 1071 468 1539 469 2008 470 1474 471 1208 472 1076 473 1011 474 1485 475 1960 476 1456 477 1205 478 1683 479 2162 480 1561 481 2042 482 1503 483 1986 484 1477 485 1962 486 1467 487 1954 488 1465 489 1954 490 1467 491 1958 492 1471 493 1964 494 1476 495 1233 496 1729 497 2226 498 1611 499 2110 500 1555 501 2056 502 1530 503 1268 504 1138 505 1074 506 1043 507 1550 508 1283 509 1792 510 1406 511 1214 512 1119 513 1632 514 1330 515 1180 516 1106 517 1070 518 1053 519 1572 520 1306 521 1174 522 1109 523 1632 524 1340 525 1195 526 1721 527 2248 528 1652 529 1355 530 1885 531 2416 532 1740 533 1403 534 1937 535 2472 536 1772 537 1423 538 1961 539 2500 540 1790 541 1436 542 1260 543 1173 544 1717 545 2262 546 1677 547 2224 548 1660 549 1379 550 1929 551 2480 552 1792 553 1449 554 2003 555 2558 556 1835 557 2392 558 1754 559 1436 560 1278 561 1200 562 1162 563 1144 564 1136 565 1133 566 1699 567 2266 568 1701 569 2270 570 1705 571 2276 572 1710 573 1428 574 1288 575 1219 576 1795 577 2372 578 1764 579 1461 580 2041 581 2622 582 1893 583 2476 584 1822 585 1496 586 1334 587 1254 588 1215 589 1804 590 1492 591 1337 592 1929 593 2522 594 1855 595 2450 596 1821 597 2418 598 1807 599 2406 600 1803 601 2404 602 1804 603 1505 604 2109 605 2714 606 1963 607 2570 608 1893 609 2502 610 1861 611 2472 612 1848 613 1537 614 2151 615 2766 616 1999 617 2616 618 1926 619 1582 620 1411 621 2032 622 1638 623 1442 624 1345 625 1970 626 1611 627 2238 628 1747 629 2376 630 1818 631 1540 632 1402 633 1334 634 1301 635 1936 636 1604 637 1439 638 2077 639 2716 640 1998 641 1640 642 1462 643 1374 644 1331 645 1976 646 1634 647 1464 648 1380 649 1339 650 1989 651 2640 652 1972 653 1639 654 2293 655 2948 656 2130 657 1722 658 1519 659 2178 660 1749 661 2410 662 1867 663 2530 664 1929 665 2594 666 1963 667 2630 668 1983 669 2652 670 1996 671 1669 672 2341 673 3014 674 2181 675 2856 676 2104 677 1729 678 2407 679 3086 680 2223 681 2904 682 2134 683 1750 684 1559 685 2244 686 1808 687 1591 688 2279 689 2968 690 2174 691 1778 692 1581 693 2274 694 1831 695 2526 696 1959 697 2656 698 2026 699 1712 700 1556 701 1479 702 2181 703 2884 704 2146 705 1778 706 1595 707 2302 708 1859 709 2568 710 1994 711 1708 712 1566 713 1496 714 1462 715 1446 716 1439 717 2156 718 1796 719 1617 720 2337 721 3058 722 2251 723 2974 724 2211 725 2936 726 2194 727 1824 728 1640 729 1549 730 2279 731 3010 732 2237 733 2970 734 2219 735 2954 736 2213 737 2950 738 2213 739 2952 740 2216 741 1849 742 2591 743 3334 744 2411 745 3156 746 2324 747 1909 748 2657 749 3406 750 2453 751 3204 752 2354 753 1930 754 1719 755 2474 756 1993 757 2750 758 2133 759 2892 760 2206 761 1864 762 1694 763 1610 764 1569 765 2334 766 1933 767 2700 768 2118 769 1828 770 1684 771 1613 772 2385 773 3158 774 2353 775 3128 776 2340 777 1947 778 2725 779 3504 780 2532 781 2047 782 2829 783 3612 784 2590 785 2080 786 1826 787 1700 788 1638 789 1608 790 1594 791 1588 792 1586 793 1586 794 1587 795 2382 796 1987 797 2784 798 2190 799 1894 800 1747 801 2548 802 2076 803 1841 804 2645 805 3450 806 2531 807 3338 808 2477 809 3286 810 2453 811 3264 812 2444 813 2035 814 2849 815 3664 816 2648 817 2141 818 2959 819 3778 820 2709 821 3530 822 2587 823 3410 824 2529 825 3354 826 2503 827 3330 828 2493 829 3322 830 2491 831 3322 832 2493 833 3326 834 2497 835 3332 836 2502 837 2088 838 1882 839 1780 840 1730 841 1706 842 1695 843 2538 844 2113 845 2958 846 2325 847 3172 848 2434 849 2066 850 1883 851 2734 852 2219 853 3072 854 2390 855 2050 856 1881 857 2738 858 2227 859 3086 860 2403 861 3264 862 2494 863 2110 864 1919 865 2784 866 2258 867 1996 868 1866 869 1802 870 1771 871 2642 872 2193 873 3066 874 2407 875 3282 876 2517 877 3394 878 2575 879 3454 880 2607 881 3488 882 2626 883 2196 884 1982 885 1876 886 1824 887 1799 888 2687 889 3576 890 2678 891 2230 892 2007 893 2900 894 2344 895 2067 896 2963 897 3860 898 2828 899 2313 900 3213 901 4114 902 2959 903 3862 904 2835 905 3740 906 2776 907 2295 908 3203 909 4112 910 2966 911 2394 912 2109 913 3022 914 2425 915 3340 916 2586 917 2210 918 2023 919 2942 920 2391 921 3312 922 2578 923 2212 924 2030 925 1940 926 1896 927 1875 928 2803 929 3732 930 2796 931 2329 932 3261 933 4194 934 3031 935 3966 936 2919 937 3856 938 2866 939 2372 940 2126 941 2004 942 1944 943 1915 944 2859 945 3804 946 2848 947 2371 948 3319 949 4268 950 3084 951 2493 952 3445 953 4398 954 3153 955 4108 956 3010 957 2462 958 2189 959 3148 960 2534 961 2228 962 2076 963 2001 964 2965 965 3930 966 2931 967 3898 968 2917 969 3886 970 2913 971 3884 972 2914 973 2430 974 2189 975 3164 976 2558 977 2256 978 2106 979 2032 980 1996 981 1979 982 2961 983 3944 984 2956 985 2463 986 3449 987 4436 988 3206 989 2592 990 2286 991 2134 992 2059 993 3052 994 2520 995 2255 996 3251 997 4248 998 3122 999 2560 1000 2280