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