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