0 1 1 4 2 12 3 24 4 42 5 64 6 90 7 131 8 168 9 206 10 259 11 313 12 383 13 441 14 506 15 583 16 656 17 766 18 841 19 933 20 1034 21 1139 22 1279 23 1376 24 1496 25 1617 26 1744 27 1911 28 2041 29 2179 30 2329 31 2494 32 2686 33 2837 34 2988 35 3178 36 3352 37 3588 38 3768 39 3926 40 4152 41 4344 42 4630 43 4822 44 5010 45 5262 46 5458 47 5795 48 5990 49 6218 50 6489 51 6725 52 7103 53 7303 54 7562 55 7835 56 8112 57 8516 58 8751 59 9033 60 9318 61 9643 62 10057 63 10338 64 10626 65 10947 66 11290 67 11731 68 12051 69 12319 70 12705 71 13068 72 13560 73 13905 74 14172 75 14594 76 14936 77 15512 78 15860 79 16158 80 16618 81 16970 82 17604 83 17934 84 18290 85 18750 86 19134 87 19819 88 20148 89 20536 90 20985 91 21453 92 22155 93 22521 94 22932 95 23375 96 23876 97 24582 98 25021 99 25413 100 25914 101 26459 102 27175 103 27660 104 28018 105 28587 106 29116 107 29911 108 30423 109 30757 110 31389 111 31900 112 32794 113 33297 114 33672 115 34328 116 34816 117 35790 118 36258 119 36700 120 37360 121 37918 122 38940 123 39390 124 39878 125 40492 126 41122 127 42169 128 42674 129 43166 130 43781 131 44487 132 45509 133 46103 134 46574 135 47235 136 47954 137 48996 138 49647 139 50049 140 50822 141 51543 142 52665 143 53342 144 53714 145 54539 146 55192 147 56449 148 57111 149 57519 150 58387 151 59042 152 60384 153 60983 154 61484 155 62326 156 63024 157 64434 158 65012 159 65548 160 66348 161 67176 162 68588 163 69228 164 69780 165 70542 166 71418 167 72809 168 73560 169 74062 170 74909 171 75833 172 77223 173 78039 174 78458 175 79411 176 80292 177 81790 178 82635 179 82997 180 84038 181 84871 182 86515 183 87328 184 87746 185 88803 186 89584 187 91347 188 92085 189 92591 190 93641 191 94520 192 96336 193 97039 194 97604 195 98558 196 99544 197 101378 198 102154 199 102714 200 103656 201 104740 202 106518 203 107424 204 107934 205 108938 206 110028 207 111817 208 112802 209 113188 210 114349 211 115433 212 117329 213 118335 214 118666 215 119893 216 120860 217 122948 218 123919 219 124289 220 125568 221 126523 222 128721 223 129594 224 130090 225 131311 226 132324 227 134605 228 135435 229 135975 230 137121 231 138308 232 140580 233 141491 234 142038 235 143124 236 144372 237 146592 238 147656 239 148120 240 149316 241 150622 242 152828 243 153974 244 154310 245 155644 246 156878 247 159231 248 160406 249 160646 250 162097 251 163251 252 165795 253 166921 254 167230 255 168687 256 169764 257 172460 258 173469 259 173897 260 175334 261 176531 262 179289 263 180244 264 180742 265 182039 266 183376 267 186143 268 187193 269 187671 270 188941 271 190408 272 193086 273 194301 274 194704 275 196050 276 197514 277 200200 278 201514 279 201736 280 203288 281 204732 282 207550 283 208890 284 209030 285 210656 286 211938 287 215003 288 216286 289 216474 290 218159 291 219413 292 222617 293 223761 294 224106 295 225711 296 227036 297 230332 298 231415 299 231811 300 233306 301 234855 302 238129 303 239310 304 239708 305 241115 306 242736 307 245937 308 247311 309 247587 310 249133 311 250820 312 253992 313 255471 314 255572 315 257286 316 258876 317 262228 318 263734 319 263710 320 265568 321 267040 322 270632 323 272070 324 272126 325 273986 326 275354 327 279129 328 280412 329 280612 330 282437 331 283957 332 287801 333 289005 334 289290 335 290929 336 292620 337 296470 338 297789 339 298037 340 299638 341 301485 342 305211 343 306740 344 306886 345 308571 346 310410 347 314139 348 315785 349 315699 350 317637 351 319440 352 323330 353 325001 354 324804 355 326834 356 328428 357 332614 358 334210 359 334068 360 336162 361 337718 362 342070 363 343484 364 343534 365 345520 366 347158 367 351621 368 352954 369 353056 370 354901 371 356811 372 361237 373 362691 374 362788 375 364515 376 366512 377 370838 378 372523 379 372469 380 374362 381 376427 382 380713 383 382524 384 382246 385 384343 386 386284 387 390781 388 392621 389 392183 390 394449 391 396244 392 401028 393 402775 394 402432 395 404694 396 406356 397 411360 398 412912 399 412736 400 414952 401 416792 402 421870 403 423328 404 423250 405 425228 406 427274 407 432353 408 433944 409 433818 410 435745 411 437971 412 442895 413 444735 414 444478 415 446507 416 448718 417 453634 418 455613 419 455071 420 457398 421 459563 422 464667 423 466668 424 465990 425 468421 426 470328 427 475787 428 477693 429 477071 430 479575 431 481432 432 487082 433 488769 434 488372 435 490738 436 492692 437 498466 438 500050 439 499716 440 501908 441 504176 442 509902 443 511628 444 511280 445 513330 446 515698 447 521295 448 523294 449 522760 450 525001 451 527449 452 532993 453 535133 454 534330 455 536809 456 539104 457 544896 458 547065 459 546065 460 548742 461 550857 462 556981 463 559042 464 558150 465 560811 466 562768 467 569147 468 570971 469 570275 470 572877 471 575036 472 581498 473 583207 474 582620 475 584942 476 587340 477 593792 478 595656 479 595008 480 597264 481 599872 482 606136 483 608286 484 607482 485 609852 486 612436 487 618691 488 621000 489 619852 490 622569 491 625095 492 631563 493 633897 494 632586 495 635417 496 637640 497 644516 498 646733 499 645489 500 648400 501 650555 502 657651 503 659610 504 658622 505 661371 506 663636 507 670867 508 672705 509 671785 510 674325 511 676956 512 684126 513 686121 514 685182 515 687554 516 690296 517 697314 518 699622 519 698460 520 701052 521 703880 522 710830 523 713304 524 711826 525 714684 526 717334 527 724567 528 727068 529 725362 530 728445 531 730879 532 738493 533 740865 534 739278 535 742343 536 744592 537 752490 538 754587 539 753223 540 756214 541 758695 542 766683 543 768642 544 767402 545 770065 546 772816 547 780793 548 782927 549 781607 550 784193 551 787182 552 794936 553 797399 554 795896 555 798606 556 801566 557 809304 558 811944 559 810048 560 813152 561 816036 562 824016 563 826682 564 824594 565 827828 566 830362 567 838801 568 841332 569 839316 570 842635 571 845093 572 853779 573 856007 574 854282 575 857413 576 859992 577 868830 578 870917 579 869263 580 872154 581 875145 582 883907 583 886176 584 884496 585 887187 586 890304 587 898889 588 901509 589 899575 590 902513 591 905720 592 914226 593 917031 594 914732 595 917974 596 920976 597 929794 598 932628 599 930068 600 933560 601 936316 602 945562 603 948244 604 945818 605 949284 606 951826 607 961395 608 963762 609 961580 610 964961 611 967763 612 977427 613 979639 614 977594 615 980597 616 983704 617 993350 618 995755 619 993621 620 996534 621 999901 622 1009293 623 1012068 624 1009722 625 1012775 626 1016106 627 1025473 628 1028447 629 1025653 630 1029145 631 1032392 632 1042028 633 1045023 634 1042012 635 1045648 636 1048496 637 1058648 638 1061488 639 1058552 640 1062282 641 1065040 642 1075464 643 1077966 644 1075354 645 1078864 646 1081758 647 1092349 648 1094688 649 1092156 650 1095393 651 1098743 652 1109247 653 1111787 654 1109220 655 1112235 656 1115724 657 1126020 658 1128953 659 1126099 660 1129386 661 1132975 662 1143179 663 1146314 664 1143050 665 1146673 666 1150028 667 1160583 668 1163747 669 1160183 670 1164085 671 1167162 672 1178190 673 1181185 674 1177768 675 1181634 676 1184472 677 1195856 678 1198494 679 1195352 680 1199120 681 1202240 682 1213728 683 1216192 684 1213198 685 1216544 686 1220002 687 1231463 688 1234142 689 1231044 690 1234285 691 1238035 692 1249209 693 1252293 694 1248958 695 1252353 696 1256058 697 1267204 698 1270507 699 1266667 700 1270550 701 1274157 702 1285597 703 1288926 704 1284842 705 1288877 706 1292040 707 1304051 708 1307203 709 1303203 710 1307339 711 1310396 712 1322708 713 1325481 714 1321836 715 1325730 716 1328936 717 1341424 718 1344016 719 1340458 720 1344044 721 1347756 722 1360144 723 1362954 724 1359356 725 1362692 726 1366554 727 1378713 728 1381956 729 1378032 730 1381669 731 1385639 732 1397691 733 1401159 734 1396778 735 1400781 736 1404492 737 1416928 738 1420423 739 1415713 740 1420022 741 1423417 742 1436375 743 1439682 744 1435130 745 1439399 746 1442528 747 1455873 748 1458785 749 1454533 750 1458689 751 1462132 752 1475588 753 1478301 754 1474212 755 1477900 756 1481712 757 1495138 758 1498086 759 1493876 760 1497448 761 1501578 762 1514682 763 1518080 764 1513606 765 1517340 766 1521420 767 1534491 768 1538126 769 1533096 770 1537365 771 1541331 772 1554725 773 1558385 774 1553082 775 1557521 776 1560996 777 1575010 778 1578475 779 1573263 780 1577808 781 1581167 782 1595509 783 1598552 784 1593730 785 1598005 786 1601524 787 1616061 788 1618903 789 1614169 790 1618105 791 1622178 792 1636600 793 1639683 794 1634902 795 1638558 796 1642796 797 1656962 798 1660516 799 1655380 800 1659364 801 1663712 802 1677760 803 1681560 804 1675918 805 1680304 806 1684366 807 1698829 808 1702658 809 1696652 810 1701369 811 1705087 812 1720119 813 1723735 814 1717902 815 1722573 816 1725996 817 1741452 818 1744633 819 1739123 820 1743670 821 1747433 822 1763005 823 1765972 824 1760638 825 1764665 826 1768832 827 1784369 828 1787589 829 1782123 830 1786021 831 1790530 832 1805714 833 1809423 834 1803664 835 1807742 836 1812194 837 1827334 838 1831302 839 1824934 840 1829592 841 1833920 842 1849410 843 1853400 844 1846734 845 1851574 846 1855362 847 1871531 848 1875306 849 1868732 850 1873687 851 1877347 852 1893869 853 1897185 854 1891034 855 1895689 856 1899524 857 1916254 858 1919347 859 1913295 860 1917578 861 1922009 862 1938613 863 1941968 864 1935860 865 1939839 866 1944448 867 1960767 868 1964635 869 1958137 870 1962469 871 1967200 872 1983388 873 1987517 874 1980468 875 1985236 876 1989652 877 2006292 878 2010450 879 2003000 880 2008128 881 2012166 882 2029420 883 2033350 884 2026086 885 2031156 886 2034874 887 2052587 888 2056040 889 2049128 890 2054061 891 2058143 892 2075981 893 2079199 894 2072474 895 2076845 896 2081364 897 2099156 898 2102649 899 2095779 900 2100006 901 2104897 902 2122303 903 2126322 904 2119134 905 2123553 906 2128378 907 2145739 908 2150037 909 2142181 910 2147229 911 2151918 912 2169654 913 2173977 914 2165796 915 2171036 916 2175140 917 2193608 918 2197694 919 2189616 920 2194978 921 2198936 922 2217786 923 2221374 924 2213750 925 2218788 926 2222934 927 2242003 928 2245350 929 2237830 930 2242461 931 2247255 932 2266185 933 2269809 934 2262228 935 2266529 936 2271512 937 2290134 938 2294311 939 2286303 940 2290986 941 2296097 942 2314573 943 2319036 944 2310430 945 2315577 946 2320348 947 2339311 948 2343801 949 2334763 950 2340297 951 2344654 952 2364280 953 2368521 954 2359680 955 2365154 956 2369164 957 2389278 958 2393004 959 2384542 960 2389864 961 2394268 962 2414514 963 2417982 964 2409722 965 2414434 966 2419306 967 2439505 968 2443268 969 2434844 970 2439401 971 2444673 972 2464451 973 2468783 974 2460014 975 2464773 976 2469974 977 2489700 978 2494329 979 2484843 980 2490278 981 2495325 982 2515455 983 2520110 984 2510270 985 2515913 986 2520328 987 2541241 988 2545641 989 2535909 990 2541679 991 2545940 992 2567262 993 2571119 994 2561876 995 2567296 996 2571756 997 2593314 998 2596910 999 2587774 1000 2592756