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