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