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