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