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