0 1 1 4 2 12 3 17 4 30 5 48 6 72 7 99 8 128 9 160 10 199 11 246 12 295 13 339 14 396 15 461 16 518 17 589 18 669 19 734 20 832 21 911 22 988 23 1090 24 1192 25 1287 26 1398 27 1502 28 1625 29 1754 30 1851 31 1991 32 2112 33 2262 34 2410 35 2527 36 2700 37 2844 38 2994 39 3172 40 3299 41 3502 42 3658 43 3838 44 4045 45 4187 46 4414 47 4583 48 4767 49 5013 50 5186 51 5404 52 5627 53 5837 54 6078 55 6279 56 6518 57 6754 58 6990 59 7245 60 7500 61 7730 62 7993 63 8271 64 8507 65 8784 66 9059 67 9337 68 9626 69 9906 70 10204 71 10483 72 10775 73 11099 74 11380 75 11708 76 12022 77 12337 78 12671 79 12985 80 13323 81 13643 82 13979 83 14344 84 14696 85 15031 86 15400 87 15744 88 16116 89 16500 90 16844 91 17233 92 17625 93 17997 94 18414 95 18781 96 19172 97 19592 98 19978 99 20413 100 20811 101 21236 102 21662 103 22081 104 22523 105 22954 106 23386 107 23822 108 24288 109 24750 110 25183 111 25657 112 26110 113 26583 114 27069 115 27522 116 28011 117 28495 118 29005 119 29489 120 29972 121 30486 122 30985 123 31501 124 32019 125 32530 126 33064 127 33573 128 34122 129 34657 130 35175 131 35744 132 36270 133 36825 134 37410 135 37945 136 38509 137 39083 138 39647 139 40246 140 40812 141 41400 142 41984 143 42577 144 43193 145 43783 146 44382 147 44993 148 45624 149 46235 150 46847 151 47488 152 48102 153 48748 154 49401 155 50020 156 50685 157 51331 158 51985 159 52650 160 53312 161 53982 162 54653 163 55329 164 56019 165 56707 166 57376 167 58075 168 58780 169 59483 170 60192 171 60890 172 61608 173 62343 174 63055 175 63784 176 64501 177 65248 178 65984 179 66736 180 67490 181 68220 182 68993 183 69748 184 70503 185 71280 186 72052 187 72822 188 73621 189 74400 190 75192 191 75979 192 76762 193 77587 194 78391 195 79178 196 80038 197 80822 198 81646 199 82505 200 83280 201 84154 202 84978 203 85828 204 86701 205 87509 206 88404 207 89247 208 90092 209 91001 210 91832 211 92735 212 93614 213 94493 214 95407 215 96266 216 97182 217 98072 218 98971 219 99912 220 100810 221 101723 222 102662 223 103573 224 104515 225 105452 226 106365 227 107327 228 108288 229 109229 230 110200 231 111134 232 112108 233 113091 234 114034 235 115037 236 116004 237 116993 238 118004 239 118976 240 119972 241 120981 242 121978 243 122996 244 124011 245 125038 246 126055 247 127070 248 128118 249 129150 250 130179 251 131224 252 132268 253 133337 254 134398 255 135437 256 136511 257 137564 258 138661 259 139739 260 140796 261 141903 262 142982 263 144079 264 145192 265 146268 266 147385 267 148494 268 149608 269 150736 270 151847 271 152985 272 154101 273 155247 274 156397 275 157522 276 158679 277 159831 278 160978 279 162159 280 163303 281 164486 282 165645 283 166817 284 168040 285 169182 286 170376 287 171590 288 172765 289 173989 290 175187 291 176385 292 177618 293 178823 294 180068 295 181273 296 182501 297 183751 298 184983 299 186235 300 187482 301 188735 302 189973 303 191244 304 192519 305 193780 306 195047 307 196325 308 197619 309 198905 310 200187 311 201478 312 202758 313 204093 314 205386 315 206695 316 208025 317 209313 318 210672 319 211975 320 213297 321 214656 322 215972 323 217338 324 218686 325 220021 326 221402 327 222736 328 224104 329 225489 330 226852 331 228226 332 229620 333 231000 334 232388 335 233789 336 235166 337 236575 338 237983 339 239408 340 240816 341 242223 342 243660 343 245086 344 246511 345 247945 346 249381 347 250831 348 252278 349 253749 350 255186 351 256642 352 258119 353 259570 354 261052 355 262528 356 264022 357 265494 358 266993 359 268491 360 269967 361 271491 362 272976 363 274492 364 276032 365 277524 366 279073 367 280570 368 282106 369 283674 370 285164 371 286732 372 288286 373 289828 374 291408 375 292945 376 294504 377 296087 378 297654 379 299239 380 300808 381 302398 382 303995 383 305587 384 307183 385 308785 386 310385 387 311990 388 313619 389 315241 390 316858 391 318479 392 320116 393 321749 394 323396 395 325031 396 326676 397 328333 398 330002 399 331651 400 333320 401 334986 402 336643 403 338346 404 340016 405 341696 406 343396 407 345080 408 346787 409 348490 410 350182 411 351912 412 353603 413 355343 414 357072 415 358775 416 360517 417 362253 418 363993 419 365736 420 367493 421 369234 422 370977 423 372762 424 374526 425 376277 426 378060 427 379829 428 381631 429 383408 430 385190 431 386990 432 388773 433 390589 434 392411 435 394194 436 396020 437 397845 438 399647 439 401498 440 403315 441 405154 442 406994 443 408828 444 410707 445 412540 446 414388 447 416259 448 418103 449 420009 450 421857 451 423731 452 425631 453 427497 454 429420 455 431279 456 433175 457 435094 458 436987 459 438921 460 440823 461 442731 462 444674 463 446593 464 448514 465 450455 466 452399 467 454330 468 456303 469 458248 470 460198 471 462164 472 464100 473 466102 474 468057 475 470041 476 472042 477 473989 478 476011 479 478001 480 479978 481 481998 482 483981 483 486020 484 488030 485 490045 486 492079 487 494079 488 496128 489 498164 490 500186 491 502247 492 504294 493 506342 494 508415 495 510454 496 512525 497 514593 498 516660 499 518750 500 520828 501 522912 502 525013 503 527086 504 529199 505 531302 506 533384 507 535508 508 537631 509 539758 510 541867 511 543998 512 546124 513 548264 514 550408 515 552543 516 554691 517 556848 518 559013 519 561173 520 563318 521 565502 522 567669 523 569836 524 572040 525 574216 526 576409 527 578591 528 580800 529 583005 530 585196 531 587418 532 589628 533 591847 534 594090 535 596293 536 598527 537 600769 538 603002 539 605263 540 607491 541 609745 542 612011 543 614270 544 616538 545 618798 546 621066 547 623360 548 625634 549 627922 550 630206 551 632502 552 634796 553 637109 554 639418 555 641707 556 644047 557 646347 558 648669 559 651014 560 653333 561 655670 562 658000 563 660354 564 662720 565 665047 566 667413 567 669763 568 672138 569 674513 570 676879 571 679256 572 681623 573 684042 574 686414 575 688794 576 691207 577 693598 578 696019 579 698427 580 700841 581 703262 582 705672 583 708118 584 710533 585 712975 586 715415 587 717853 588 720316 589 722763 590 725223 591 727667 592 730122 593 732619 594 735087 595 737553 596 740053 597 742517 598 745018 599 747530 600 749991 601 752505 602 755022 603 757517 604 760070 605 762553 606 765084 607 767621 608 770117 609 772702 610 775210 611 777754 612 780326 613 782854 614 785435 615 787982 616 790534 617 793119 618 795673 619 798277 620 800846 621 803430 622 806032 623 808607 624 811221 625 813814 626 816408 627 819030 628 821657 629 824264 630 826901 631 829513 632 832139 633 834791 634 837412 635 840071 636 842723 637 845353 638 848052 639 850679 640 853341 641 856039 642 858661 643 861372 644 864062 645 866738 646 869434 647 872104 648 874825 649 877533 650 880209 651 882947 652 885644 653 888372 654 891112 655 893817 656 896553 657 899281 658 902035 659 904775 660 907503 661 910286 662 913031 663 915779 664 918573 665 921311 666 924099 667 926873 668 929650 669 932456 670 935225 671 938028 672 940827 673 943620 674 946439 675 949241 676 952050 677 954877 678 957701 679 960537 680 963358 681 966188 682 969030 683 971883 684 974734 685 977574 686 980430 687 983303 688 986154 689 989036 690 991907 691 994763 692 997673 693 1000547 694 1003435 695 1006335 696 1009218 697 1012137 698 1015034 699 1017944 700 1020881 701 1023773 702 1026701 703 1029638 704 1032565 705 1035495 706 1038444 707 1041380 708 1044335 709 1047297 710 1050234 711 1053200 712 1056151 713 1059145 714 1062117 715 1065072 716 1068079 717 1071047 718 1074044 719 1077050 720 1080014 721 1083050 722 1086028 723 1089061 724 1092089 725 1095070 726 1098132 727 1101118 728 1104161 729 1107229 730 1110229 731 1113289 732 1116339 733 1119389 734 1122466 735 1125500 736 1128566 737 1131632 738 1134717 739 1137802 740 1140876 741 1143955 742 1147053 743 1150150 744 1153228 745 1156344 746 1159444 747 1162555 748 1165684 749 1168803 750 1171920 751 1175042 752 1178172 753 1181311 754 1184446 755 1187603 756 1190744 757 1193896 758 1197059 759 1200217 760 1203379 761 1206538 762 1209711 763 1212896 764 1216097 765 1219263 766 1222459 767 1225641 768 1228845 769 1232065 770 1235240 771 1238465 772 1241688 773 1244895 774 1248146 775 1251346 776 1254572 777 1257828 778 1261045 779 1264304 780 1267553 781 1270809 782 1274059 783 1277316 784 1280589 785 1283861 786 1287119 787 1290395 788 1293692 789 1296975 790 1300266 791 1303564 792 1306843 793 1310155 794 1313474 795 1316767 796 1320081 797 1323407 798 1326741 799 1330059 800 1333388 801 1336725 802 1340055 803 1343412 804 1346768 805 1350102 806 1353474 807 1356821 808 1360198 809 1363568 810 1366919 811 1370324 812 1373682 813 1377076 814 1380488 815 1383847 816 1387265 817 1390664 818 1394060 819 1397497 820 1400890 821 1404318 822 1407731 823 1411169 824 1414603 825 1418026 826 1421479 827 1424909 828 1428372 829 1431818 830 1435266 831 1438741 832 1442188 833 1445673 834 1449152 835 1452604 836 1456112 837 1459585 838 1463071 839 1466577 840 1470067 841 1473565 842 1477080 843 1480588 844 1484108 845 1487629 846 1491133 847 1494673 848 1498201 849 1501746 850 1505283 851 1508812 852 1512377 853 1515933 854 1519484 855 1523044 856 1526591 857 1530181 858 1533745 859 1537336 860 1540915 861 1544481 862 1548101 863 1551669 864 1555268 865 1558888 866 1562479 867 1566085 868 1569723 869 1573336 870 1576955 871 1580577 872 1584198 873 1587853 874 1591492 875 1595124 876 1598800 877 1602414 878 1606097 879 1609775 880 1613379 881 1617092 882 1620748 883 1624436 884 1628134 885 1631789 886 1635504 887 1639176 888 1642882 889 1646604 890 1650272 891 1654008 892 1657720 893 1661443 894 1665175 895 1668878 896 1672627 897 1676345 898 1680085 899 1683852 900 1687586 901 1691340 902 1695102 903 1698851 904 1702634 905 1706393 906 1710149 907 1713942 908 1717727 909 1721516 910 1725314 911 1729087 912 1732884 913 1736699 914 1740497 915 1744309 916 1748126 917 1751948 918 1755778 919 1759599 920 1763424 921 1767274 922 1771087 923 1774945 924 1778813 925 1782647 926 1786505 927 1790368 928 1794231 929 1798103 930 1801974 931 1805847 932 1809723 933 1813621 934 1817525 935 1821398 936 1825295 937 1829199 938 1833115 939 1837019 940 1840936 941 1844855 942 1848775 943 1852707 944 1856647 945 1860571 946 1864506 947 1868460 948 1872401 949 1876359 950 1880321 951 1884275 952 1888233 953 1892212 954 1896184 955 1900162 956 1904141 957 1908125 958 1912116 959 1916123 960 1920105 961 1924114 962 1928113 963 1932129 964 1936162 965 1940147 966 1944191 967 1948215 968 1952238 969 1956294 970 1960312 971 1964362 972 1968421 973 1972467 974 1976534 975 1980568 976 1984657 977 1988716 978 1992787 979 1996881 980 2000944 981 2005050 982 2009114 983 2013219 984 2017322 985 2021415 986 2025538 987 2029627 988 2033758 989 2037891 990 2041991 991 2046124 992 2050239 993 2054399 994 2058537 995 2062671 996 2066833 997 2070964 998 2075146 999 2079296 1000 2083442