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