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