0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 2 11 2 12 8 13 6 14 5 15 5 16 4 17 4 18 4 19 4 20 2 21 12 22 2 23 5 24 8 25 4 26 6 27 3 28 5 29 3 30 2 31 12 32 7 33 2 34 4 35 4 36 8 37 3 38 3 39 6 40 2 41 12 42 12 43 5 44 2 45 4 46 5 47 3 48 8 49 3 50 2 51 12 52 7 53 5 54 4 55 2 56 3 57 3 58 3 59 3 60 2 61 12 62 12 63 12 64 7 65 4 66 2 67 3 68 4 69 5 70 2 71 12 72 7 73 5 74 4 75 4 76 3 77 2 78 3 79 3 80 2 81 12 82 12 83 5 84 12 85 4 86 5 87 3 88 2 89 3 90 2 91 12 92 7 93 12 94 4 95 4 96 7 97 3 98 3 99 2 100 12 101 12 102 298 103 203 104 158 105 133 106 111 107 97 108 88 109 80 110 68 111 12 112 1230 113 793 114 580 115 453 116 371 117 312 118 270 119 237 120 907 121 881 122 879 123 10494 124 8080 125 6454 126 5527 127 4742 128 4271 129 3804 130 511 131 508 132 10024 133 506 134 5207 135 4248 136 3617 137 3156 138 2817 139 2560 140 362 141 358 142 7854 143 5288 144 364 145 3314 146 2853 147 2473 148 2239 149 2007 150 288 151 283 152 6611 153 4507 154 3458 155 294 156 2409 157 2113 158 1887 159 1717 160 234 161 233 162 5999 163 4054 164 3137 165 2537 166 242 167 1893 168 1712 169 1539 170 201 171 203 172 5525 173 3764 174 2884 175 2358 176 2007 177 210 178 1571 179 1425 180 181 181 181 182 5307 183 3583 184 2772 185 2241 186 1922 187 1667 188 190 189 1362 190 164 191 165 192 5093 193 3469 194 2652 195 2166 196 1842 197 1609 198 1438 199 174 200 12 201 562 202 12 203 192 204 298 205 122 206 203 207 86 208 158 209 69 210 4633 211 4293 212 4015 213 74543 214 53770 215 41475 216 33539 217 27936 218 23879 219 20751 220 68 221 2612 222 12 223 832 224 1230 225 483 226 793 227 335 228 580 229 254 230 699 231 44700 232 677 233 668 234 11181 235 8925 236 7482 237 6391 238 5620 239 5005 240 907 241 30653 242 881 243 10279 244 879 245 6210 246 10494 247 4471 248 8080 249 3509 250 342 251 23628 252 326 253 7999 254 6072 255 333 256 4111 257 3539 258 3138 259 2801 260 511 261 19459 262 508 263 6595 264 10024 265 4009 266 506 267 2907 268 5207 269 2301 270 211 271 16847 272 212 273 5734 274 4367 275 3510 276 2973 277 210 278 2275 279 2044 280 362 281 15000 282 358 283 5088 284 7854 285 3107 286 5288 287 2260 288 364 289 1787 290 158 291 13734 292 157 293 4688 294 3572 295 2873 296 2438 297 2100 298 1867 299 160 300 12 301 562 302 287 303 12 304 147 305 122 306 298 307 86 308 77 309 203 310 6573 311 6056 312 238174 313 5264 314 106997 315 81779 316 65392 317 53978 318 45641 319 39321 320 1857 321 155026 322 1731 323 1655 324 36905 325 28492 326 23736 327 19692 328 17268 329 14900 330 68 331 2635 332 1300 333 12 334 631 335 499 336 1230 337 349 338 303 339 793 340 568 341 52798 342 26722 343 539 344 541 345 10444 346 8829 347 7437 348 6625 349 5778 350 413 351 38771 352 19395 353 388 354 9713 355 396 356 6500 357 5577 358 4886 359 4355 360 907 361 30697 362 15634 363 881 364 7888 365 6246 366 879 367 4504 368 4018 369 10494 370 240 371 25489 372 12801 373 238 374 6457 375 5192 376 4355 377 233 378 3292 379 2947 380 202 381 21968 382 11192 383 199 384 5676 385 4489 386 3823 387 3245 388 198 389 2559 390 511 391 19463 392 9804 393 508 394 4976 395 4011 396 10024 397 2909 398 2564 399 506 400 12 401 562 402 562 403 192 404 12 405 122 406 192 407 86 408 298 409 69 410 8523 411 7825 412 402385 413 251967 414 6341 415 135801 416 108057 417 88673 418 74622 419 63911 420 4633 421 253877 422 4293 423 79951 424 4015 425 45646 426 74543 427 31213 428 53770 429 23357 430 1117 431 128462 432 63389 433 1045 434 1023 435 24329 436 20125 437 16991 438 14738 439 12987 440 68 441 2646 442 2612 443 864 444 12 445 508 446 832 447 357 448 1230 449 275 450 491 451 58038 452 28988 453 19214 454 452 455 465 456 9550 457 8144 458 7132 459 6314 460 699 461 44717 462 44700 463 14893 464 677 465 8893 466 668 467 6338 468 11181 469 4935 470 275 471 36340 472 18247 473 12134 474 269 475 7296 476 6109 477 265 478 4598 479 4077 480 907 481 30711 482 30653 483 10331 484 881 485 6256 486 10279 487 4512 488 879 489 3545 490 193 491 26568 492 13378 493 8930 494 188 495 5380 496 4524 497 3870 498 3411 499 186 500 12 501 562 502 287 503 192 504 147 505 12 506 100 507 86 508 77 509 69 510 10470 511 9597 512 608924 513 380221 514 268667 515 7273 516 161310 517 132013 518 110661 519 94523 520 2839 521 377375 522 2622 523 118152 524 87664 525 2330 526 55463 527 45618 528 39715 529 33960 530 1331 531 186976 532 91824 533 1239 534 44412 535 1185 536 28811 537 24289 538 20974 539 18461 540 809 541 115983 542 58340 543 37863 544 760 545 736 546 18720 547 15654 548 13870 549 11994 550 68 551 2652 552 1317 553 870 554 648 555 12 556 425 557 361 558 315 559 279 560 404 561 61691 562 31226 563 20472 564 15517 565 382 566 381 567 8654 568 7676 569 6715 570 312 571 49309 572 24615 573 16388 574 12274 575 301 576 8165 577 296 578 6111 579 5430 580 256 581 40959 582 20787 583 13647 584 10432 585 246 586 6930 587 5854 588 245 589 4558 590 212 591 35024 592 17526 593 11721 594 8780 595 205 596 5879 597 5034 598 4411 599 205 600 12 601 562 602 562 603 562 604 287 605 122 606 12 607 86 608 147 609 192 610 12423 611 11369 612 858896 613 534839 614 377195 615 284953 616 8092 617 183987 618 153944 619 131152 620 6573 621 525200 622 6056 623 163664 624 238174 625 92470 626 5264 627 62591 628 106997 629 46380 630 4633 631 256615 632 125942 633 4293 634 60692 635 47672 636 4015 637 32982 638 28465 639 74543 640 1857 641 156971 642 155026 643 51024 644 1731 645 29902 646 1655 647 20899 648 36905 649 15937 650 651 651 108763 652 54036 653 35683 654 26599 655 609 656 577 657 14856 658 12937 659 11414 660 68 661 2656 662 2635 663 2612 664 1300 665 518 666 12 667 365 668 631 669 832 670 349 671 64382 672 32162 673 21321 674 15978 675 12717 676 334 677 331 678 7904 679 6995 680 568 681 52878 682 52798 683 17558 684 26722 685 10487 686 539 687 7464 688 541 689 5791 690 699 691 44789 692 22458 693 44700 694 11227 695 8956 696 677 697 6398 698 5617 699 668 700 12 701 562 702 287 703 192 704 147 705 122 706 100 707 12 708 77 709 69 710 14372 711 13143 712 1150972 713 715786 714 503752 715 380097 716 300068 717 8812 718 204248 719 173786 720 3826 721 697638 722 3518 723 216753 724 160260 725 122121 726 100635 727 2911 728 71527 729 60922 730 1763 731 337187 732 164985 733 1630 734 79220 735 62186 736 51031 737 1485 738 36883 739 32354 740 1054 741 204310 742 102466 743 66232 744 978 745 38727 746 32431 747 919 748 23875 749 20543 750 733 751 140191 752 69419 753 45849 754 34076 755 683 756 22329 757 636 758 16484 759 14545 760 510 761 104059 762 52544 763 34319 764 25945 765 20285 766 479 767 470 768 12675 769 11051 770 68 771 2659 772 1324 773 877 774 655 775 521 776 432 777 12 778 321 779 284 780 314 781 66442 782 33652 783 22013 784 16796 785 13136 786 11090 787 296 788 298 789 7224 790 257 791 55782 792 27839 793 18573 794 13869 795 11077 796 9238 797 246 798 6891 799 245 800 12 801 562 802 562 803 192 804 562 805 122 806 192 807 86 808 12 809 69 810 16326 811 14917 812 1486709 813 923100 814 649039 815 488939 816 385632 817 313857 818 9457 819 222439 820 8523 821 894412 822 7825 823 277151 824 402385 825 155751 826 251967 827 104850 828 6341 829 77276 830 1980 831 428876 832 209795 833 1827 834 100494 835 78718 836 64590 837 54138 838 1624 839 40772 840 4633 841 257998 842 253877 843 83528 844 4293 845 48779 846 79951 847 33981 848 4015 849 25821 850 814 851 175661 852 87015 853 57320 854 42617 855 757 856 27872 857 23637 858 695 859 18062 860 1117 861 129444 862 128462 863 42589 864 63389 865 25106 866 1045 867 17683 868 1023 869 13610 870 427 871 100760 872 50192 873 33215 874 24824 875 19721 876 16382 877 401 878 398 879 10753 880 68 881 2661 882 2646 883 879 884 2612 885 523 886 864 887 370 888 12 889 286 890 280 891 68068 892 34019 893 22620 894 16916 895 13465 896 11248 897 9575 898 267 899 266 900 12 901 562 902 287 903 562 904 147 905 122 906 287 907 86 908 77 909 12 910 18275 911 16691 912 1864309 913 1156775 914 812260 915 611498 916 481657 917 391747 918 326406 919 10028 920 4814 921 1115798 922 4416 923 345155 924 254676 925 193622 926 159246 927 130147 928 112698 929 3410 930 6573 931 531680 932 259634 933 6056 934 124175 935 97283 936 238174 937 66801 938 57372 939 5264 940 1300 941 317728 942 159077 943 102592 944 1203 945 59745 946 49951 947 41495 948 36627 949 1085 950 895 951 215163 952 106330 953 70102 954 51998 955 831 956 33948 957 28801 958 24958 959 751 960 1857 961 157732 962 79547 963 155026 964 39146 965 30547 966 1731 967 21497 968 19001 969 1655 970 467 971 122056 972 60640 973 40180 974 29941 975 23810 976 19735 977 436 978 14631 979 433 980 379 981 98314 982 49732 983 32471 984 24741 985 19296 986 16284 987 13665 988 353 989 352 990 68 991 2662 992 1327 993 2635 994 658 995 524 996 1300 997 371 998 324 999 12 1000 562