0 1 1 3 2 5 3 10 4 18 5 29 6 45 7 56 8 65 9 86 10 110 11 130 12 151 13 177 14 210 15 246 16 292 17 344 18 384 19 430 20 491 21 541 22 581 23 630 24 690 25 750 26 805 27 882 28 985 29 1069 30 1138 31 1225 32 1313 33 1378 34 1441 35 1542 36 1654 37 1725 38 1794 39 1895 40 1992 41 2092 42 2226 43 2377 44 2503 45 2596 46 2708 47 2842 48 2951 49 3063 50 3212 51 3362 52 3484 53 3594 54 3715 55 3835 56 3959 57 4142 58 4353 59 4511 60 4646 61 4805 62 4970 63 5132 64 5312 65 5508 66 5672 67 5803 68 5962 69 6135 70 6277 71 6438 72 6666 73 6916 74 7125 75 7310 76 7517 77 7713 78 7891 79 8120 80 8379 81 8576 82 8729 83 8926 84 9156 85 9355 86 9554 87 9809 88 10072 89 10299 90 10539 91 10809 92 11053 93 11268 94 11526 95 11826 96 12085 97 12295 98 12522 99 12772 100 13005 101 13249 102 13539 103 13823 104 14077 105 14366 106 14697 107 15001 108 15272 109 15559 110 15864 111 16149 112 16427 113 16722 114 16994 115 17245 116 17538 117 17873 118 18197 119 18498 120 18820 121 19174 122 19508 123 19829 124 20177 125 20511 126 20817 127 21150 128 21511 129 21840 130 22123 131 22434 132 22800 133 23156 134 23501 135 23873 136 24244 137 24601 138 24975 139 25379 140 25781 141 26140 142 26492 143 26874 144 27240 145 27578 146 27932 147 28318 148 28719 149 29117 150 29523 151 29935 152 30327 153 30730 154 31171 155 31614 156 32037 157 32437 158 32824 159 33219 160 33623 161 34040 162 34474 163 34911 164 35344 165 35771 166 36196 167 36633 168 37084 169 37554 170 38040 171 38517 172 38973 173 39407 174 39831 175 40272 176 40737 177 41211 178 41684 179 42150 180 42606 181 43066 182 43547 183 44049 184 44564 185 45087 186 45599 187 46085 188 46560 189 47037 190 47518 191 48012 192 48532 193 49060 194 49562 195 50056 196 50571 197 51093 198 51613 199 52148 200 52706 201 53260 202 53781 203 54302 204 54849 205 55381 206 55904 207 56463 208 57037 209 57576 210 58093 211 58650 212 59230 213 59775 214 60328 215 60929 216 61524 217 62094 218 62674 219 63265 220 63833 221 64378 222 64964 223 65588 224 66175 225 66743 226 67344 227 67956 228 68550 229 69146 230 69771 231 70393 232 70989 233 71614 234 72259 235 72857 236 73446 237 74083 238 74742 239 75384 240 76016 241 76658 242 77282 243 77887 244 78536 245 79217 246 79863 247 80492 248 81156 249 81838 250 82489 251 83132 252 83821 253 84513 254 85167 255 85842 256 86545 257 87204 258 87835 259 88526 260 89266 261 89965 262 90626 263 91315 264 92012 265 92685 266 93387 267 94141 268 94877 269 95562 270 96264 271 97010 272 97735 273 98427 274 99150 275 99906 276 100633 277 101337 278 102063 279 102785 280 103489 281 104242 282 105053 283 105843 284 106582 285 107315 286 108070 287 108825 288 109587 289 110374 290 111146 291 111889 292 112644 293 113419 294 114185 295 114938 296 115720 297 116548 298 117366 299 118157 300 118955 301 119743 302 120521 303 121334 304 122181 305 123008 306 123785 307 124562 308 125372 309 126172 310 126965 311 127791 312 128634 313 129477 314 130325 315 131183 316 132041 317 132868 318 133694 319 134560 320 135426 321 136262 322 137086 323 137918 324 138759 325 139599 326 140457 327 141343 328 142225 329 143106 330 144003 331 144898 332 145783 333 146655 334 147528 335 148427 336 149333 337 150222 338 151098 339 151969 340 152842 341 153723 342 154626 343 155557 344 156488 345 157410 346 158342 347 159279 348 160209 349 161133 350 162065 351 163010 352 163943 353 164853 354 165758 355 166666 356 167580 357 168522 358 169499 359 170477 360 171438 361 172405 362 173379 363 174343 364 175312 365 176299 366 177280 367 178236 368 179190 369 180152 370 181100 371 182056 372 183055 373 184069 374 185059 375 186038 376 187042 377 188062 378 189065 379 190082 380 191135 381 192161 382 193144 383 194139 384 195151 385 196140 386 197121 387 198158 388 199224 389 200237 390 201236 391 202287 392 203352 393 204406 394 205478 395 206569 396 207629 397 208636 398 209662 399 210728 400 211767 401 212795 402 213870 403 214966 404 216030 405 217076 406 218155 407 219249 408 220325 409 221436 410 222579 411 223671 412 224726 413 225807 414 226910 415 228000 416 229086 417 230200 418 231310 419 232389 420 233492 421 234629 422 235743 423 236846 424 237994 425 239176 426 240325 427 241438 428 242573 429 243705 430 244801 431 245928 432 247105 433 248254 434 249363 435 250510 436 251702 437 252863 438 253996 439 255171 440 256372 441 257547 442 258721 443 259917 444 261087 445 262212 446 263368 447 264592 448 265811 449 266983 450 268158 451 269360 452 270547 453 271725 454 272941 455 274171 456 275379 457 276600 458 277847 459 279069 460 280250 461 281441 462 282678 463 283929 464 285167 465 286400 466 287616 467 288821 468 290054 469 291323 470 292599 471 293852 472 295096 473 296358 474 297610 475 298847 476 300107 477 301379 478 302649 479 303932 480 305223 481 306496 482 307739 483 308998 484 310304 485 311610 486 312897 487 314183 488 315462 489 316743 490 318041 491 319363 492 320701 493 322014 494 323308 495 324620 496 325936 497 327242 498 328550 499 329874 500 331215 501 332547 502 333867 503 335193 504 336517 505 337850 506 339207 507 340576 508 341945 509 343287 510 344610 511 345963 512 347341 513 348710 514 350072 515 351441 516 352808 517 354155 518 355502 519 356877 520 358256 521 359632 522 361036 523 362459 524 363863 525 365241 526 366629 527 368042 528 369449 529 370843 530 372248 531 373654 532 375038 533 376426 534 377843 535 379263 536 380676 537 382117 538 383581 539 385023 540 386448 541 387887 542 389330 543 390758 544 392198 545 393664 546 395114 547 396542 548 397983 549 399431 550 400861 551 402294 552 403776 553 405290 554 406773 555 408242 556 409741 557 411227 558 412684 559 414169 560 415689 561 417182 562 418631 563 420104 564 421602 565 423057 566 424514 567 426047 568 427608 569 429138 570 430656 571 432191 572 433713 573 435198 574 436718 575 438294 576 439833 577 441323 578 442832 579 444362 580 445872 581 447380 582 448943 583 450529 584 452075 585 453630 586 455219 587 456777 588 458314 589 459891 590 461500 591 463084 592 464630 593 466180 594 467728 595 469257 596 470824 597 472441 598 474041 599 475612 600 477206 601 478838 602 480457 603 482054 604 483681 605 485313 606 486901 607 488490 608 490107 609 491698 610 493259 611 494866 612 496532 613 498177 614 499780 615 501405 616 503060 617 504707 618 506361 619 508043 620 509711 621 511330 622 512952 623 514620 624 516283 625 517903 626 519532 627 521206 628 522879 629 524531 630 526201 631 527887 632 529563 633 531258 634 532989 635 534711 636 536390 637 538051 638 539734 639 541425 640 543105 641 544790 642 546480 643 548175 644 549886 645 551611 646 553339 647 555054 648 556770 649 558518 650 560274 651 562013 652 563745 653 565459 654 567163 655 568886 656 570631 657 572382 658 574119 659 575858 660 577616 661 579368 662 581115 663 582875 664 584644 665 586433 666 588235 667 590025 668 591799 669 593544 670 595280 671 597050 672 598848 673 600650 674 602434 675 604204 676 605989 677 607783 678 609581 679 611401 680 613235 681 615068 682 616887 683 618690 684 620493 685 622281 686 624066 687 625903 688 627773 689 629612 690 631418 691 633233 692 635066 693 636895 694 638738 695 640619 696 642492 697 644328 698 646168 699 648029 700 649883 701 651725 702 653593 703 655492 704 657367 705 659207 706 661062 707 662938 708 664806 709 666686 710 668603 711 670515 712 672390 713 674271 714 676177 715 678071 716 679956 717 681869 718 683796 719 685694 720 687584 721 689504 722 691426 723 693334 724 695261 725 697207 726 699131 727 701030 728 702956 729 704914 730 706845 731 708768 732 710739 733 712711 734 714642 735 716581 736 718557 737 720518 738 722441 739 724398 740 726396 741 728349 742 730276 743 732255 744 734256 745 736228 746 738198 747 740207 748 742219 749 744182 750 746158 751 748186 752 750187 753 752149 754 754144 755 756178 756 758190 757 760170 758 762175 759 764195 760 766181 761 768190 762 770257 763 772309 764 774326 765 776355 766 778410 767 780454 768 782474 769 784514 770 786570 771 788603 772 790638 773 792691 774 794723 775 796736 776 798788 777 800902 778 803017 779 805090 780 807163 781 809239 782 811289 783 813356 784 815467 785 817568 786 819629 787 821698 788 823798 789 825877 790 827926 791 830013 792 832152 793 834291 794 836415 795 838541 796 840655 797 842740 798 844844 799 847008 800 849177 801 851291 802 853380 803 855490 804 857601 805 859703 806 861837 807 864003 808 866165 809 868328 810 870505 811 872677 812 874826 813 876971 814 879146 815 881337 816 883509 817 885656 818 887786 819 889923 820 892086 821 894271 822 896473 823 898672 824 900858 825 903056 826 905266 827 907477 828 909689 829 911889 830 914091 831 916308 832 918519 833 920714 834 922895 835 925082 836 927294 837 929518 838 931751 839 933985 840 936208 841 938453 842 940723 843 942987 844 945245 845 947490 846 949724 847 951964 848 954208 849 956450 850 958676 851 960898 852 963157 853 965441 854 967717 855 969993 856 972279 857 974574 858 976865 859 979154 860 981461 861 983751 862 986008 863 988287 864 990591 865 992870 866 995130 867 997423 868 999750 869 1002059 870 1004354 871 1006681 872 1009014 873 1011324 874 1013654 875 1016023 876 1018381 877 1020691 878 1022995 879 1025326 880 1027643 881 1029941 882 1032278 883 1034650 884 1036994 885 1039320 886 1041681 887 1044055 888 1046408 889 1048783 890 1051199 891 1053593 892 1055940 893 1058287 894 1060648 895 1062992 896 1065344 897 1067748 898 1070162 899 1072540 900 1074911 901 1077303 902 1079693 903 1082074 904 1084496 905 1086960 906 1089385 907 1091768 908 1094175 909 1096585 910 1098966 911 1101369 912 1103825 913 1106272 914 1108663 915 1111066 916 1113514 917 1115937 918 1118348 919 1120819 920 1123320 921 1125784 922 1128216 923 1130665 924 1133119 925 1135534 926 1137970 927 1140472 928 1142957 929 1145389 930 1147834 931 1150322 932 1152806 933 1155266 934 1157757 935 1160275 936 1162755 937 1165230 938 1167741 939 1170237 940 1172702 941 1175185 942 1177712 943 1180242 944 1182736 945 1185230 946 1187742 947 1190243 948 1192752 949 1195289 950 1197821 951 1200332 952 1202854 953 1205414 954 1207969 955 1210484 956 1213009 957 1215559 958 1218099 959 1220644 960 1223211 961 1225764 962 1228287 963 1230828 964 1233414 965 1235997 966 1238548 967 1241107 968 1243688 969 1246261 970 1248825 971 1251405 972 1253997 973 1256576 974 1259160 975 1261776 976 1264391 977 1266965 978 1269528 979 1272128 980 1274747 981 1277353 982 1279955 983 1282557 984 1285151 985 1287756 986 1290391 987 1293045 988 1295690 989 1298311 990 1300932 991 1303567 992 1306201 993 1308826 994 1311450 995 1314097 996 1316760 997 1319407 998 1322043 999 1324676 1000 1327308