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