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