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