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