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