0 1 1 2 2 7 3 12 4 25 5 38 6 63 7 88 8 129 9 170 10 231 11 292 12 377 13 462 14 575 15 688 16 833 17 978 18 1159 19 1340 20 1561 21 1782 22 2047 23 2312 24 2625 25 2938 26 3303 27 3668 28 4089 29 4510 30 4991 31 5472 32 6017 33 6562 34 7175 35 7788 36 8473 37 9158 38 9919 39 10680 40 11521 41 12362 42 13287 43 14212 44 15225 45 16238 46 17343 47 18448 48 19649 49 20850 50 22151 51 23452 52 24857 53 26262 54 27775 55 29288 56 30913 57 32538 58 34279 59 36020 60 37881 61 39742 62 41727 63 43712 64 45825 65 47938 66 50183 67 52428 68 54809 69 57190 70 59711 71 62232 72 64897 73 67562 74 70375 75 73188 76 76153 77 79118 78 82239 79 85360 80 88641 81 91922 82 95367 83 98812 84 102425 85 106038 86 109823 87 113608 88 117569 89 121530 90 125671 91 129812 92 134137 93 138462 94 142975 95 147488 96 152193 97 156898 98 161799 99 166700 100 171801 101 176902 102 182207 103 187512 104 193025 105 198538 106 204263 107 209988 108 215929 109 221870 110 228031 111 234192 112 240577 113 246962 114 253575 115 260188 116 267033 117 273878 118 280959 119 288040 120 295361 121 302682 122 310247 123 317812 124 325625 125 333438 126 341503 127 349568 128 357889 129 366210 130 374791 131 383372 132 392217 133 401062 134 410175 135 419288 136 428673 137 438058 138 447719 139 457380 140 467321 141 477262 142 487487 143 497712 144 508225 145 518738 146 529543 147 540348 148 551449 149 562550 150 573951 151 585352 152 597057 153 608762 154 620775 155 632788 156 645113 157 657438 158 670079 159 682720 160 695681 161 708642 162 721927 163 735212 164 748825 165 762438 166 776383 167 790328 168 804609 169 818890 170 833511 171 848132 172 863097 173 878062 174 893375 175 908688 176 924353 177 940018 178 956039 179 972060 180 988441 181 1004822 182 1021567 183 1038312 184 1055425 185 1072538 186 1090023 187 1107508 188 1125369 189 1143230 190 1161471 191 1179712 192 1198337 193 1216962 194 1235975 195 1254988 196 1274393 197 1293798 198 1313599 199 1333400 200 1353601 201 1373802 202 1394407 203 1415012 204 1436025 205 1457038 206 1478463 207 1499888 208 1521729 209 1543570 210 1565831 211 1588092 212 1610777 213 1633462 214 1656575 215 1679688 216 1703233 217 1726778 218 1750759 219 1774740 220 1799161 221 1823582 222 1848447 223 1873312 224 1898625 225 1923938 226 1949703 227 1975468 228 2001689 229 2027910 230 2054591 231 2081272 232 2108417 233 2135562 234 2163175 235 2190788 236 2218873 237 2246958 238 2275519 239 2304080 240 2333121 241 2362162 242 2391687 243 2421212 244 2451225 245 2481238 246 2511743 247 2542248 248 2573249 249 2604250 250 2635751 251 2667252 252 2699257 253 2731262 254 2763775 255 2796288 256 2829313 257 2862338 258 2895879 259 2929420 260 2963481 261 2997542 262 3032127 263 3066712 264 3101825 265 3136938 266 3172583 267 3208228 268 3244409 269 3280590 270 3317311 271 3354032 272 3391297 273 3428562 274 3466375 275 3504188 276 3542553 277 3580918 278 3619839 279 3658760 280 3698241 281 3737722 282 3777767 283 3817812 284 3858425 285 3899038 286 3940223 287 3981408 288 4023169 289 4064930 290 4107271 291 4149612 292 4192537 293 4235462 294 4278975 295 4322488 296 4366593 297 4410698 298 4455399 299 4500100 300 4545401 301 4590702 302 4636607 303 4682512 304 4729025 305 4775538 306 4822663 307 4869788 308 4917529 309 4965270 310 5013631 311 5061992 312 5110977 313 5159962 314 5209575 315 5259188 316 5309433 317 5359678 318 5410559 319 5461440 320 5512961 321 5564482 322 5616647 323 5668812 324 5721625 325 5774438 326 5827903 327 5881368 328 5935489 329 5989610 330 6044391 331 6099172 332 6154617 333 6210062 334 6266175 335 6322288 336 6379073 337 6435858 338 6493319 339 6550780 340 6608921 341 6667062 342 6725887 343 6784712 344 6844225 345 6903738 346 6963943 347 7024148 348 7085049 349 7145950 350 7207551 351 7269152 352 7331457 353 7393762 354 7456775 355 7519788 356 7583513 357 7647238 358 7711679 359 7776120 360 7841281 361 7906442 362 7972327 363 8038212 364 8104825 365 8171438 366 8238783 367 8306128 368 8374209 369 8442290 370 8511111 371 8579932 372 8649497 373 8719062 374 8789375 375 8859688 376 8930753 377 9001818 378 9073639 379 9145460 380 9218041 381 9290622 382 9363967 383 9437312 384 9511425 385 9585538 386 9660423 387 9735308 388 9810969 389 9886630 390 9963071 391 10039512 392 10116737 393 10193962 394 10271975 395 10349988 396 10428793 397 10507598 398 10587199 399 10666800 400 10747201 401 10827602 402 10908807 403 10990012 404 11072025 405 11154038 406 11236863 407 11319688 408 11403329 409 11486970 410 11571431 411 11655892 412 11741177 413 11826462 414 11912575 415 11998688 416 12085633 417 12172578 418 12260359 419 12348140 420 12436761 421 12525382 422 12614847 423 12704312 424 12794625 425 12884938 426 12976103 427 13067268 428 13159289 429 13251310 430 13344191 431 13437072 432 13530817 433 13624562 434 13719175 435 13813788 436 13909273 437 14004758 438 14101119 439 14197480 440 14294721 441 14391962 442 14490087 443 14588212 444 14687225 445 14786238 446 14886143 447 14986048 448 15086849 449 15187650 450 15289351 451 15391052 452 15493657 453 15596262 454 15699775 455 15803288 456 15907713 457 16012138 458 16117479 459 16222820 460 16329081 461 16435342 462 16542527 463 16649712 464 16757825 465 16865938 466 16974983 467 17084028 468 17194009 469 17303990 470 17414911 471 17525832 472 17637697 473 17749562 474 17862375 475 17975188 476 18088953 477 18202718 478 18317439 479 18432160 480 18547841 481 18663522 482 18780167 483 18896812 484 19014425 485 19132038 486 19250623 487 19369208 488 19488769 489 19608330 490 19728871 491 19849412 492 19970937 493 20092462 494 20214975 495 20337488 496 20460993 497 20584498 498 20708999 499 20833500 500 20959001 501 21084502 502 21211007 503 21337512 504 21465025 505 21592538 506 21721063 507 21849588 508 21979129 509 22108670 510 22239231 511 22369792 512 22501377 513 22632962 514 22765575 515 22898188 516 23031833 517 23165478 518 23300159 519 23434840 520 23570561 521 23706282 522 23843047 523 23979812 524 24117625 525 24255438 526 24394303 527 24533168 528 24673089 529 24813010 530 24953991 531 25094972 532 25237017 533 25379062 534 25522175 535 25665288 536 25809473 537 25953658 538 26098919 539 26244180 540 26390521 541 26536862 542 26684287 543 26831712 544 26980225 545 27128738 546 27278343 547 27427948 548 27578649 549 27729350 550 27881151 551 28032952 552 28185857 553 28338762 554 28492775 555 28646788 556 28801913 557 28957038 558 29113279 559 29269520 560 29426881 561 29584242 562 29742727 563 29901212 564 30060825 565 30220438 566 30381183 567 30541928 568 30703809 569 30865690 570 31028711 571 31191732 572 31355897 573 31520062 574 31685375 575 31850688 576 32017153 577 32183618 578 32351239 579 32518860 580 32687641 581 32856422 582 33026367 583 33196312 584 33367425 585 33538538 586 33710823 587 33883108 588 34056569 589 34230030 590 34404671 591 34579312 592 34755137 593 34930962 594 35107975 595 35284988 596 35463193 597 35641398 598 35820799 599 36000200 600 36180801 601 36361402 602 36543207 603 36725012 604 36908025 605 37091038 606 37275263 607 37459488 608 37644929 609 37830370 610 38017031 611 38203692 612 38391577 613 38579462 614 38768575 615 38957688 616 39148033 617 39338378 618 39529959 619 39721540 620 39914361 621 40107182 622 40301247 623 40495312 624 40690625 625 40885938 626 41082503 627 41279068 628 41476889 629 41674710 630 41873791 631 42072872 632 42273217 633 42473562 634 42675175 635 42876788 636 43079673 637 43282558 638 43486719 639 43690880 640 43896321 641 44101762 642 44308487 643 44515212 644 44723225 645 44931238 646 45140543 647 45349848 648 45560449 649 45771050 650 45982951 651 46194852 652 46408057 653 46621262 654 46835775 655 47050288 656 47266113 657 47481938 658 47699079 659 47916220 660 48134681 661 48353142 662 48572927 663 48792712 664 49013825 665 49234938 666 49457383 667 49679828 668 49903609 669 50127390 670 50352511 671 50577632 672 50804097 673 51030562 674 51258375 675 51486188 676 51715353 677 51944518 678 52175039 679 52405560 680 52637441 681 52869322 682 53102567 683 53335812 684 53570425 685 53805038 686 54041023 687 54277008 688 54514369 689 54751730 690 54990471 691 55229212 692 55469337 693 55709462 694 55950975 695 56192488 696 56435393 697 56678298 698 56922599 699 57166900 700 57412601 701 57658302 702 57905407 703 58152512 704 58401025 705 58649538 706 58899463 707 59149388 708 59400729 709 59652070 710 59904831 711 60157592 712 60411777 713 60665962 714 60921575 715 61177188 716 61434233 717 61691278 718 61949759 719 62208240 720 62468161 721 62728082 722 62989447 723 63250812 724 63513625 725 63776438 726 64040703 727 64304968 728 64570689 729 64836410 730 65103591 731 65370772 732 65639417 733 65908062 734 66178175 735 66448288 736 66719873 737 66991458 738 67264519 739 67537580 740 67812121 741 68086662 742 68362687 743 68638712 744 68916225 745 69193738 746 69472743 747 69751748 748 70032249 749 70312750 750 70594751 751 70876752 752 71160257 753 71443762 754 71728775 755 72013788 756 72300313 757 72586838 758 72874879 759 73162920 760 73452481 761 73742042 762 74033127 763 74324212 764 74616825 765 74909438 766 75203583 767 75497728 768 75793409 769 76089090 770 76386311 771 76683532 772 76982297 773 77281062 774 77581375 775 77881688 776 78183553 777 78485418 778 78788839 779 79092260 780 79397241 781 79702222 782 80008767 783 80315312 784 80623425 785 80931538 786 81241223 787 81550908 788 81862169 789 82173430 790 82486271 791 82799112 792 83113537 793 83427962 794 83743975 795 84059988 796 84377593 797 84695198 798 85014399 799 85333600 800 85654401 801 85975202 802 86297607 803 86620012 804 86944025 805 87268038 806 87593663 807 87919288 808 88246529 809 88573770 810 88902631 811 89231492 812 89561977 813 89892462 814 90224575 815 90556688 816 90890433 817 91224178 818 91559559 819 91894940 820 92231961 821 92568982 822 92907647 823 93246312 824 93586625 825 93926938 826 94268903 827 94610868 828 94954489 829 95298110 830 95643391 831 95988672 832 96335617 833 96682562 834 97031175 835 97379788 836 97730073 837 98080358 838 98432319 839 98784280 840 99137921 841 99491562 842 99846887 843 100202212 844 100559225 845 100916238 846 101274943 847 101633648 848 101994049 849 102354450 850 102716551 851 103078652 852 103442457 853 103806262 854 104171775 855 104537288 856 104904513 857 105271738 858 105640679 859 106009620 860 106380281 861 106750942 862 107123327 863 107495712 864 107869825 865 108243938 866 108619783 867 108995628 868 109373209 869 109750790 870 110130111 871 110509432 872 110890497 873 111271562 874 111654375 875 112037188 876 112421753 877 112806318 878 113192639 879 113578960 880 113967041 881 114355122 882 114744967 883 115134812 884 115526425 885 115918038 886 116311423 887 116704808 888 117099969 889 117495130 890 117892071 891 118289012 892 118687737 893 119086462 894 119486975 895 119887488 896 120289793 897 120692098 898 121096199 899 121500300 900 121906201 901 122312102 902 122719807 903 123127512 904 123537025 905 123946538 906 124357863 907 124769188 908 125182329 909 125595470 910 126010431 911 126425392 912 126842177 913 127258962 914 127677575 915 128096188 916 128516633 917 128937078 918 129359359 919 129781640 920 130205761 921 130629882 922 131055847 923 131481812 924 131909625 925 132337438 926 132767103 927 133196768 928 133628289 929 134059810 930 134493191 931 134926572 932 135361817 933 135797062 934 136234175 935 136671288 936 137110273 937 137549258 938 137990119 939 138430980 940 138873721 941 139316462 942 139761087 943 140205712 944 140652225 945 141098738 946 141547143 947 141995548 948 142445849 949 142896150 950 143348351 951 143800552 952 144254657 953 144708762 954 145164775 955 145620788 956 146078713 957 146536638 958 146996479 959 147456320 960 147918081 961 148379842 962 148843527 963 149307212 964 149772825 965 150238438 966 150705983 967 151173528 968 151643009 969 152112490 970 152583911 971 153055332 972 153528697 973 154002062 974 154477375 975 154952688 976 155429953 977 155907218 978 156386439 979 156865660 980 157346841 981 157828022 982 158311167 983 158794312 984 159279425 985 159764538 986 160251623 987 160738708 988 161227769 989 161716830 990 162207871 991 162698912 992 163191937 993 163684962 994 164179975 995 164674988 996 165171993 997 165668998 998 166167999 999 166667000 1000 167168001