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