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