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