0 1 1 0 2 1 3 0 4 1 5 0 6 1 7 0 8 1 9 0 10 2 11 1 12 3 13 1 14 3 15 1 16 3 17 1 18 3 19 1 20 4 21 2 22 6 23 3 24 7 25 3 26 7 27 3 28 7 29 3 30 8 31 4 32 10 33 6 34 12 35 7 36 13 37 7 38 13 39 7 40 14 41 8 42 16 43 10 44 19 45 12 46 21 47 13 48 22 49 13 50 23 51 14 52 25 53 16 54 28 55 19 56 31 57 21 58 33 59 22 60 35 61 23 62 37 63 25 64 40 65 28 66 44 67 31 68 47 69 33 70 50 71 35 72 53 73 37 74 56 75 40 76 60 77 44 78 64 79 47 80 68 81 50 82 72 83 53 84 76 85 56 86 80 87 60 88 85 89 64 90 90 91 68 92 95 93 72 94 100 95 76 96 105 97 80 98 110 99 85 100 116 101 90 102 122 103 95 104 128 105 100 106 134 107 105 108 140 109 110 110 147 111 116 112 154 113 122 114 161 115 128 116 168 117 134 118 175 119 140 120 183 121 147 122 191 123 154 124 199 125 161 126 207 127 168 128 215 129 175 130 224 131 183 132 234 133 191 134 243 135 199 136 252 137 207 138 261 139 215 140 271 141 224 142 282 143 234 144 293 145 243 146 303 147 252 148 313 149 261 150 324 151 271 152 336 153 282 154 349 155 293 156 361 157 303 158 372 159 313 160 384 161 324 162 397 163 336 164 411 165 349 166 425 167 361 168 438 169 372 170 451 171 384 172 465 173 397 174 480 175 411 176 496 177 425 178 511 179 438 180 526 181 451 182 541 183 465 184 557 185 480 186 574 187 496 188 591 189 511 190 608 191 526 192 625 193 541 194 642 195 557 196 660 197 574 198 679 199 591 200 698 201 608 202 717 203 625 204 736 205 642 206 755 207 660 208 775 209 679 210 796 211 698 212 817 213 717 214 838 215 736 216 859 217 755 218 880 219 775 220 903 221 796 222 926 223 817 224 949 225 838 226 972 227 859 228 995 229 880 230 1019 231 903 232 1044 233 926 234 1069 235 949 236 1094 237 972 238 1119 239 995 240 1145 241 1019 242 1172 243 1044 244 1199 245 1069 246 1226 247 1094 248 1253 249 1119 250 1281 251 1145 252 1310 253 1172 254 1339 255 1199 256 1368 257 1226 258 1397 259 1253 260 1427 261 1281 262 1458 263 1310 264 1490 265 1339 266 1521 267 1368 268 1552 269 1397 270 1584 271 1427 272 1617 273 1458 274 1651 275 1490 276 1685 277 1521 278 1718 279 1552 280 1752 281 1584 282 1787 283 1617 284 1823 285 1651 286 1860 287 1685 288 1896 289 1718 290 1932 291 1752 292 1969 293 1787 294 2007 295 1823 296 2046 297 1860 298 2085 299 1896 300 2124 301 1932 302 2163 303 1969 304 2203 305 2007 306 2244 307 2046 308 2286 309 2085 310 2328 311 2124 312 2370 313 2163 314 2412 315 2203 316 2455 317 2244 318 2499 319 2286 320 2544 321 2328 322 2589 323 2370 324 2634 325 2412 326 2679 327 2455 328 2725 329 2499 330 2773 331 2544 332 2821 333 2589 334 2869 335 2634 336 2917 337 2679 338 2965 339 2725 340 3015 341 2773 342 3066 343 2821 344 3117 345 2869 346 3168 347 2917 348 3219 349 2965 350 3271 351 3015 352 3325 353 3066 354 3379 355 3117 356 3433 357 3168 358 3487 359 3219 360 3542 361 3271 362 3598 363 3325 364 3655 365 3379 366 3712 367 3433 368 3769 369 3487 370 3827 371 3542 372 3886 373 3598 374 3946 375 3655 376 4006 377 3712 378 4066 379 3769 380 4127 381 3827 382 4189 383 3886 384 4252 385 3946 386 4315 387 4006 388 4378 389 4066 390 4442 391 4127 392 4507 393 4189 394 4573 395 4252 396 4640 397 4315 398 4706 399 4378 400 4773 401 4442 402 4841 403 4507 404 4910 405 4573 406 4980 407 4640 408 5050 409 4706 410 5120 411 4773 412 5191 413 4841 414 5263 415 4910 416 5336 417 4980 418 5410 419 5050 420 5484 421 5120 422 5558 423 5191 424 5633 425 5263 426 5709 427 5336 428 5786 429 5410 430 5864 431 5484 432 5942 433 5558 434 6020 435 5633 436 6099 437 5709 438 6179 439 5786 440 6261 441 5864 442 6343 443 5942 444 6425 445 6020 446 6507 447 6099 448 6590 449 6179 450 6675 451 6261 452 6761 453 6343 454 6847 455 6425 456 6933 457 6507 458 7019 459 6590 460 7107 461 6675 462 7197 463 6761 464 7287 465 6847 466 7377 467 6933 468 7467 469 7019 470 7558 471 7107 472 7651 473 7197 474 7745 475 7287 476 7839 477 7377 478 7933 479 7467 480 8028 481 7558 482 8124 483 7651 484 8222 485 7745 486 8320 487 7839 488 8418 489 7933 490 8517 491 8028 492 8617 493 8124 494 8718 495 8222 496 8820 497 8320 498 8922 499 8418 500 9025 501 8517 502 9129 503 8617 504 9234 505 8718 506 9340 507 8820 508 9446 509 8922 510 9553 511 9025 512 9661 513 9129 514 9770 515 9234 516 9880 517 9340 518 9990 519 9446 520 10101 521 9553 522 10213 523 9661 524 10326 525 9770 526 10440 527 9880 528 10555 529 9990 530 10670 531 10101 532 10786 533 10213 534 10903 535 10326 536 11021 537 10440 538 11140 539 10555 540 11260 541 10670 542 11380 543 10786 544 11501 545 10903 546 11623 547 11021 548 11746 549 11140 550 11871 551 11260 552 11996 553 11380 554 12121 555 11501 556 12247 557 11623 558 12374 559 11746 560 12503 561 11871 562 12633 563 11996 564 12763 565 12121 566 12893 567 12247 568 13024 569 12374 570 13157 571 12503 572 13292 573 12633 574 13427 575 12763 576 13562 577 12893 578 13697 579 13024 580 13834 581 13157 582 13973 583 13292 584 14113 585 13427 586 14253 587 13562 588 14393 589 13697 590 14534 591 13834 592 14677 593 13973 594 14822 595 14113 596 14967 597 14253 598 15112 599 14393 600 15258 601 14534 602 15405 603 14677 604 15554 605 14822 606 15704 607 14967 608 15854 609 15112 610 16005 611 15258 612 16157 613 15405 614 16310 615 15554 616 16465 617 15704 618 16620 619 15854 620 16776 621 16005 622 16933 623 16157 624 17091 625 16310 626 17250 627 16465 628 17410 629 16620 630 17571 631 16776 632 17733 633 16933 634 17896 635 17091 636 18060 637 17250 638 18225 639 17410 640 18391 641 17571 642 18558 643 17733 644 18726 645 17896 646 18895 647 18060 648 19065 649 18225 650 19236 651 18391 652 19408 653 18558 654 19581 655 18726 656 19755 657 18895 658 19930 659 19065 660 20107 661 19236 662 20284 663 19408 664 20462 665 19581 666 20641 667 19755 668 20821 669 19930 670 21003 671 20107 672 21186 673 20284 674 21369 675 20462 676 21553 677 20641 678 21738 679 20821 680 21925 681 21003 682 22114 683 21186 684 22303 685 21369 686 22492 687 21553 688 22682 689 21738 690 22874 691 21925 692 23068 693 22114 694 23263 695 22303 696 23458 697 22492 698 23653 699 22682 700 23850 701 22874 702 24049 703 23068 704 24250 705 23263 706 24451 707 23458 708 24652 709 23653 710 24854 711 23850 712 25058 713 24049 714 25264 715 24250 716 25471 717 24451 718 25678 719 24652 720 25886 721 24854 722 26095 723 25058 724 26306 725 25264 726 26519 727 25471 728 26732 729 25678 730 26946 731 25886 732 27161 733 26095 734 27377 735 26306 736 27595 737 26519 738 27814 739 26732 740 28034 741 26946 742 28255 743 27161 744 28477 745 27377 746 28700 747 27595 748 28925 749 27814 750 29151 751 28034 752 29378 753 28255 754 29606 755 28477 756 29835 757 28700 758 30065 759 28925 760 30297 761 29151 762 30530 763 29378 764 30764 765 29606 766 30999 767 29835 768 31235 769 30065 770 31473 771 30297 772 31712 773 30530 774 31952 775 30764 776 32193 777 30999 778 32435 779 31235 780 32679 781 31473 782 32924 783 31712 784 33170 785 31952 786 33417 787 32193 788 33665 789 32435 790 33915 791 32679 792 34167 793 32924 794 34419 795 33170 796 34672 797 33417 798 34926 799 33665 800 35182 801 33915 802 35440 803 34167 804 35699 805 34419 806 35958 807 34672 808 36218 809 34926 810 36480 811 35182 812 36744 813 35440 814 37010 815 35699 816 37276 817 35958 818 37542 819 36218 820 37810 821 36480 822 38080 823 36744 824 38352 825 37010 826 38625 827 37276 828 38898 829 37542 830 39172 831 37810 832 39448 833 38080 834 39726 835 38352 836 40006 837 38625 838 40286 839 38898 840 40567 841 39172 842 40849 843 39448 844 41133 845 39726 846 41419 847 40006 848 41706 849 40286 850 41994 851 40567 852 42283 853 40849 854 42573 855 41133 856 42865 857 41419 858 43159 859 41706 860 43454 861 41994 862 43750 863 42283 864 44047 865 42573 866 44345 867 42865 868 44645 869 43159 870 44947 871 43454 872 45250 873 43750 874 45554 875 44047 876 45859 877 44345 878 46165 879 44645 880 46474 881 44947 882 46784 883 45250 884 47095 885 45554 886 47407 887 45859 888 47720 889 46165 890 48035 891 46474 892 48352 893 46784 894 48670 895 47095 896 48989 897 47407 898 49309 899 47720 900 49631 901 48035 902 49955 903 48352 904 50280 905 48670 906 50606 907 48989 908 50933 909 49309 910 51262 911 49631 912 51593 913 49955 914 51925 915 50280 916 52258 917 50606 918 52592 919 50933 920 52928 921 51262 922 53266 923 51593 924 53606 925 51925 926 53946 927 52258 928 54287 929 52592 930 54630 931 52928 932 54975 933 53266 934 55322 935 53606 936 55670 937 53946 938 56018 939 54287 940 56368 941 54630 942 56720 943 54975 944 57074 945 55322 946 57430 947 55670 948 57786 949 56018 950 58143 951 56368 952 58502 953 56720 954 58863 955 57074 956 59226 957 57430 958 59590 959 57786 960 59955 961 58143 962 60321 963 58502 964 60689 965 58863 966 61059 967 59226 968 61431 969 59590 970 61804 971 59955 972 62178 973 60321 974 62553 975 60689 976 62930 977 61059 978 63309 979 61431 980 63690 981 61804 982 64072 983 62178 984 64455 985 62553 986 64839 987 62930 988 65225 989 63309 990 65614 991 63690 992 66004 993 64072 994 66395 995 64455 996 66787 997 64839 998 67180 999 65225 1000 67576