1 0 2 1 3 4 4 7 5 14 6 19 7 28 8 34 9 45 10 53 11 72 12 80 13 96 14 105 15 119 16 139 17 168 18 179 19 213 20 234 21 248 22 269 23 312 24 327 25 363 26 391 27 430 28 452 29 493 30 530 31 570 32 593 33 645 34 677 35 732 36 756 37 801 38 844 39 885 40 922 41 981 42 1019 43 1100 44 1137 45 1188 46 1224 47 1283 48 1344 49 1397 50 1463 51 1524 52 1567 53 1668 54 1703 55 1793 56 1868 57 1926 58 1973 59 2087 60 2167 61 2280 62 2328 63 2379 64 2450 65 2520 66 2553 67 2659 68 2758 69 2824 70 2887 71 3025 72 3102 73 3194 74 3267 75 3349 76 3457 77 3587 78 3687 79 3816 80 3879 81 3978 82 4045 83 4192 84 4260 85 4342 86 4425 87 4517 88 4643 89 4817 90 4936 91 5052 92 5129 93 5269 94 5404 95 5519 96 5649 97 5798 98 5890 99 5976 100 6053 101 6252 102 6317 103 6520 104 6614 105 6712 106 6818 107 6967 108 7112 109 7263 110 7378 111 7487 112 7650 113 7789 114 7940 115 8076 116 8172 117 8278 118 8393 119 8576 120 8674 121 8841 122 8969 123 9166 124 9289 125 9499 126 9638 127 9821 128 9987 129 10152 130 10250 131 10427 132 10597 133 10834 134 10968 135 11086 136 11213 137 11484 138 11569 139 11836 140 11953 141 12182 142 12322 143 12511 144 12705 145 12884 146 13029 147 13202 148 13332 149 13522 150 13646 151 13870 152 13998 153 14139 154 14297 155 14565 156 14699 157 15010 158 15146 159 15324 160 15445 161 15703 162 15916 163 16152 164 16285 165 16500 166 16620 167 16828 168 16949 169 17268 170 17388 171 17537 172 17764 173 18020 174 18140 175 18330 176 18444 177 18610 178 18762 179 18995 180 19187 181 19521 182 19712 183 19895 184 20114 185 20351 186 20595 187 20848 188 21029 189 21307 190 21538 191 21812 192 21952 193 22224 194 22379 195 22638 196 22767 197 23090 198 23226 199 23479 200 23754 201 23944 202 24134 203 24389 204 24644 205 24905 206 25154 207 25380 208 25525 209 25869 210 26061 211 26379 212 26617 213 26959 214 27273 215 27587 216 27844 217 28130 218 28313 219 28660 220 28827 221 29168 222 29352 223 29645 224 29875 225 30172 226 30386 227 30723 228 30907 229 31355 230 31622 231 31850 232 32029 233 32492 234 32684 235 32985 236 33219 237 33528 238 33687 239 34073 240 34362 241 34675 242 34958 243 35208 244 35402 245 35682 246 35839 247 36305 248 36615 249 36907 250 37220 251 37569 252 37785 253 38116 254 38354 255 38599 256 38946 257 39286 258 39488 259 39832 260 40045 261 40415 262 40742 263 41124 264 41283 265 41646 266 41831 267 42262 268 42503 269 43020 270 43164 271 43514 272 43767 273 44086 274 44325 275 44662 276 44878 277 45283 278 45649 279 46099 280 46468 281 46887 282 47165 283 47672 284 47944 285 48217 286 48595 287 49064 288 49302 289 49657 290 50020 291 50318 292 50598 293 50985 294 51209 295 51725 296 52101 297 52446 298 52686 299 53047 300 53426 301 53828 302 54122 303 54466 304 54752 305 55132 306 55337 307 55948 308 56211 309 56613 310 56930 311 57363 312 57664 313 58118 314 58422 315 58643 316 59082 317 59498 318 59752 319 60148 320 60410 321 60729 322 61058 323 61504 324 61761 325 62175 326 62498 327 62872 328 63177 329 63670 330 63876 331 64315 332 64719 333 65138 334 65457 335 65913 336 66223 337 66887 338 67372 339 67756 340 68025 341 68501 342 68940 343 69323 344 69823 345 70301 346 70726 347 71243 348 71692 349 72213 350 72557 351 73103 352 73595 353 74220 354 74423 355 75038 356 75374 357 75723 358 76124 359 76659 360 76958 361 77445 362 77809 363 78349 364 78847 365 79492 366 79753 367 80482 368 80830 369 81206 370 81518 371 82010 372 82271 373 82941 374 83334 375 83644 376 83989 377 84698 378 84991 379 85745 380 86158 381 86588 382 86958 383 87462 384 87706 385 88137 386 88539 387 89025 388 89415 389 90009 390 90354 391 90814 392 91159 393 91803 394 92245 395 92859 396 93213 397 93870 398 94150 399 94495 400 94966 401 95563 402 96058 403 96627 404 97079 405 97695 406 98058 407 98548 408 98861 409 99606 410 99882 411 100274 412 100674 413 101126 414 101444 415 101949 416 102396 417 102772 418 103150 419 103733 420 104165 421 104913 422 105393 423 105921 424 106402 425 106928 426 107262 427 107758 428 108139 429 108802 430 109174 431 109778 432 110120 433 110723 434 111329 435 111983 436 112619 437 113412 438 113677 439 114513 440 114896 441 115356 442 115685 443 116458 444 116813 445 117610 446 117989 447 118725 448 119149 449 120021 450 120407 451 121179 452 121686 453 122120 454 122514 455 122926 456 123283 457 124188 458 124556 459 125060 460 125387 461 126302 462 126628 463 127319 464 127972 465 128416 466 128870 467 129493 468 129996 469 130543 470 131094 471 131558 472 131978 473 132575 474 133099 475 133934 476 134350 477 134846 478 135306 479 135941 480 136505 481 137312 482 137745 483 138261 484 138771 485 139461 486 139876 487 140567 488 141204 489 141654 490 141971 491 142950 492 143226 493 143831 494 144529 495 145154 496 145632 497 146200 498 146532 499 147195 500 147649 501 148440 502 148810 503 149501 504 150092 505 150738 506 151078 507 151635 508 152116 509 152862 510 153144 511 153741 512 154273 513 155022 514 155409 515 156163 516 156759 517 157558 518 158021 519 158853 520 159381 521 160246 522 160642 523 161416 524 161922 525 162327 526 162892 527 163629 528 164124 529 164795 530 165396 531 165864 532 166241 533 167241 534 167752 535 168425 536 169106 537 169670 538 170119 539 171043 540 171715 541 172679 542 173422 543 174039 544 174638 545 175335 546 175755 547 176591 548 177396 549 177924 550 178294 551 179070 552 179365 553 180257 554 180951 555 181604 556 182139 557 183060 558 183373 559 184437 560 184938 561 185412 562 185866 563 186704 564 187110 565 187672 566 188222 567 188811 568 189392 569 190186 570 190599 571 191547 572 192155 573 192973 574 193710 575 194286 576 194648 577 195501 578 196138 579 196787 580 197574 581 198228 582 198593 583 199688 584 200246 585 200810 586 201311 587 202426 588 202814 589 203639 590 204427 591 205389 592 206056 593 206935 594 207569 595 208537 596 209311 597 210285 598 210855 599 211770 600 212063 601 213258 602 213700 603 214322 604 214907 605 215815 606 216453 607 217444 608 218021 609 218947 610 219784 611 220639 612 221379 613 222393 614 223095 615 223728 616 224159 617 225327 618 225924 619 226741 620 227589 621 228370 622 228911 623 230061 624 230596 625 231410 626 231957 627 232672 628 233259 629 234220 630 234564 631 235383 632 236094 633 236687 634 237567 635 238437 636 239044 637 239841 638 240462 639 241065 640 241620 641 242428 642 242938 643 243900 644 244323 645 245075 646 245863 647 247153 648 247985 649 249071 650 249918 651 250467 652 251152 653 252098 654 252545 655 253578 656 254090 657 254758 658 255299 659 256555 660 257185 661 258371 662 259335 663 260026 664 260645 665 261487 666 262320 667 263111 668 264098 669 264851 670 265755 671 266652 672 267052 673 268057 674 269037 675 269825 676 270661 677 271987 678 272851 679 274103 680 275024 681 275794 682 276417 683 277552 684 278039 685 279244 686 279829 687 280888 688 281561 689 282719 690 283566 691 284483 692 285510 693 286038 694 286607 695 287828 696 288373 697 289692 698 290248 699 290983 700 291758 701 292807 702 293711 703 295001 704 295849 705 296846 706 297508 707 298456 708 299027 709 300439 710 301421 711 302584 712 303284 713 304296 714 304705 715 305744 716 306445 717 307468 718 308119 719 309452 720 309937 721 311269 722 312211 723 313398 724 313982 725 314901 726 315583 727 317002 728 317603 729 318685 730 319549 731 320905 732 321678 733 322600 734 323255 735 324132 736 324718 737 325740 738 326163 739 327351 740 328097 741 329091 742 329822 743 330934 744 331534 745 332427 746 333274 747 334119 748 334917 749 335971 750 336868 751 337930 752 338589 753 339544 754 340257 755 341348 756 341871 757 343129 758 344242 759 345019 760 346060 761 347073 762 347792 763 348812 764 349540 765 350221 766 351328 767 352408 768 352957 769 354423 770 355131 771 356068 772 356833 773 358369 774 359312 775 360279 776 361180 777 361909 778 363071 779 364518 780 364905 781 365976 782 366529 783 367747 784 368817 785 369971 786 370850 787 371948 788 372728 789 373631 790 374734 791 375792 792 376278 793 377213 794 378353 795 379559 796 380689 797 382278 798 382720 799 383725 800 384683 801 385929 802 386855 803 388108 804 388702 805 389589 806 390460 807 391255 808 392261 809 393875 810 394701 811 396046 812 396733 813 398072 814 398806 815 399861 816 400520 817 401557 818 402632 819 403458 820 404025 821 405281 822 406345 823 407818 824 408638 825 409443 826 410343 827 411664 828 412283 829 413932 830 414675 831 415630 832 416349 833 417562 834 418238 835 419300 836 419932 837 420876 838 421570 839 422739 840 423446 841 424679 842 425936 843 426845 844 427937 845 429356 846 430042 847 431116 848 431883 849 432992 850 433660 851 434788 852 435475 853 437008 854 437728 855 438582 856 439281 857 440705 858 441580 859 442780 860 443426 861 444325 862 445338 863 446485 864 447395 865 448719 866 449719 867 451076 868 451852 869 453055 870 453920 871 455070 872 455674 873 456667 874 457914 875 458790 876 459288 877 460455 878 461355 879 462398 880 463129 881 464865 882 465549 883 466933 884 468188 885 469005 886 469914 887 471076 888 471758 889 472875 890 473648 891 474560 892 475354 893 476536 894 477258 895 478243 896 479520 897 480266 898 481152 899 482250 900 482710 901 483885 902 484753 903 486144 904 486882 905 487868 906 488601 907 490105 908 491076 909 491963 910 493073 911 494762 912 495480 913 496536 914 497268 915 498027 916 499067 917 500754 918 501318 919 502540 920 503232 921 504133 922 505371 923 506835 924 507486 925 508458 926 509214 927 510116 928 511016 929 512365 930 513222 931 514265 932 515456 933 516524 934 517439 935 518897 936 520066 937 521466 938 522141 939 523372 940 524188 941 525524 942 526284 943 527438 944 528348 945 529071 946 530102 947 531518 948 532244 949 533582 950 534322 951 535408 952 536238 953 537494 954 538250 955 539386 956 540304 957 541328 958 542242 959 543512 960 544220 961 545533 962 546914 963 548020 964 548815 965 550285 966 551285 967 552877 968 554172 969 555045 970 555918 971 557178 972 557796 973 558914 974 559839 975 560853 976 561958 977 563420 978 564036 979 565206 980 565838 981 566855 982 568106 983 569435 984 570499 985 572255 986 573458 987 574459 988 575855 989 577446 990 577981 991 579959 992 581410 993 582444 994 583177 995 584811 996 585769 997 587700 998 588441 999 589649 1000 591014