1 1 2 4 3 11 4 21 5 37 6 58 7 87 8 123 9 169 10 224 11 291 12 369 13 461 14 566 15 687 16 823 17 977 18 1148 19 1339 20 1549 21 1781 22 2034 23 2311 24 2611 25 2937 26 3288 27 3667 28 4073 29 4509 30 4974 31 5471 32 5999 33 6561 34 7156 35 7787 36 8453 37 9157 38 9898 39 10679 40 11499 41 12361 42 13264 43 14211 44 15201 45 16237 46 17318 47 18447 48 19623 49 20849 50 22124 51 23451 52 24829 53 26261 54 27746 55 29287 56 30883 57 32537 58 34248 59 36019 60 37849 61 39741 62 41694 63 43711 64 45791 65 47937 66 50148 67 52427 68 54773 69 57189 70 59674 71 62231 72 64859 73 67561 74 70336 75 73187 76 76113 77 79117 78 82198 79 85359 80 88599 81 91921 82 95324 83 98811 84 102381 85 106037 86 109778 87 113607 88 117523 89 121529 90 125624 91 129811 92 134089 93 138461 94 142926 95 147487 96 152143 97 156897 98 161748 99 166699 100 171749 101 176901 102 182154 103 187511 104 192971 105 198537 106 204208 107 209987 108 215873 109 221869 110 227974 111 234191 112 240519 113 246961 114 253516 115 260187 116 266973 117 273877 118 280898 119 288039 120 295299 121 302681 122 310184 123 317811 124 325561 125 333437 126 341438 127 349567 128 357823 129 366209 130 374724 131 383371 132 392149 133 401061 134 410106 135 419287 136 428603 137 438057 138 447648 139 457379 140 467249 141 477261 142 487414 143 497711 144 508151 145 518737 146 529468 147 540347 148 551373 149 562549 150 573874 151 585351 152 596979 153 608761 154 620696 155 632787 156 645033 157 657437 158 669998 159 682719 160 695599 161 708641 162 721844 163 735211 164 748741 165 762437 166 776298 167 790327 168 804523 169 818889 170 833424 171 848131 172 863009 173 878061 174 893286 175 908687 176 924263 177 940017 178 955948 179 972059 180 988349 181 1004821 182 1021474 183 1038311 184 1055331 185 1072537 186 1089928 187 1107507 188 1125273 189 1143229 190 1161374 191 1179711 192 1198239 193 1216961 194 1235876 195 1254987 196 1274293 197 1293797 198 1313498 199 1333399 200 1353499 201 1373801 202 1394304 203 1415011 204 1435921 205 1457037 206 1478358 207 1499887 208 1521623 209 1543569 210 1565724 211 1588091 212 1610669 213 1633461 214 1656466 215 1679687 216 1703123 217 1726777 218 1750648 219 1774739 220 1799049 221 1823581 222 1848334 223 1873311 224 1898511 225 1923937 226 1949588 227 1975467 228 2001573 229 2027909 230 2054474 231 2081271 232 2108299 233 2135561 234 2163056 235 2190787 236 2218753 237 2246957 238 2275398 239 2304079 240 2332999 241 2362161 242 2391564 243 2421211 244 2451101 245 2481237 246 2511618 247 2542247 248 2573123 249 2604249 250 2635624 251 2667251 252 2699129 253 2731261 254 2763646 255 2796287 256 2829183 257 2862337 258 2895748 259 2929419 260 2963349 261 2997541 262 3031994 263 3066711 264 3101691 265 3136937 266 3172448 267 3208227 268 3244273 269 3280589 270 3317174 271 3354031 272 3391159 273 3428561 274 3466236 275 3504187 276 3542413 277 3580917 278 3619698 279 3658759 280 3698099 281 3737721 282 3777624 283 3817811 284 3858281 285 3899037 286 3940078 287 3981407 288 4023023 289 4064929 290 4107124 291 4149611 292 4192389 293 4235461 294 4278826 295 4322487 296 4366443 297 4410697 298 4455248 299 4500099 300 4545249 301 4590701 302 4636454 303 4682511 304 4728871 305 4775537 306 4822508 307 4869787 308 4917373 309 4965269 310 5013474 311 5061991 312 5110819 313 5159961 314 5209416 315 5259187 316 5309273 317 5359677 318 5410398 319 5461439 320 5512799 321 5564481 322 5616484 323 5668811 324 5721461 325 5774437 326 5827738 327 5881367 328 5935323 329 5989609 330 6044224 331 6099171 332 6154449 333 6210061 334 6266006 335 6322287 336 6378903 337 6435857 338 6493148 339 6550779 340 6608749 341 6667061 342 6725714 343 6784711 344 6844051 345 6903737 346 6963768 347 7024147 348 7084873 349 7145949 350 7207374 351 7269151 352 7331279 353 7393761 354 7456596 355 7519787 356 7583333 357 7647237 358 7711498 359 7776119 360 7841099 361 7906441 362 7972144 363 8038211 364 8104641 365 8171437 366 8238598 367 8306127 368 8374023 369 8442289 370 8510924 371 8579931 372 8649309 373 8719061 374 8789186 375 8859687 376 8930563 377 9001817 378 9073448 379 9145459 380 9217849 381 9290621 382 9363774 383 9437311 384 9511231 385 9585537 386 9660228 387 9735307 388 9810773 389 9886629 390 9962874 391 10039511 392 10116539 393 10193961 394 10271776 395 10349987 396 10428593 397 10507597 398 10586998 399 10666799 400 10746999 401 10827601 402 10908604 403 10990011 404 11071821 405 11154037 406 11236658 407 11319687 408 11403123 409 11486969 410 11571224 411 11655891 412 11740969 413 11826461 414 11912366 415 11998687 416 12085423 417 12172577 418 12260148 419 12348139 420 12436549 421 12525381 422 12614634 423 12704311 424 12794411 425 12884937 426 12975888 427 13067267 428 13159073 429 13251309 430 13343974 431 13437071 432 13530599 433 13624561 434 13718956 435 13813787 436 13909053 437 14004757 438 14100898 439 14197479 440 14294499 441 14391961 442 14489864 443 14588211 444 14687001 445 14786237 446 14885918 447 14986047 448 15086623 449 15187649 450 15289124 451 15391051 452 15493429 453 15596261 454 15699546 455 15803287 456 15907483 457 16012137 458 16117248 459 16222819 460 16328849 461 16435341 462 16542294 463 16649711 464 16757591 465 16865937 466 16974748 467 17084027 468 17193773 469 17303989 470 17414674 471 17525831 472 17637459 473 17749561 474 17862136 475 17975187 476 18088713 477 18202717 478 18317198 479 18432159 480 18547599 481 18663521 482 18779924 483 18896811 484 19014181 485 19132037 486 19250378 487 19369207 488 19488523 489 19608329 490 19728624 491 19849411 492 19970689 493 20092461 494 20214726 495 20337487 496 20460743 497 20584497 498 20708748 499 20833499 500 20958749 501 21084501 502 21210754 503 21337511 504 21464771 505 21592537 506 21720808 507 21849587 508 21978873 509 22108669 510 22238974 511 22369791 512 22501119 513 22632961 514 22765316 515 22898187 516 23031573 517 23165477 518 23299898 519 23434839 520 23570299 521 23706281 522 23842784 523 23979811 524 24117361 525 24255437 526 24394038 527 24533167 528 24672823 529 24813009 530 24953724 531 25094971 532 25236749 533 25379061 534 25521906 535 25665287 536 25809203 537 25953657 538 26098648 539 26244179 540 26390249 541 26536861 542 26684014 543 26831711 544 26979951 545 27128737 546 27278068 547 27427947 548 27578373 549 27729349 550 27880874 551 28032951 552 28185579 553 28338761 554 28492496 555 28646787 556 28801633 557 28957037 558 29112998 559 29269519 560 29426599 561 29584241 562 29742444 563 29901211 564 30060541 565 30220437 566 30380898 567 30541927 568 30703523 569 30865689 570 31028424 571 31191731 572 31355609 573 31520061 574 31685086 575 31850687 576 32016863 577 32183617 578 32350948 579 32518859 580 32687349 581 32856421 582 33026074 583 33196311 584 33367131 585 33538537 586 33710528 587 33883107 588 34056273 589 34230029 590 34404374 591 34579311 592 34754839 593 34930961 594 35107676 595 35284987 596 35462893 597 35641397 598 35820498 599 36000199 600 36180499 601 36361401 602 36542904 603 36725011 604 36907721 605 37091037 606 37274958 607 37459487 608 37644623 609 37830369 610 38016724 611 38203691 612 38391269 613 38579461 614 38768266 615 38957687 616 39147723 617 39338377 618 39529648 619 39721539 620 39914049 621 40107181 622 40300934 623 40495311 624 40690311 625 40885937 626 41082188 627 41279067 628 41476573 629 41674709 630 41873474 631 42072871 632 42272899 633 42473561 634 42674856 635 42876787 636 43079353 637 43282557 638 43486398 639 43690879 640 43895999 641 44101761 642 44308164 643 44515211 644 44722901 645 44931237 646 45140218 647 45349847 648 45560123 649 45771049 650 45982624 651 46194851 652 46407729 653 46621261 654 46835446 655 47050287 656 47265783 657 47481937 658 47698748 659 47916219 660 48134349 661 48353141 662 48572594 663 48792711 664 49013491 665 49234937 666 49457048 667 49679827 668 49903273 669 50127389 670 50352174 671 50577631 672 50803759 673 51030561 674 51258036 675 51486187 676 51715013 677 51944517 678 52174698 679 52405559 680 52637099 681 52869321 682 53102224 683 53335811 684 53570081 685 53805037 686 54040678 687 54277007 688 54514023 689 54751729 690 54990124 691 55229211 692 55468989 693 55709461 694 55950626 695 56192487 696 56435043 697 56678297 698 56922248 699 57166899 700 57412249 701 57658301 702 57905054 703 58152511 704 58400671 705 58649537 706 58899108 707 59149387 708 59400373 709 59652069 710 59904474 711 60157591 712 60411419 713 60665961 714 60921216 715 61177187 716 61433873 717 61691277 718 61949398 719 62208239 720 62467799 721 62728081 722 62989084 723 63250811 724 63513261 725 63776437 726 64040338 727 64304967 728 64570323 729 64836409 730 65103224 731 65370771 732 65639049 733 65908061 734 66177806 735 66448287 736 66719503 737 66991457 738 67264148 739 67537579 740 67811749 741 68086661 742 68362314 743 68638711 744 68915851 745 69193737 746 69472368 747 69751747 748 70031873 749 70312749 750 70594374 751 70876751 752 71159879 753 71443761 754 71728396 755 72013787 756 72299933 757 72586837 758 72874498 759 73162919 760 73452099 761 73742041 762 74032744 763 74324211 764 74616441 765 74909437 766 75203198 767 75497727 768 75793023 769 76089089 770 76385924 771 76683531 772 76981909 773 77281061 774 77580986 775 77881687 776 78183163 777 78485417 778 78788448 779 79092259 780 79396849 781 79702221 782 80008374 783 80315311 784 80623031 785 80931537 786 81240828 787 81550907 788 81861773 789 82173429 790 82485874 791 82799111 792 83113139 793 83427961 794 83743576 795 84059987 796 84377193 797 84695197 798 85013998 799 85333599 800 85653999 801 85975201 802 86297204 803 86620011 804 86943621 805 87268037 806 87593258 807 87919287 808 88246123 809 88573769 810 88902224 811 89231491 812 89561569 813 89892461 814 90224166 815 90556687 816 90890023 817 91224177 818 91559148 819 91894939 820 92231549 821 92568981 822 92907234 823 93246311 824 93586211 825 93926937 826 94268488 827 94610867 828 94954073 829 95298109 830 95642974 831 95988671 832 96335199 833 96682561 834 97030756 835 97379787 836 97729653 837 98080357 838 98431898 839 98784279 840 99137499 841 99491561 842 99846464 843 100202211 844 100558801 845 100916237 846 101274518 847 101633647 848 101993623 849 102354449 850 102716124 851 103078651 852 103442029 853 103806261 854 104171346 855 104537287 856 104904083 857 105271737 858 105640248 859 106009619 860 106379849 861 106750941 862 107122894 863 107495711 864 107869391 865 108243937 866 108619348 867 108995627 868 109372773 869 109750789 870 110129674 871 110509431 872 110890059 873 111271561 874 111653936 875 112037187 876 112421313 877 112806317 878 113192198 879 113578959 880 113966599 881 114355121 882 114744524 883 115134811 884 115525981 885 115918037 886 116310978 887 116704807 888 117099523 889 117495129 890 117891624 891 118289011 892 118687289 893 119086461 894 119486526 895 119887487 896 120289343 897 120692097 898 121095748 899 121500299 900 121905749 901 122312101 902 122719354 903 123127511 904 123536571 905 123946537 906 124357408 907 124769187 908 125181873 909 125595469 910 126009974 911 126425391 912 126841719 913 127258961 914 127677116 915 128096187 916 128516173 917 128937077 918 129358898 919 129781639 920 130205299 921 130629881 922 131055384 923 131481811 924 131909161 925 132337437 926 132766638 927 133196767 928 133627823 929 134059809 930 134492724 931 134926571 932 135361349 933 135797061 934 136233706 935 136671287 936 137109803 937 137549257 938 137989648 939 138430979 940 138873249 941 139316461 942 139760614 943 140205711 944 140651751 945 141098737 946 141546668 947 141995547 948 142445373 949 142896149 950 143347874 951 143800551 952 144254179 953 144708761 954 145164296 955 145620787 956 146078233 957 146536637 958 146995998 959 147456319 960 147917599 961 148379841 962 148843044 963 149307211 964 149772341 965 150238437 966 150705498 967 151173527 968 151642523 969 152112489 970 152583424 971 153055331 972 153528209 973 154002061 974 154476886 975 154952687 976 155429463 977 155907217 978 156385948 979 156865659 980 157346349 981 157828021 982 158310674 983 158794311 984 159278931 985 159764537 986 160251128 987 160738707 988 161227273 989 161716829 990 162207374 991 162698911 992 163191439 993 163684961 994 164179476 995 164674987 996 165171493 997 165668997 998 166167498 999 166666999 1000 167167499