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