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