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