1000 1 3 3 3 2 3 1 0 3 3 2 0 4 97 64 35 5 15 15 15 6 15 8 8 7 15 13 13 8 15 13 10 9 46 46 46 10 46 46 32 11 46 18 18 12 32 18 18 13 46 18 11 14 21 18 11 15 33 33 33 16 33 33 23 17 33 26 26 18 33 26 25 19 63 63 63 20 63 36 36 21 63 51 51 22 63 51 46 23 60 60 60 24 60 35 35 25 60 45 45 26 60 45 36 27 58 45 36 28 85 85 85 29 85 49 49 30 85 61 61 31 85 61 6 32 9 9 6 33 18 18 18 34 18 10 10 35 18 3 3 36 6 3 3 37 18 3 2 38 5 3 2 39 82 82 82 40 82 47 47 41 82 60 60 42 82 60 35 43 50 50 35 44 96 96 96 45 96 56 56 46 96 35 35 47 96 35 27 48 53 35 27 49 77 77 77 50 77 77 54 51 77 13 13 52 24 13 13 53 77 13 11 54 22 13 11 55 21 21 21 56 21 12 12 57 21 19 19 58 21 19 18 59 67 67 67 60 67 67 47 61 67 33 33 62 57 33 33 63 67 33 3 64 5 5 3 65 94 94 94 66 94 94 66 67 94 37 37 68 64 37 37 69 94 37 32 70 58 37 32 71 73 73 73 72 73 42 42 73 73 60 60 74 73 60 23 75 68 68 68 76 68 39 39 77 68 17 17 78 30 17 17 79 68 17 14 80 27 17 14 81 80 80 80 82 80 46 46 83 80 15 15 84 27 15 15 85 80 15 4 86 7 7 4 87 75 75 75 88 75 75 52 89 75 26 26 90 45 26 26 91 75 26 6 92 34 34 34 93 34 19 19 94 34 25 25 95 34 25 23 96 50 23 23 97 40 23 23 98 50 23 12 99 17 17 12 100 15 9 9 101 15 9 8 102 14 9 8 103 36 36 36 104 36 36 25 105 36 1 1 106 3 1 1 107 16 16 16 108 16 9 9 109 16 7 7 110 13 7 7 111 16 7 1 112 2 2 1 113 79 79 79 114 79 79 55 115 79 34 34 116 59 34 34 117 79 34 15 118 22 22 15 119 35 35 35 120 35 20 20 121 35 9 9 122 35 9 8 123 52 52 52 124 52 52 37 125 52 35 35 126 52 35 1 127 48 48 48 128 48 27 27 129 48 2 2 130 4 2 2 131 48 2 1 132 76 76 76 133 76 44 44 134 76 46 46 135 76 46 31 136 65 46 31 137 2 1 1 138 21 16 16 139 21 16 3 140 65 65 65 141 65 65 46 142 65 39 39 143 65 39 2 144 41 39 2 145 95 95 95 146 95 55 55 147 95 40 40 148 70 40 40 149 95 40 34 150 64 40 34 151 91 91 91 152 91 91 64 153 91 57 57 154 91 57 5 155 61 57 5 156 1 1 1 157 1 0 0 158 19 19 19 159 19 19 13 160 19 3 3 161 19 3 2 162 68 28 28 163 49 28 28 164 68 28 25 165 41 28 25 166 15 6 6 167 11 6 6 168 15 6 5 169 9 6 5 170 84 84 84 171 84 84 59 172 84 72 72 173 84 72 41 174 58 58 41 175 11 11 11 176 11 4 4 177 8 4 4 178 11 4 2 179 6 4 2 180 80 54 54 181 80 54 18 182 26 26 18 183 65 23 23 184 65 23 17 185 26 23 17 186 39 39 39 187 39 22 22 188 39 1 1 189 80 58 58 190 80 58 3 191 10 10 10 192 10 5 5 193 10 7 7 194 10 7 5 195 76 31 31 196 54 31 31 197 76 31 18 198 59 59 59 199 59 5 5 200 59 5 2 201 7 5 2 202 58 10 10 203 58 10 1 204 40 40 40 205 40 34 34 206 40 34 13 207 8 8 8 208 8 2 2 209 8 2 1 210 91 10 10 211 91 10 4 212 28 28 28 213 28 16 16 214 28 22 22 215 28 22 16 216 41 41 41 217 41 41 29 218 41 14 14 219 25 14 14 220 41 14 11 221 17 14 11 222 79 28 28 223 79 28 5 224 32 28 5 225 9 7 7 226 9 7 2 227 15 3 3 228 15 3 1 229 50 21 21 230 37 21 21 231 50 21 15 232 31 21 15 233 8 1 1 234 75 34 34 235 75 34 31 236 56 34 31 237 65 1 1 238 86 86 86 239 86 86 61 240 86 46 46 241 86 46 42 242 98 98 98 243 98 57 57 244 98 92 92 245 98 92 84 246 12 12 12 247 12 12 8 248 12 7 7 249 12 7 5 250 11 7 5 251 28 5 5 252 28 5 2 253 20 20 20 254 20 11 11 255 20 14 14 256 20 14 11 257 44 44 44 258 44 25 25 259 44 17 17 260 44 17 3 261 59 40 40 262 59 40 8 263 44 30 30 264 44 30 13 265 95 91 91 266 95 91 87 267 87 87 87 268 87 50 50 269 87 30 30 270 53 30 30 271 87 30 23 272 46 30 23 273 73 53 53 274 73 53 19 275 65 53 19 276 22 6 6 277 22 6 4 278 10 6 4 279 98 17 17 280 98 17 11 281 25 17 11 282 28 3 3 283 28 3 1 284 59 30 30 285 59 30 13 286 29 29 29 287 29 29 20 288 29 25 25 289 29 25 1 290 44 38 38 291 44 38 2 292 40 38 2 293 25 25 25 294 25 22 22 295 25 22 12 296 39 14 14 297 39 14 12 298 22 14 12 299 76 63 63 300 76 63 2 301 65 63 2 302 75 60 60 303 75 60 23 304 38 38 38 305 38 38 27 306 38 14 14 307 38 14 6 308 87 75 75 309 87 75 42 310 9 1 1 311 18 2 2 312 18 2 1 313 27 27 27 314 27 2 2 315 27 2 1 316 82 51 51 317 82 51 45 318 71 51 45 319 75 6 6 320 75 6 5 321 36 19 19 322 36 19 13 323 76 20 20 324 76 20 12 325 85 14 14 326 85 14 13 327 23 14 13 328 35 10 10 329 35 10 9 330 17 10 9 331 83 83 83 332 83 48 48 333 83 23 23 334 83 23 20 335 33 23 20 336 26 24 24 337 26 24 18 338 41 35 35 339 41 35 34 340 97 97 97 341 97 97 68 342 97 66 66 343 97 66 15 344 33 15 15 345 33 15 6 346 24 24 24 347 24 9 9 348 24 9 6 349 3 3 3 350 3 2 2 351 3 2 1 352 74 74 74 353 74 43 43 354 74 59 59 355 74 59 23 356 38 27 27 357 38 27 5 358 31 27 5 359 61 61 61 360 61 61 43 361 61 42 42 362 61 42 28 363 59 42 28 364 59 27 27 365 59 27 26 366 47 27 26 367 61 8 8 368 61 8 6 369 13 8 6 370 29 12 12 371 29 12 10 372 20 12 10 373 57 57 57 374 57 50 50 375 57 50 45 376 28 1 1 377 11 8 8 378 11 8 7 379 12 9 9 380 12 9 5 381 75 33 33 382 75 33 18 383 5 2 2 384 5 2 1 385 30 30 30 386 30 3 3 387 30 3 1 388 96 77 77 389 96 77 54 390 60 46 46 391 60 46 24 392 25 5 5 393 25 5 3 394 99 99 99 395 99 99 70 396 99 49 49 397 99 49 1 398 9 3 3 399 9 3 2 400 34 12 12 401 34 12 11 402 19 12 11 403 17 13 13 404 17 13 6 405 18 5 5 406 18 5 1 407 12 3 3 408 12 3 2 409 16 1 1 410 86 11 11 411 86 11 8 412 17 11 8 413 57 44 44 414 57 44 39 415 79 41 41 416 72 41 41 417 79 41 28 418 58 41 28 419 55 55 55 420 55 55 39 421 55 50 50 422 55 50 24 423 5 1 1 424 17 1 1 425 65 30 30 426 65 30 2 427 32 30 2 428 30 1 1 429 62 62 62 430 62 62 44 431 62 34 34 432 62 34 22 433 48 34 22 434 30 22 22 435 30 22 20 436 92 92 92 437 92 53 53 438 92 9 9 439 92 9 4 440 25 21 21 441 25 21 14 442 63 25 25 443 63 25 10 444 14 14 10 445 76 39 39 446 76 39 36 447 13 13 13 448 13 11 11 449 13 11 10 450 58 21 21 451 58 21 3 452 92 77 77 453 92 77 27 454 32 32 32 455 32 13 13 456 32 13 1 457 90 90 90 458 90 90 63 459 90 28 28 460 90 28 1 461 95 22 22 462 95 22 2 463 24 22 2 464 11 9 9 465 11 9 1 466 27 14 14 467 27 14 6 468 87 56 56 469 87 56 50 470 96 86 86 471 96 86 56 472 73 34 34 473 73 34 8 474 26 13 13 475 26 13 10 476 21 13 10 477 67 46 46 478 67 46 37 479 74 37 37 480 74 37 3 481 10 4 4 482 10 4 3 483 7 4 3 484 82 14 14 485 82 14 1 486 6 6 6 487 6 1 1 488 79 11 11 489 79 11 6 490 60 34 34 491 60 34 12 492 5 4 4 493 5 4 1 494 87 44 44 495 87 44 43 496 75 44 43 497 21 10 10 498 21 10 7 499 15 10 7 500 35 13 13 501 35 13 10 502 73 1 1 503 36 9 9 504 36 9 2 505 63 17 17 506 63 17 6 507 55 45 45 508 55 45 1 509 74 6 6 510 74 6 4 511 71 71 71 512 71 71 50 513 71 47 47 514 71 47 35 515 65 47 35 516 45 45 45 517 45 2 2 518 45 2 1 519 12 10 10 520 12 10 5 521 79 22 22 522 79 22 2 523 35 18 18 524 35 18 12 525 4 4 4 526 4 1 1 527 20 17 17 528 20 17 16 529 22 4 4 530 22 4 2 531 99 29 29 532 51 29 29 533 99 29 6 534 61 12 12 535 61 12 10 536 66 66 66 537 66 38 38 538 66 59 59 539 66 59 4 540 95 45 45 541 78 45 45 542 95 45 29 543 92 21 21 544 92 21 1 545 86 33 33 546 86 33 12 547 55 9 9 548 55 9 5 549 13 9 5 550 14 13 13 551 14 13 12 552 54 54 54 553 54 44 44 554 54 44 23 555 19 7 7 556 19 7 2 557 36 4 4 558 36 4 2 559 72 72 72 560 72 53 53 561 72 53 8 562 55 16 16 563 55 16 14 564 23 16 14 565 67 31 31 566 67 31 1 567 25 7 7 568 25 7 4 569 32 22 22 570 32 22 12 571 24 3 3 572 24 3 2 573 95 61 61 574 95 61 56 575 94 61 56 576 72 45 45 577 72 45 3 578 15 11 11 579 15 11 6 580 45 10 10 581 45 10 8 582 16 10 8 583 37 37 37 584 37 19 19 585 37 19 12 586 50 5 5 587 50 5 2 588 94 18 18 589 94 18 17 590 31 18 17 591 54 14 14 592 54 14 13 593 42 42 42 594 42 24 24 595 42 21 21 596 42 21 19 597 35 21 19 598 45 36 36 599 45 36 25 600 81 81 81 601 81 81 57 602 81 30 30 603 81 30 13 604 15 5 5 605 15 5 4 606 9 5 4 607 32 23 23 608 32 23 19 609 31 23 19 610 46 20 20 611 46 20 1 612 99 55 55 613 99 55 19 614 67 55 19 615 8 6 6 616 8 6 5 617 87 26 26 618 87 26 11 619 22 18 18 620 22 18 4 621 55 39 39 622 55 39 22 623 53 39 22 624 77 60 60 625 77 60 40 626 53 53 53 627 53 49 49 628 53 49 36 629 52 49 36 630 39 5 5 631 39 5 1 632 67 42 42 633 67 42 39 634 65 42 39 635 7 2 2 636 7 2 1 637 95 6 6 638 95 6 2 639 13 1 1 640 98 58 58 641 98 58 18 642 74 62 62 643 74 62 57 644 23 23 23 645 23 23 16 646 23 1 1 647 19 10 10 648 19 10 5 649 14 10 5 650 16 6 6 651 16 6 1 652 44 21 21 653 44 21 8 654 59 39 39 655 59 39 2 656 16 15 15 657 16 15 10 658 53 29 29 659 53 29 24 660 46 29 24 661 30 29 29 662 30 29 2 663 30 16 16 664 30 16 4 665 30 5 5 666 30 5 4 667 34 4 4 668 34 4 2 669 49 49 49 670 49 32 32 671 49 32 6 672 79 57 57 673 79 57 54 674 96 15 15 675 96 15 4 676 51 51 51 677 51 3 3 678 51 3 2 679 41 25 25 680 41 25 19 681 38 25 19 682 78 78 78 683 78 51 51 684 78 51 32 685 12 11 11 686 12 11 7 687 94 13 13 688 94 13 10 689 87 78 78 690 87 78 41 691 68 34 34 692 68 34 19 693 46 34 19 694 93 93 93 695 93 54 54 696 93 72 72 697 93 72 28 698 89 72 28 699 71 25 25 700 71 25 1 701 48 20 20 702 48 20 6 703 59 43 43 704 59 43 34 705 39 18 18 706 39 18 16 707 26 18 16 708 69 69 69 709 69 69 49 710 69 54 54 711 69 54 5 712 58 54 5 713 15 14 14 714 15 14 10 715 32 24 24 716 32 24 17 717 50 10 10 718 50 10 6 719 30 28 28 720 30 28 3 721 21 17 17 722 21 17 13 723 18 14 14 724 18 14 13 725 15 2 2 726 15 2 1 727 91 90 90 728 91 90 16 729 4 3 3 730 4 3 2 731 45 37 37 732 45 37 5 733 41 37 5 734 74 20 20 735 74 20 18 736 31 20 18 737 43 43 43 738 43 43 30 739 43 18 18 740 43 18 7 741 23 18 7 742 77 12 12 743 77 12 5 744 16 12 5 745 47 47 47 746 47 47 33 747 47 23 23 748 47 23 6 749 97 18 18 750 97 18 12 751 74 57 57 752 74 57 12 753 7 1 1 754 39 25 25 755 39 25 16 756 7 6 6 757 7 6 4 758 44 16 16 759 44 16 1 760 12 2 2 761 12 2 1 762 39 35 35 763 39 35 1 764 27 19 19 765 27 19 18 766 99 39 39 767 99 39 25 768 66 34 34 769 66 34 3 770 82 20 20 771 82 20 4 772 41 36 36 773 41 36 11 774 89 89 89 775 89 51 51 776 89 41 41 777 89 41 11 778 48 41 11 779 6 2 2 780 6 2 1 781 63 50 50 782 63 50 43 783 17 4 4 784 17 4 2 785 50 26 26 786 50 26 17 787 37 26 17 788 68 15 15 789 68 15 13 790 22 15 13 791 46 2 2 792 46 2 1 793 74 63 63 794 74 63 26 795 14 12 12 796 14 12 5 797 79 50 50 798 79 50 42 799 6 5 5 800 6 5 4 801 44 24 24 802 44 24 10 803 22 5 5 804 22 5 4 805 93 83 83 806 93 83 59 807 87 51 51 808 87 51 29 809 51 19 19 810 51 19 3 811 72 39 39 812 72 39 29 813 58 39 29 814 29 2 2 815 29 2 1 816 8 5 5 817 8 5 4 818 45 17 17 819 45 17 7 820 22 17 7 821 68 57 57 822 68 57 28 823 10 2 2 824 10 2 1 825 20 2 2 826 20 2 1 827 34 32 32 828 34 32 18 829 89 48 48 830 89 48 5 831 52 48 5 832 81 3 3 833 81 3 1 834 85 30 30 835 85 30 11 836 37 30 11 837 18 8 8 838 18 8 1 839 91 61 61 840 91 61 9 841 67 61 9 842 45 8 8 843 45 8 5 844 12 8 5 845 28 4 4 846 28 4 1 847 53 50 50 848 53 50 43 849 33 29 29 850 33 29 2 851 31 29 2 852 36 23 23 853 36 23 21 854 77 19 19 855 77 19 17 856 29 19 17 857 52 7 7 858 52 7 3 859 90 40 40 860 90 40 35 861 61 40 35 862 91 62 62 863 91 62 24 864 77 62 24 865 56 56 56 866 56 32 32 867 56 6 6 868 56 6 1 869 96 30 30 870 96 30 25 871 38 30 25 872 66 45 45 873 66 45 21 874 31 31 21 875 58 25 25 876 58 25 4 877 51 41 41 878 51 41 25 879 97 82 82 880 97 82 10 881 42 23 23 882 42 23 7 883 28 23 7 884 48 1 1 885 63 58 58 886 63 58 11 887 81 59 59 888 81 59 57 889 11 3 3 890 11 3 2 891 85 24 24 892 85 24 11 893 31 24 11 894 98 36 36 895 98 36 28 896 55 36 28 897 75 16 16 898 75 16 15 899 26 16 15 900 11 10 10 901 11 10 9 902 14 11 11 903 14 11 2 904 58 24 24 905 58 24 15 906 50 44 44 907 50 44 15 908 74 15 15 909 74 15 14 910 26 15 14 911 71 40 40 912 71 40 34 913 7 3 3 914 7 3 1 915 96 42 42 916 96 42 28 917 74 60 60 918 74 60 27 919 47 5 5 920 47 5 2 921 33 31 31 922 33 31 10 923 30 8 8 924 30 8 2 925 10 8 2 926 100 100 100 927 100 58 58 928 100 83 83 929 100 83 48 930 51 22 22 931 51 22 14 932 31 22 14 933 68 23 23 934 68 23 15 935 25 15 15 936 25 15 13 937 42 13 13 938 42 13 2 939 80 74 74 940 80 74 47 941 51 5 5 942 51 5 1 943 49 47 47 944 49 47 31 945 12 4 4 946 12 4 1 947 17 15 15 948 17 15 9 949 56 17 17 950 56 17 15 951 28 17 15 952 52 26 26 953 52 26 23 954 38 26 23 955 28 15 15 956 28 15 6 957 62 4 4 958 62 4 2 959 84 13 13 960 84 13 7 961 18 13 7 962 26 8 8 963 26 8 7 964 14 8 7 965 89 69 69 966 89 69 24 967 84 69 24 968 18 7 7 969 18 7 5 970 10 3 3 971 10 3 1 972 61 44 44 973 61 44 33 974 72 35 35 975 72 35 24 976 50 35 24 977 50 11 11 978 50 11 9 979 71 48 48 980 71 48 27 981 29 5 5 982 29 5 1 983 96 47 47 984 96 47 26 985 63 47 26 986 24 4 4 987 24 4 1 988 31 15 15 989 31 15 12 990 24 15 12 991 18 17 17 992 18 17 14 993 96 78 78 994 96 78 42 995 68 12 12 996 68 12 9 997 18 12 9 998 31 19 19 999 31 19 12 1000 31 2 2