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