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