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