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