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