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