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