0 1 1 0 2 0 3 1 4 1 5 1 6 1 7 2 8 2 9 2 10 3 11 3 12 4 13 4 14 5 15 6 16 6 17 7 18 8 19 9 20 10 21 11 22 12 23 13 24 15 25 16 26 17 27 19 28 21 29 22 30 24 31 26 32 28 33 30 34 32 35 35 36 37 37 39 38 42 39 45 40 48 41 50 42 54 43 57 44 60 45 64 46 67 47 71 48 75 49 79 50 83 51 87 52 92 53 96 54 101 55 106 56 111 57 116 58 121 59 127 60 133 61 138 62 144 63 151 64 157 65 163 66 170 67 177 68 184 69 191 70 199 71 206 72 214 73 222 74 230 75 239 76 247 77 256 78 265 79 274 80 284 81 293 82 303 83 313 84 324 85 334 86 344 87 356 88 367 89 378 90 390 91 402 92 414 93 426 94 439 95 452 96 465 97 478 98 492 99 506 100 520 101 534 102 549 103 564 104 579 105 595 106 610 107 626 108 643 109 659 110 676 111 693 112 711 113 728 114 746 115 765 116 783 117 802 118 821 119 841 120 861 121 880 122 901 123 922 124 943 125 964 126 986 127 1008 128 1030 129 1053 130 1076 131 1099 132 1123 133 1147 134 1171 135 1196 136 1221 137 1246 138 1272 139 1298 140 1325 141 1351 142 1378 143 1406 144 1434 145 1462 146 1490 147 1520 148 1549 149 1578 150 1609 151 1639 152 1670 153 1701 154 1733 155 1765 156 1797 157 1830 158 1863 159 1897 160 1931 161 1965 162 2000 163 2035 164 2071 165 2107 166 2143 167 2180 168 2218 169 2255 170 2293 171 2332 172 2371 173 2410 174 2450 175 2491 176 2531 177 2572 178 2614 179 2656 180 2699 181 2741 182 2785 183 2829 184 2873 185 2918 186 2963 187 3009 188 3055 189 3102 190 3149 191 3196 192 3245 193 3293 194 3342 195 3392 196 3442 197 3492 198 3543 199 3595 200 3647 201 3699 202 3752 203 3806 204 3860 205 3914 206 3969 207 4025 208 4081 209 4137 210 4195 211 4252 212 4310 213 4369 214 4428 215 4488 216 4548 217 4609 218 4670 219 4732 220 4795 221 4857 222 4921 223 4985 224 5050 225 5115 226 5180 227 5247 228 5314 229 5381 230 5449 231 5518 232 5587 233 5656 234 5727 235 5798 236 5869 237 5941 238 6014 239 6087 240 6161 241 6235 242 6310 243 6386 244 6462 245 6539 246 6616 247 6694 248 6773 249 6852 250 6932 251 7012 252 7094 253 7175 254 7257 255 7341 256 7424 257 7508 258 7593 259 7679 260 7765 261 7851 262 7939 263 8027 264 8116 265 8205 266 8295 267 8386 268 8477 269 8569 270 8662 271 8755 272 8849 273 8944 274 9039 275 9135 276 9232 277 9329 278 9427 279 9526 280 9626 281 9725 282 9826 283 9928 284 10030 285 10133 286 10236 287 10341 288 10446 289 10551 290 10658 291 10765 292 10873 293 10981 294 11091 295 11201 296 11311 297 11423 298 11535 299 11648 300 11762 301 11876 302 11991 303 12107 304 12224 305 12341 306 12459 307 12578 308 12698 309 12818 310 12939 311 13061 312 13184 313 13307 314 13431 315 13557 316 13682 317 13808 318 13936 319 14064 320 14193 321 14322 322 14453 323 14584 324 14716 325 14849 326 14982 327 15117 328 15252 329 15388 330 15525 331 15662 332 15801 333 15940 334 16080 335 16221 336 16363 337 16505 338 16648 339 16793 340 16938 341 17083 342 17230 343 17378 344 17526 345 17675 346 17825 347 17976 348 18128 349 18280 350 18434 351 18588 352 18743 353 18899 354 19056 355 19214 356 19372 357 19532 358 19692 359 19853 360 20016 361 20178 362 20342 363 20507 364 20673 365 20839 366 21006 367 21175 368 21344 369 21514 370 21685 371 21857 372 22030 373 22203 374 22378 375 22554 376 22730 377 22907 378 23086 379 23265 380 23445 381 23626 382 23808 383 23991 384 24175 385 24360 386 24545 387 24732 388 24920 389 25108 390 25298 391 25488 392 25680 393 25872 394 26065 395 26260 396 26455 397 26651 398 26848 399 27047 400 27246 401 27445 402 27647 403 27849 404 28052 405 28256 406 28461 407 28667 408 28874 409 29082 410 29291 411 29501 412 29712 413 29924 414 30137 415 30351 416 30566 417 30782 418 30999 419 31217 420 31437 421 31656 422 31877 423 32100 424 32323 425 32547 426 32772 427 32999 428 33226 429 33454 430 33684 431 33914 432 34146 433 34378 434 34612 435 34847 436 35082 437 35319 438 35557 439 35796 440 36036 441 36277 442 36519 443 36762 444 37007 445 37252 446 37498 447 37746 448 37995 449 38244 450 38495 451 38747 452 39000 453 39254 454 39509 455 39766 456 40023 457 40281 458 40541 459 40802 460 41064 461 41326 462 41591 463 41856 464 42122 465 42390 466 42658 467 42928 468 43199 469 43471 470 43744 471 44018 472 44294 473 44570 474 44848 475 45127 476 45407 477 45688 478 45970 479 46254 480 46539 481 46824 482 47111 483 47400 484 47689 485 47979 486 48271 487 48564 488 48858 489 49153 490 49450 491 49747 492 50046 493 50346 494 50647 495 50950 496 51253 497 51558 498 51864 499 52171 500 52480 501 52789 502 53100 503 53412 504 53726 505 54040 506 54355 507 54673 508 54991 509 55310 510 55631 511 55953 512 56276 513 56600 514 56926 515 57253 516 57581 517 57910 518 58241 519 58573 520 58906 521 59240 522 59576 523 59913 524 60251 525 60591 526 60931 527 61273 528 61617 529 61961 530 62307 531 62654 532 63003 533 63352 534 63703 535 64056 536 64409 537 64764 538 65120 539 65478 540 65837 541 66196 542 66558 543 66921 544 67285 545 67650 546 68017 547 68385 548 68754 549 69125 550 69497 551 69870 552 70245 553 70621 554 70998 555 71377 556 71757 557 72138 558 72521 559 72905 560 73291 561 73677 562 74065 563 74455 564 74846 565 75238 566 75631 567 76027 568 76423 569 76820 570 77220 571 77620 572 78022 573 78425 574 78830 575 79236 576 79643 577 80052 578 80462 579 80874 580 81287 581 81701 582 82117 583 82534 584 82953 585 83373 586 83794 587 84217 588 84642 589 85067 590 85494 591 85923 592 86353 593 86784 594 87217 595 87652 596 88087 597 88524 598 88963 599 89403 600 89845 601 90287 602 90732 603 91178 604 91625 605 92074 606 92524 607 92976 608 93429 609 93884 610 94340 611 94797 612 95257 613 95717 614 96179 615 96643 616 97108 617 97574 618 98042 619 98512 620 98983 621 99455 622 99929 623 100405 624 100882 625 101360 626 101840 627 102322 628 102805 629 103289 630 103776 631 104263 632 104752 633 105243 634 105735 635 106229 636 106724 637 107221 638 107719 639 108219 640 108721 641 109223 642 109728 643 110234 644 110742 645 111251 646 111761 647 112274 648 112788 649 113303 650 113820 651 114339 652 114859 653 115380 654 115904 655 116429 656 116955 657 117483 658 118013 659 118544 660 119077 661 119611 662 120147 663 120685 664 121224 665 121765 666 122307 667 122851 668 123397 669 123944 670 124493 671 125043 672 125596 673 126149 674 126704 675 127262 676 127820 677 128380 678 128942 679 129506 680 130071 681 130637 682 131206 683 131776 684 132348 685 132921 686 133496 687 134073 688 134651 689 135231 690 135813 691 136396 692 136981 693 137568 694 138156 695 138746 696 139338 697 139931 698 140526 699 141123 700 141722 701 142321 702 142923 703 143527 704 144132 705 144739 706 145347 707 145958 708 146570 709 147183 710 147799 711 148416 712 149035 713 149655 714 150278 715 150902 716 151527 717 152155 718 152784 719 153415 720 154048 721 154682 722 155318 723 155956 724 156596 725 157237 726 157880 727 158525 728 159172 729 159820 730 160470 731 161122 732 161776 733 162431 734 163088 735 163748 736 164408 737 165070 738 165735 739 166401 740 167069 741 167738 742 168410 743 169083 744 169758 745 170435 746 171113 747 171794 748 172476 749 173160 750 173846 751 174533 752 175223 753 175914 754 176607 755 177302 756 177999 757 178697 758 179397 759 180100 760 180804 761 181509 762 182217 763 182927 764 183638 765 184351 766 185066 767 185783 768 186502 769 187222 770 187945 771 188669 772 189395 773 190123 774 190853 775 191585 776 192318 777 193054 778 193791 779 194530 780 195272 781 196014 782 196759 783 197506 784 198255 785 199005 786 199757 787 200512 788 201268 789 202026 790 202786 791 203548 792 204312 793 205077 794 205845 795 206615 796 207386 797 208159 798 208935 799 209712 800 210491 801 211272 802 212055 803 212840 804 213627 805 214416 806 215206 807 215999 808 216794 809 217590 810 218389 811 219189 812 219992 813 220796 814 221602 815 222411 816 223221 817 224033 818 224847 819 225664 820 226482 821 227301 822 228124 823 228948 824 229774 825 230602 826 231432 827 232264 828 233098 829 233934 830 234772 831 235612 832 236454 833 237298 834 238144 835 238992 836 239842 837 240694 838 241548 839 242404 840 243263 841 244122 842 244984 843 245849 844 246715 845 247583 846 248453 847 249326 848 250200 849 251076 850 251955 851 252835 852 253718 853 254602 854 255489 855 256378 856 257268 857 258161 858 259056 859 259953 860 260852 861 261753 862 262656 863 263561 864 264469 865 265378 866 266289 867 267203 868 268119 869 269036 870 269956 871 270878 872 271802 873 272728 874 273656 875 274587 876 275519 877 276453 878 277390 879 278329 880 279270 881 280212 882 281158 883 282105 884 283054 885 284006 886 284959 887 285915 888 286873 889 287833 890 288795 891 289759 892 290726 893 291694 894 292665 895 293638 896 294613 897 295590 898 296569 899 297551 900 298535 901 299520 902 300508 903 301499 904 302491 905 303485 906 304482 907 305481 908 306482 909 307485 910 308491 911 309498 912 310508 913 311520 914 312534 915 313551 916 314569 917 315590 918 316613 919 317638 920 318666 921 319695 922 320727 923 321761 924 322798 925 323836 926 324876 927 325920 928 326965 929 328012 930 329062 931 330114 932 331168 933 332224 934 333283 935 334344 936 335407 937 336472 938 337540 939 338610 940 339682 941 340756 942 341833 943 342912 944 343993 945 345077 946 346162 947 347250 948 348341 949 349433 950 350528 951 351625 952 352725 953 353826 954 354930 955 356037 956 357145 957 358256 958 359369 959 360485 960 361603 961 362722 962 363845 963 364970 964 366097 965 367226 966 368358 967 369492 968 370628 969 371767 970 372908 971 374051 972 375197 973 376345 974 377495 975 378648 976 379803 977 380960 978 382120 979 383282 980 384447 981 385613 982 386782 983 387954 984 389128 985 390304 986 391482 987 392664 988 393847 989 395032 990 396221 991 397411 992 398604 993 399799 994 400997 995 402197 996 403399 997 404604 998 405811 999 407021 1000 408233