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