0 1 1 4 2 9 3 18 4 32 5 48 6 67 7 92 8 120 9 150 10 187 11 231 12 275 13 320 14 374 15 433 16 490 17 551 18 620 19 692 20 765 21 841 22 923 23 1011 24 1099 25 1188 26 1286 27 1389 28 1490 29 1595 30 1712 31 1837 32 1956 33 2073 34 2206 35 2344 36 2473 37 2609 38 2757 39 2905 40 3053 41 3204 42 3362 43 3529 44 3692 45 3853 46 4030 47 4212 48 4385 49 4565 50 4763 51 4968 52 5162 53 5352 54 5563 55 5780 56 5982 57 6192 58 6419 59 6644 60 6866 61 7092 62 7327 63 7572 64 7810 65 8044 66 8299 67 8560 68 8806 69 9060 70 9339 71 9625 72 9893 73 10156 74 10446 75 10741 76 11016 77 11301 78 11606 79 11908 80 12205 81 12505 82 12817 83 13141 84 13453 85 13760 86 14094 87 14433 88 14752 89 15081 90 15440 91 15807 92 16150 93 16485 94 16854 95 17228 96 17575 97 17935 98 18319 99 18697 100 19069 101 19444 102 19832 103 20235 104 20622 105 21001 106 21414 107 21832 108 22223 109 22627 110 23067 111 23514 112 23932 113 24340 114 24787 115 25240 116 25660 117 26094 118 26557 119 27012 120 27458 121 27908 122 28373 123 28854 124 29316 125 29768 126 30259 127 30756 128 31220 129 31698 130 32219 131 32747 132 33239 133 33720 134 34246 135 34777 136 35270 137 35779 138 36320 139 36852 140 37373 141 37897 142 38439 143 38999 144 39535 145 40060 146 40630 147 41205 148 41742 149 42295 150 42896 151 43505 152 44072 153 44625 154 45230 155 45840 156 46405 157 46989 158 47609 159 48217 160 48813 161 49412 162 50030 163 50669 164 51280 165 51877 166 52526 167 53180 168 53789 169 54417 170 55099 171 55788 172 56430 173 57056 174 57739 175 58428 176 59066 177 59724 178 60423 179 61108 180 61778 181 62452 182 63147 183 63864 184 64550 185 65220 186 65947 187 66680 188 67362 189 68064 190 68827 191 69597 192 70313 193 71012 194 71774 195 72541 196 73252 197 73985 198 74762 199 75524 200 76269 201 77017 202 77789 203 78585 204 79345 205 80088 206 80894 207 81705 208 82460 209 83237 210 84080 211 84931 212 85722 213 86493 214 87334 215 88180 216 88963 217 89771 218 90627 219 91465 220 92285 221 93108 222 93956 223 94831 224 95666 225 96481 226 97366 227 98256 228 99083 229 99935 230 100859 231 101790 232 102656 233 103500 234 104419 235 105344 236 106200 237 107082 238 108017 239 108932 240 109826 241 110724 242 111649 243 112602 244 113512 245 114400 246 115363 247 116332 248 117232 249 118158 250 119163 251 120175 252 121115 253 122032 254 123030 255 124033 256 124962 257 125919 258 126932 259 127924 260 128893 261 129865 262 130867 263 131899 264 132883 265 133844 266 134886 267 135933 268 136906 269 137907 270 138992 271 140085 272 141100 273 142089 274 143166 275 144248 276 145249 277 146281 278 147373 279 148441 280 149485 281 150532 282 151610 283 152721 284 153780 285 154813 286 155934 287 157060 288 158105 289 159181 290 160347 291 161520 292 162610 293 163672 294 164827 295 165988 296 167062 297 168168 298 169339 299 170484 300 171602 301 172724 302 173879 303 175068 304 176202 305 177308 306 178507 307 179712 308 180830 309 181980 310 183227 311 184481 312 185645 313 186780 314 188014 315 189253 316 190400 317 191581 318 192830 319 194052 320 195245 321 196441 322 197673 323 198941 324 200149 325 201328 326 202606 327 203889 328 205080 329 206305 330 207632 331 208967 332 210206 333 211413 334 212726 335 214044 336 215263 337 216519 338 217847 339 219145 340 220413 341 221684 342 222992 343 224339 344 225622 345 226873 346 228230 347 229592 348 230855 349 232155 350 233563 351 234978 352 236292 353 237572 354 238963 355 240360 356 241652 357 242982 358 244389 359 245764 360 247106 361 248452 362 249837 363 251262 364 252620 365 253944 366 255379 367 256820 368 258156 369 259530 370 261019 371 262515 372 263903 373 265256 374 266726 375 268201 376 269566 377 270971 378 272456 379 273908 380 275325 381 276745 382 278207 383 279711 384 281143 385 282540 386 284054 387 285573 388 286982 389 288431 390 290000 391 291577 392 293040 393 294465 394 296014 395 297568 396 299005 397 300485 398 302049 399 303577 400 305069 401 306564 402 308102 403 309685 404 311192 405 312661 406 314254 407 315852 408 317333 409 318857 410 320507 411 322164 412 323702 413 325200 414 326827 415 328460 416 329970 417 331524 418 333167 419 334772 420 336338 421 337908 422 339523 423 341184 424 342766 425 344308 426 345979 427 347656 428 349210 429 350808 430 352539 431 354277 432 355889 433 357460 434 359166 435 360877 436 362460 437 364089 438 365810 439 367492 440 369133 441 370777 442 372469 443 374209 444 375865 445 377480 446 379230 447 380985 448 382612 449 384285 450 386096 451 387915 452 389602 453 391245 454 393030 455 394820 456 396475 457 398179 458 399979 459 401737 460 403453 461 405172 462 406940 463 408759 464 410490 465 412177 466 414006 467 415840 468 417539 469 419287 470 421179 471 423078 472 424840 473 426556 474 428419 475 430288 476 432016 477 433794 478 435673 479 437508 480 439298 481 441092 482 442937 483 444834 484 446640 485 448400 486 450307 487 452220 488 453992 489 455814 490 457787 491 459767 492 461603 493 463392 494 465334 495 467281 496 469082 497 470935 498 472892 499 474804 500 476669 501 478537 502 480459 503 482435 504 484315 505 486148 506 488134 507 490125 508 491970 509 493867 510 495920 511 497981 512 499892 513 501753 514 503774 515 505800 516 507673 517 509601 518 511637 519 513625 520 515565 521 517508 522 519506 523 521561 524 523516 525 525421 526 527486 527 529556 528 531473 529 533445 530 535579 531 537720 532 539706 533 541640 534 543739 535 545844 536 547790 537 549792 538 551907 539 553972 540 555986 541 558004 542 560079 543 562212 544 564242 545 566220 546 568363 547 570512 548 572502 549 574548 550 576763 551 578985 552 581045 553 583052 554 585230 555 587413 556 589432 557 591509 558 593702 559 595844 560 597933 561 600025 562 602177 563 604389 564 606493 565 608544 566 610766 567 612993 568 615056 569 617177 570 619472 571 621775 572 623910 573 625989 574 628246 575 630508 576 632599 577 634751 578 637023 579 639241 580 641405 581 643572 582 645800 583 648091 584 650270 585 652393 586 654694 587 657000 588 659135 589 661331 590 663707 591 666090 592 668300 593 670452 594 672787 595 675128 596 677292 597 679518 598 681869 599 684164 600 686402 601 688644 602 690949 603 693318 604 695572 605 697768 606 700147 607 702532 608 704740 609 707010 610 709467 611 711931 612 714215 613 716440 614 718854 615 721273 616 723510 617 725811 618 728240 619 730612 620 732925 621 735241 622 737623 623 740071 624 742399 625 744668 626 747126 627 749589 628 751870 629 754215 630 756752 631 759297 632 761656 633 763953 634 766446 635 768944 636 771253 637 773629 638 776137 639 778585 640 780973 641 783364 642 785822 643 788349 644 790752 645 793093 646 795630 647 798172 648 800525 649 802945 650 805563 651 808188 652 810622 653 812992 654 815563 655 818140 656 820522 657 822972 658 825559 659 828084 660 830546 661 833012 662 835547 663 838152 664 840630 665 843044 666 845659 667 848280 668 850706 669 853200 670 855899 671 858605 672 861113 673 863556 674 866206 675 868861 676 871316 677 873841 678 876506 679 879108 680 881645 681 884185 682 886797 683 889481 684 892033 685 894520 686 897214 687 899913 688 902412 689 904981 690 907760 691 910547 692 913130 693 915645 694 918374 695 921108 696 923635 697 926235 698 928979 699 931657 700 934269 701 936884 702 939572 703 942335 704 944962 705 947521 706 950294 707 953072 708 955643 709 958287 710 961147 711 964014 712 966672 713 969260 714 972067 715 974880 716 977480 717 980154 718 982977 719 985732 720 988418 721 991108 722 993873 723 996714 724 999416 725 1002048 726 1004899 727 1007756 728 1010400 729 1013118 730 1016059 731 1019007 732 1021739 733 1024400 734 1027286 735 1030177 736 1032850 737 1035599 738 1038500 739 1041332 740 1044093 741 1046857 742 1049699 743 1052619 744 1055395 745 1058100 746 1061030 747 1063965 748 1066682 749 1069475 750 1072496 751 1075525 752 1078332 753 1081065 754 1084030 755 1087000 756 1089745 757 1092569 758 1095549 759 1098457 760 1101293 761 1104132 762 1107050 763 1110049 764 1112900 765 1115677 766 1118686 767 1121700 768 1124489 769 1127357 770 1130459 771 1133568 772 1136450 773 1139256 774 1142299 775 1145348 776 1148166 777 1151064 778 1154123 779 1157108 780 1160018 781 1162932 782 1165927 783 1169004 784 1171930 785 1174780 786 1177867 787 1180960 788 1183822 789 1186764 790 1189947 791 1193137 792 1196093 793 1198972 794 1202094 795 1205221 796 1208112 797 1211085 798 1214222 799 1217284 800 1220269 801 1223257 802 1226329 803 1229485 804 1232485 805 1235408 806 1238574 807 1241745 808 1244680 809 1247697 810 1250960 811 1254231 812 1257262 813 1260213 814 1263414 815 1266620 816 1269583 817 1272631 818 1275847 819 1278985 820 1282045 821 1285108 822 1288256 823 1291491 824 1294566 825 1297561 826 1300806 827 1304056 828 1307063 829 1310155 830 1313499 831 1316850 832 1319956 833 1322980 834 1326259 835 1329544 836 1332580 837 1335702 838 1338997 839 1342212 840 1345346 841 1348484 842 1351709 843 1355022 844 1358172 845 1361240 846 1364563 847 1367892 848 1370972 849 1374138 850 1377563 851 1380995 852 1384175 853 1387272 854 1390630 855 1393993 856 1397102 857 1400299 858 1403672 859 1406964 860 1410173 861 1413385 862 1416687 863 1420079 864 1423303 865 1426444 866 1429846 867 1433253 868 1436406 869 1439647 870 1443152 871 1446665 872 1449920 873 1453089 874 1456526 875 1459968 876 1463149 877 1466421 878 1469873 879 1473241 880 1476525 881 1479812 882 1483190 883 1486661 884 1489960 885 1493173 886 1496654 887 1500140 888 1503365 889 1506681 890 1510267 891 1513860 892 1517190 893 1520432 894 1523947 895 1527468 896 1530722 897 1534068 898 1537599 899 1541044 900 1544402 901 1547764 902 1551219 903 1554768 904 1558142 905 1561428 906 1564987 907 1568552 908 1571850 909 1575240 910 1578907 911 1582581 912 1585985 913 1589300 914 1592894 915 1596493 916 1599820 917 1603241 918 1606850 919 1610372 920 1613805 921 1617241 922 1620773 923 1624401 924 1627849 925 1631208 926 1634846 927 1638489 928 1641860 929 1645325 930 1649072 931 1652827 932 1656306 933 1659693 934 1663366 935 1667044 936 1670443 937 1673939 938 1677627 939 1681225 940 1684733 941 1688244 942 1691852 943 1695559 944 1699082 945 1702513 946 1706230 947 1709952 948 1713395 949 1716935 950 1720763 951 1724598 952 1728152 953 1731612 954 1735363 955 1739120 956 1742592 957 1746162 958 1749929 959 1753604 960 1757186 961 1760772 962 1764457 963 1768242 964 1771840 965 1775344 966 1779139 967 1782940 968 1786456 969 1790070 970 1793979 971 1797895 972 1801523 973 1805056 974 1808886 975 1812721 976 1816266 977 1819911 978 1823756 979 1827508 980 1831165 981 1834825 982 1838587 983 1842451 984 1846123 985 1849700 986 1853574 987 1857453 988 1861042 989 1864731 990 1868720 991 1872717 992 1876420 993 1880025 994 1883934 995 1887848 996 1891465 997 1895185 998 1899109 999 1902937 1000 1906669