0 1 1 1 2 2 3 2 4 7 5 10 6 15 7 15 8 28 9 39 10 52 11 59 12 76 13 87 14 100 15 100 16 129 17 156 18 185 19 208 20 241 21 268 22 297 23 312 24 353 25 388 26 425 27 448 28 489 29 516 30 545 31 545 32 606 33 665 34 726 35 781 36 846 37 905 38 966 39 1013 40 1086 41 1153 42 1222 43 1277 44 1350 45 1409 46 1470 47 1501 48 1590 49 1673 50 1758 51 1829 52 1918 53 1993 54 2070 55 2117 56 2214 57 2297 58 2382 59 2437 60 2526 61 2585 62 2646 63 2646 64 2771 65 2894 66 3019 67 3138 68 3267 69 3390 70 3515 71 3626 72 3763 73 3894 74 4027 75 4146 76 4283 77 4406 78 4531 79 4626 80 4779 81 4926 82 5075 83 5210 84 5363 85 5502 86 5643 87 5754 88 5915 89 6062 90 6211 91 6330 92 6483 93 6606 94 6731 95 6794 96 6979 97 7158 98 7339 99 7506 100 7691 101 7862 102 8035 103 8178 104 8371 105 8550 106 8731 107 8882 108 9067 109 9222 110 9379 111 9474 112 9683 113 9878 114 10075 115 10242 116 10443 117 10614 118 10787 119 10898 120 11107 121 11286 122 11467 123 11586 124 11771 125 11894 126 12019 127 12019 128 12272 129 12523 130 12776 131 13023 132 13280 133 13531 134 13784 135 14023 136 14288 137 14547 138 14808 139 15055 140 15320 141 15571 142 15824 143 16047 144 16328 145 16603 146 16880 147 17143 148 17424 149 17691 150 17960 151 18199 152 18488 153 18763 154 19040 155 19287 156 19568 157 19819 158 20072 159 20263 160 20576 161 20883 162 21192 163 21487 164 21800 165 22099 166 22400 167 22671 168 22992 169 23299 170 23608 171 23887 172 24200 173 24483 174 24768 175 24991 176 25328 177 25651 178 25976 179 26271 180 26600 181 26899 182 27200 183 27439 184 27776 185 28083 186 28392 187 28639 188 28952 189 29203 190 29456 191 29583 192 29960 193 30331 194 30704 195 31063 196 31440 197 31803 198 32168 199 32503 200 32888 201 33259 202 33632 203 33975 204 34352 205 34699 206 35048 207 35335 208 35736 209 36123 210 36512 211 36871 212 37264 213 37627 214 37992 215 38295 216 38696 217 39067 218 39440 219 39751 220 40128 221 40443 222 40760 223 40951 224 41384 225 41803 226 42224 227 42615 228 43040 229 43435 230 43832 231 44167 232 44600 233 45003 234 45408 235 45751 236 46160 237 46507 238 46856 239 47079 240 47528 241 47947 242 48368 243 48727 244 49152 245 49515 246 49880 247 50119 248 50552 249 50923 250 51296 251 51543 252 51920 253 52171 254 52424 255 52424 256 52933 257 53440 258 53949 259 54452 260 54965 261 55472 262 55981 263 56476 264 56997 265 57512 266 58029 267 58532 268 59053 269 59560 270 60069 271 60548 272 61085 273 61616 274 62149 275 62668 276 63205 277 63728 278 64253 279 64748 280 65293 281 65824 282 66357 283 66860 284 67397 285 67904 286 68413 287 68860 288 69429 289 69992 290 70557 291 71108 292 71677 293 72232 294 72789 295 73316 296 73893 297 74456 298 75021 299 75556 300 76125 301 76664 302 77205 303 77684 304 78277 305 78856 306 79437 307 79988 308 80573 309 81128 310 81685 311 82180 312 82773 313 83336 314 83901 315 84404 316 84973 317 85480 318 85989 319 86372 320 87005 321 87632 322 88261 323 88876 324 89509 325 90128 326 90749 327 91340 328 91981 329 92608 330 93237 331 93836 332 94469 333 95072 334 95677 335 96220 336 96877 337 97520 338 98165 339 98780 340 99429 341 100048 342 100669 343 101228 344 101885 345 102512 346 103141 347 103708 348 104341 349 104912 350 105485 351 105932 352 106621 353 107296 354 107973 355 108620 356 109301 357 109952 358 110605 359 111196 360 111885 361 112544 362 113205 363 113804 364 114469 365 115072 366 115677 367 116156 368 116861 369 117536 370 118213 371 118828 372 119509 373 120128 374 120749 375 121244 376 121933 377 122560 378 123189 379 123692 380 124325 381 124832 382 125341 383 125596 384 126357 385 127112 386 127869 387 128612 388 129373 389 130120 390 130869 391 131588 392 132357 393 133112 394 133869 395 134596 396 135357 397 136088 398 136821 399 137492 400 138277 401 139048 402 139821 403 140564 404 141341 405 142088 406 142837 407 143524 408 144309 409 145064 410 145821 411 146516 412 147277 413 147976 414 148677 415 149252 416 150069 417 150872 418 151677 419 152452 420 153261 421 154040 422 154821 423 155540 424 156357 425 157144 426 157933 427 158660 428 159453 429 160184 430 160917 431 161524 432 162357 433 163160 434 163965 435 164708 436 165517 437 166264 438 167013 439 167636 440 168453 441 169208 442 169965 443 170596 444 171357 445 171992 446 172629 447 173012 448 173893 449 174760 450 175629 451 176468 452 177341 453 178184 454 179029 455 179812 456 180693 457 181544 458 182397 459 183188 460 184045 461 184840 462 185637 463 186308 464 187205 465 188072 466 188941 467 189748 468 190621 469 191432 470 192245 471 192932 472 193813 473 194632 474 195453 475 196148 476 196973 477 197672 478 198373 479 198820 480 199749 481 200648 482 201549 483 202388 484 203293 485 204136 486 204981 487 205700 488 206613 489 207464 490 208317 491 209044 492 209901 493 210632 494 211365 495 211844 496 212773 497 213640 498 214509 499 215252 500 216125 501 216872 502 217621 503 218116 504 218997 505 219752 506 220509 507 221012 508 221773 509 222280 510 222789 511 222789 512 223810 513 224829 514 225850 515 226865 516 227890 517 228909 518 229930 519 230937 520 231970 521 232997 522 234026 523 235041 524 236074 525 237093 526 238114 527 239105 528 240154 529 241197 530 242242 531 243273 532 244322 533 245357 534 246394 535 247401 536 248458 537 249501 538 250546 539 251561 540 252610 541 253629 542 254650 543 255609 544 256690 545 257765 546 258842 547 259905 548 260986 549 262053 550 263122 551 264161 552 265250 553 266325 554 267402 555 268449 556 269530 557 270581 558 271634 559 272625 560 273730 561 274821 562 275914 563 276977 564 278074 565 279141 566 280210 567 281217 568 282322 569 283397 570 284474 571 285489 572 286570 573 287589 574 288610 575 289505 576 290650 577 291789 578 292930 579 294057 580 295202 581 296333 582 297466 583 298569 584 299722 585 300861 586 302002 587 303113 588 304258 589 305373 590 306490 591 307545 592 308714 593 309869 594 311026 595 312153 596 313314 597 314445 598 315578 599 316649 600 317818 601 318957 602 320098 603 321177 604 322322 605 323405 606 324490 607 325449 608 326650 609 327837 610 329026 611 330185 612 331378 613 332541 614 333706 615 334809 616 336010 617 337181 618 338354 619 339465 620 340642 621 341757 622 342874 623 343865 624 345082 625 346269 626 347458 627 348585 628 349778 629 350909 630 352042 631 353049 632 354250 633 355389 634 356530 635 357545 636 358690 637 359709 638 360730 639 361497 640 362770 641 364037 642 365306 643 366561 644 367834 645 369093 646 370354 647 371585 648 372866 649 374133 650 375402 651 376641 652 377914 653 379157 654 380402 655 381585 656 382882 657 384165 658 385450 659 386705 660 387994 661 389253 662 390514 663 391713 664 393010 665 394277 666 395546 667 396753 668 398026 669 399237 670 400450 671 401537 672 402866 673 404181 674 405498 675 406785 676 408106 677 409397 678 410690 679 411921 680 413250 681 414549 682 415850 683 417089 684 418394 685 419637 686 420882 687 422001 688 423346 689 424661 690 425978 691 427233 692 428554 693 429813 694 431074 695 432209 696 433538 697 434805 698 436074 699 437217 700 438490 701 439637 702 440786 703 441681 704 443074 705 444453 706 445834 707 447185 708 448570 709 449925 710 451282 711 452577 712 453970 713 455333 714 456698 715 458001 716 459370 717 460677 718 461986 719 463169 720 464578 721 465957 722 467338 723 468657 724 470042 725 471365 726 472690 727 473889 728 475282 729 476613 730 477946 731 479153 732 480490 733 481701 734 482914 735 483873 736 485314 737 486725 738 488138 739 489489 740 490906 741 492261 742 493618 743 494849 744 496274 745 497637 746 499002 747 500241 748 501610 749 502853 750 504098 751 505089 752 506530 753 507909 754 509290 755 510545 756 511930 757 513189 758 514450 759 515457 760 516850 761 518117 762 519386 763 520401 764 521674 765 522693 766 523714 767 524225 768 525754 769 527277 770 528802 771 530313 772 531842 773 533357 774 534874 775 536361 776 537898 777 539421 778 540946 779 542441 780 543970 781 545469 782 546970 783 548409 784 549962 785 551501 786 553042 787 554553 788 556098 789 557613 790 559130 791 560585 792 562138 793 563661 794 565186 795 566649 796 568178 797 569645 798 571114 799 572457 800 574042 801 575613 802 577186 803 578729 804 580306 805 581853 806 583402 807 584889 808 586474 809 588029 810 589586 811 591081 812 592642 813 594141 814 595642 815 597017 816 598618 817 600189 818 601762 819 603273 820 604850 821 606365 822 607882 823 609273 824 610858 825 612381 826 613906 827 615305 828 616834 829 618237 830 619642 831 620793 832 622442 833 624077 834 625714 835 627321 836 628962 837 630573 838 632186 839 633737 840 635386 841 637005 842 638626 843 640185 844 641810 845 643373 846 644938 847 646377 848 648042 849 649677 850 651314 851 652889 852 654530 853 656109 854 657690 855 659145 856 660794 857 662381 858 663970 859 665433 860 667026 861 668493 862 669962 863 671177 864 672874 865 674541 866 676210 867 677817 868 679490 869 681101 870 682714 871 684201 872 685882 873 687501 874 689122 875 690617 876 692242 877 693741 878 695242 879 696489 880 698186 881 699821 882 701458 883 702969 884 704610 885 706125 886 707642 887 708905 888 710554 889 712077 890 713602 891 714873 892 716402 893 717677 894 718954 895 719721 896 721498 897 723261 898 725026 899 726761 900 728530 901 730269 902 732010 903 733689 904 735466 905 737213 906 738962 907 740649 908 742402 909 744093 910 745786 911 747353 912 749146 913 750909 914 752674 915 754377 916 756146 917 757853 918 759562 919 761145 920 762922 921 764637 922 766354 923 767945 924 769666 925 771261 926 772858 927 774201 928 776026 929 777821 930 779618 931 781353 932 783154 933 784893 934 786634 935 788249 936 790058 937 791805 938 793554 939 795177 940 796930 941 798557 942 800186 943 801561 944 803386 945 805149 946 806914 947 808553 948 810322 949 811965 950 813610 951 815001 952 816778 953 818429 954 820082 955 821481 956 823138 957 824541 958 825946 959 826841 960 828730 961 830589 962 832450 963 834249 964 836114 965 837917 966 839722 967 841401 968 843274 969 845085 970 846898 971 848585 972 850402 973 852093 974 853786 975 855225 976 857114 977 858941 978 860770 979 862473 980 864306 981 866013 982 867722 983 869177 984 871018 985 872733 986 874450 987 875913 988 877634 989 879101 990 880570 991 881529 992 883450 993 885309 994 887170 995 888905 996 890770 997 892509 998 894250 999 895737 1000 897610