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