0 1 1 4 2 11 3 23 4 41 5 67 6 102 7 147 8 204 9 274 10 358 11 458 12 575 13 710 14 865 15 1041 16 1239 17 1461 18 1708 19 1981 20 2282 21 2612 22 2972 23 3364 24 3789 25 4248 26 4743 27 5275 28 5845 29 6455 30 7106 31 7799 32 8536 33 9318 34 10146 35 11022 36 11947 37 12922 38 13949 39 15029 40 16163 41 17353 42 18600 43 19905 44 21270 45 22696 46 24184 47 25736 48 27353 49 29036 50 30787 51 32607 52 34497 53 36459 54 38494 55 40603 56 42788 57 45050 58 47390 59 49810 60 52311 61 54894 62 57561 63 60313 64 63151 65 66077 66 69092 67 72197 68 75394 69 78684 70 82068 71 85548 72 89125 73 92800 74 96575 75 100451 76 104429 77 108511 78 112698 79 116991 80 121392 81 125902 82 130522 83 135254 84 140099 85 145058 86 150133 87 155325 88 160635 89 166065 90 171616 91 177289 92 183086 93 189008 94 195056 95 201232 96 207537 97 213972 98 220539 99 227239 100 234073 101 241043 102 248150 103 255395 104 262780 105 270306 106 277974 107 285786 108 293743 109 301846 110 310097 111 318497 112 327047 113 335749 114 344604 115 353613 116 362778 117 372100 118 381580 119 391220 120 401021 121 410984 122 421111 123 431403 124 441861 125 452487 126 463282 127 474247 128 485384 129 496694 130 508178 131 519838 132 531675 133 543690 134 555885 135 568261 136 580819 137 593561 138 606488 139 619601 140 632902 141 646392 142 660072 143 673944 144 688009 145 702268 146 716723 147 731375 148 746225 149 761275 150 776526 151 791979 152 807636 153 823498 154 839566 155 855842 156 872327 157 889022 158 905929 159 923049 160 940383 161 957933 162 975700 163 993685 164 1011890 165 1030316 166 1048964 167 1067836 168 1086933 169 1106256 170 1125807 171 1145587 172 1165597 173 1185839 174 1206314 175 1227023 176 1247968 177 1269150 178 1290570 179 1312230 180 1334131 181 1356274 182 1378661 183 1401293 184 1424171 185 1447297 186 1470672 187 1494297 188 1518174 189 1542304 190 1566688 191 1591328 192 1616225 193 1641380 194 1666795 195 1692471 196 1718409 197 1744611 198 1771078 199 1797811 200 1824812 201 1852082 202 1879622 203 1907434 204 1935519 205 1963878 206 1992513 207 2021425 208 2050615 209 2080085 210 2109836 211 2139869 212 2170186 213 2200788 214 2231676 215 2262852 216 2294317 217 2326072 218 2358119 219 2390459 220 2423093 221 2456023 222 2489250 223 2522775 224 2556600 225 2590726 226 2625154 227 2659886 228 2694923 229 2730266 230 2765917 231 2801877 232 2838147 233 2874729 234 2911624 235 2948833 236 2986358 237 3024200 238 3062360 239 3100840 240 3139641 241 3178764 242 3218211 243 3257983 244 3298081 245 3338507 246 3379262 247 3420347 248 3461764 249 3503514 250 3545598 251 3588018 252 3630775 253 3673870 254 3717305 255 3761081 256 3805199 257 3849661 258 3894468 259 3939621 260 3985122 261 4030972 262 4077172 263 4123724 264 4170629 265 4217888 266 4265503 267 4313475 268 4361805 269 4410495 270 4459546 271 4508959 272 4558736 273 4608878 274 4659386 275 4710262 276 4761507 277 4813122 278 4865109 279 4917469 280 4970203 281 5023313 282 5076800 283 5130665 284 5184910 285 5239536 286 5294544 287 5349936 288 5405713 289 5461876 290 5518427 291 5575367 292 5632697 293 5690419 294 5748534 295 5807043 296 5865948 297 5925250 298 5984950 299 6045050 300 6105551 301 6166454 302 6227761 303 6289473 304 6351591 305 6414117 306 6477052 307 6540397 308 6604154 309 6668324 310 6732908 311 6797908 312 6863325 313 6929160 314 6995415 315 7062091 316 7129189 317 7196711 318 7264658 319 7333031 320 7401832 321 7471062 322 7540722 323 7610814 324 7681339 325 7752298 326 7823693 327 7895525 328 7967795 329 8040505 330 8113656 331 8187249 332 8261286 333 8335768 334 8410696 335 8486072 336 8561897 337 8638172 338 8714899 339 8792079 340 8869713 341 8947803 342 9026350 343 9105355 344 9184820 345 9264746 346 9345134 347 9425986 348 9507303 349 9589086 350 9671337 351 9754057 352 9837247 353 9920909 354 10005044 355 10089653 356 10174738 357 10260300 358 10346340 359 10432860 360 10519861 361 10607344 362 10695311 363 10783763 364 10872701 365 10962127 366 11052042 367 11142447 368 11233344 369 11324734 370 11416618 371 11508998 372 11601875 373 11695250 374 11789125 375 11883501 376 11978379 377 12073761 378 12169648 379 12266041 380 12362942 381 12460352 382 12558272 383 12656704 384 12755649 385 12855108 386 12955083 387 13055575 388 13156585 389 13258115 390 13360166 391 13462739 392 13565836 393 13669458 394 13773606 395 13878282 396 13983487 397 14089222 398 14195489 399 14302289 400 14409623 401 14517493 402 14625900 403 14734845 404 14844330 405 14954356 406 15064924 407 15176036 408 15287693 409 15399896 410 15512647 411 15625947 412 15739797 413 15854199 414 15969154 415 16084663 416 16200728 417 16317350 418 16434530 419 16552270 420 16670571 421 16789434 422 16908861 423 17028853 424 17149411 425 17270537 426 17392232 427 17514497 428 17637334 429 17760744 430 17884728 431 18009288 432 18134425 433 18260140 434 18386435 435 18513311 436 18640769 437 18768811 438 18897438 439 19026651 440 19156452 441 19286842 442 19417822 443 19549394 444 19681559 445 19814318 446 19947673 447 20081625 448 20216175 449 20351325 450 20487076 451 20623429 452 20760386 453 20897948 454 21036116 455 21174892 456 21314277 457 21454272 458 21594879 459 21736099 460 21877933 461 22020383 462 22163450 463 22307135 464 22451440 465 22596366 466 22741914 467 22888086 468 23034883 469 23182306 470 23330357 471 23479037 472 23628347 473 23778289 474 23928864 475 24080073 476 24231918 477 24384400 478 24537520 479 24691280 480 24845681 481 25000724 482 25156411 483 25312743 484 25469721 485 25627347 486 25785622 487 25944547 488 26104124 489 26264354 490 26425238 491 26586778 492 26748975 493 26911830 494 27075345 495 27239521 496 27404359 497 27569861 498 27736028 499 27902861 500 28070362 501 28238532 502 28407372 503 28576884 504 28747069 505 28917928 506 29089463 507 29261675 508 29434565 509 29608135 510 29782386 511 29957319 512 30132936 513 30309238 514 30486226 515 30663902 516 30842267 517 31021322 518 31201069 519 31381509 520 31562643 521 31744473 522 31927000 523 32110225 524 32294150 525 32478776 526 32664104 527 32850136 528 33036873 529 33224316 530 33412467 531 33601327 532 33790897 533 33981179 534 34172174 535 34363883 536 34556308 537 34749450 538 34943310 539 35137890 540 35333191 541 35529214 542 35725961 543 35923433 544 36121631 545 36320557 546 36520212 547 36720597 548 36921714 549 37123564 550 37326148 551 37529468 552 37733525 553 37938320 554 38143855 555 38350131 556 38557149 557 38764911 558 38973418 559 39182671 560 39392672 561 39603422 562 39814922 563 40027174 564 40240179 565 40453938 566 40668453 567 40883725 568 41099755 569 41316545 570 41534096 571 41752409 572 41971486 573 42191328 574 42411936 575 42633312 576 42855457 577 43078372 578 43302059 579 43526519 580 43751753 581 43977763 582 44204550 583 44432115 584 44660460 585 44889586 586 45119494 587 45350186 588 45581663 589 45813926 590 46046977 591 46280817 592 46515447 593 46750869 594 46987084 595 47224093 596 47461898 597 47700500 598 47939900 599 48180100 600 48421101 601 48662904 602 48905511 603 49148923 604 49393141 605 49638167 606 49884002 607 50130647 608 50378104 609 50626374 610 50875458 611 51125358 612 51376075 613 51627610 614 51879965 615 52133141 616 52387139 617 52641961 618 52897608 619 53154081 620 53411382 621 53669512 622 53928472 623 54188264 624 54448889 625 54710348 626 54972643 627 55235775 628 55499745 629 55764555 630 56030206 631 56296699 632 56564036 633 56832218 634 57101246 635 57371122 636 57641847 637 57913422 638 58185849 639 58459129 640 58733263 641 59008253 642 59284100 643 59560805 644 59838370 645 60116796 646 60396084 647 60676236 648 60957253 649 61239136 650 61521887 651 61805507 652 62089997 653 62375359 654 62661594 655 62948703 656 63236688 657 63525550 658 63815290 659 64105910 660 64397411 661 64689794 662 64983061 663 65277213 664 65572251 665 65868177 666 66164992 667 66462697 668 66761294 669 67060784 670 67361168 671 67662448 672 67964625 673 68267700 674 68571675 675 68876551 676 69182329 677 69489011 678 69796598 679 70105091 680 70414492 681 70724802 682 71036022 683 71348154 684 71661199 685 71975158 686 72290033 687 72605825 688 72922535 689 73240165 690 73558716 691 73878189 692 74198586 693 74519908 694 74842156 695 75165332 696 75489437 697 75814472 698 76140439 699 76467339 700 76795173 701 77123943 702 77453650 703 77784295 704 78115880 705 78448406 706 78781874 707 79116286 708 79451643 709 79787946 710 80125197 711 80463397 712 80802547 713 81142649 714 81483704 715 81825713 716 82168678 717 82512600 718 82857480 719 83203320 720 83550121 721 83897884 722 84246611 723 84596303 724 84946961 725 85298587 726 85651182 727 86004747 728 86359284 729 86714794 730 87071278 731 87428738 732 87787175 733 88146590 734 88506985 735 88868361 736 89230719 737 89594061 738 89958388 739 90323701 740 90690002 741 91057292 742 91425572 743 91794844 744 92165109 745 92536368 746 92908623 747 93281875 748 93656125 749 94031375 750 94407626 751 94784879 752 95163136 753 95542398 754 95922666 755 96303942 756 96686227 757 97069522 758 97453829 759 97839149 760 98225483 761 98612833 762 99001200 763 99390585 764 99780990 765 100172416 766 100564864 767 100958336 768 101352833 769 101748356 770 102144907 771 102542487 772 102941097 773 103340739 774 103741414 775 104143123 776 104545868 777 104949650 778 105354470 779 105760330 780 106167231 781 106575174 782 106984161 783 107394193 784 107805271 785 108217397 786 108630572 787 109044797 788 109460074 789 109876404 790 110293788 791 110712228 792 111131725 793 111552280 794 111973895 795 112396571 796 112820309 797 113245111 798 113670978 799 114097911 800 114525912 801 114954982 802 115385122 803 115816334 804 116248619 805 116681978 806 117116413 807 117551925 808 117988515 809 118426185 810 118864936 811 119304769 812 119745686 813 120187688 814 120630776 815 121074952 816 121520217 817 121966572 818 122414019 819 122862559 820 123312193 821 123762923 822 124214750 823 124667675 824 125121700 825 125576826 826 126033054 827 126490386 828 126948823 829 127408366 830 127869017 831 128330777 832 128793647 833 129257629 834 129722724 835 130188933 836 130656258 837 131124700 838 131594260 839 132064940 840 132536741 841 133009664 842 133483711 843 133958883 844 134435181 845 134912607 846 135391162 847 135870847 848 136351664 849 136833614 850 137316698 851 137800918 852 138286275 853 138772770 854 139260405 855 139749181 856 140239099 857 140730161 858 141222368 859 141715721 860 142210222 861 142705872 862 143202672 863 143700624 864 144199729 865 144699988 866 145201403 867 145703975 868 146207705 869 146712595 870 147218646 871 147725859 872 148234236 873 148743778 874 149254486 875 149766362 876 150279407 877 150793622 878 151309009 879 151825569 880 152343303 881 152862213 882 153382300 883 153903565 884 154426010 885 154949636 886 155474444 887 156000436 888 156527613 889 157055976 890 157585527 891 158116267 892 158648197 893 159181319 894 159715634 895 160251143 896 160787848 897 161325750 898 161864850 899 162405150 900 162946651 901 163489354 902 164033261 903 164578373 904 165124691 905 165672217 906 166220952 907 166770897 908 167322054 909 167874424 910 168428008 911 168982808 912 169538825 913 170096060 914 170654515 915 171214191 916 171775089 917 172337211 918 172900558 919 173465131 920 174030932 921 174597962 922 175166222 923 175735714 924 176306439 925 176878398 926 177451593 927 178026025 928 178601695 929 179178605 930 179756756 931 180336149 932 180916786 933 181498668 934 182081796 935 182666172 936 183251797 937 183838672 938 184426799 939 185016179 940 185606813 941 186198703 942 186791850 943 187386255 944 187981920 945 188578846 946 189177034 947 189776486 948 190377203 949 190979186 950 191582437 951 192186957 952 192792747 953 193399809 954 194008144 955 194617753 956 195228638 957 195840800 958 196454240 959 197068960 960 197684961 961 198302244 962 198920811 963 199540663 964 200161801 965 200784227 966 201407942 967 202032947 968 202659244 969 203286834 970 203915718 971 204545898 972 205177375 973 205810150 974 206444225 975 207079601 976 207716279 977 208354261 978 208993548 979 209634141 980 210276042 981 210919252 982 211563772 983 212209604 984 212856749 985 213505208 986 214154983 987 214806075 988 215458485 989 216112215 990 216767266 991 217423639 992 218081336 993 218740358 994 219400706 995 220062382 996 220725387 997 221389722 998 222055389 999 222722389 1000 223390723