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