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