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