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