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