0 1 1 3 2 8 3 13 4 29 5 53 6 80 7 113 8 147 9 193 10 231 11 288 12 341 13 411 14 462 15 560 16 605 17 725 18 767 19 902 20 960 21 1106 22 1164 23 1331 24 1395 25 1566 26 1643 27 1824 28 1914 29 2109 30 2193 31 2427 32 2492 33 2747 34 2817 35 3089 36 3156 37 3466 38 3524 39 3852 40 3906 41 4250 42 4317 43 4655 44 4748 45 5110 46 5198 47 5563 48 5681 49 6036 50 6165 51 6527 52 6672 53 7070 54 7186 55 7625 56 7726 57 8192 58 8271 59 8791 60 8847 61 9407 62 9458 63 10018 64 10097 65 10646 66 10749 67 11298 68 11422 69 11983 70 12128 71 12669 72 12837 73 13398 74 13541 75 14148 76 14288 77 14917 78 15057 79 15704 80 15831 81 16529 82 16611 83 17359 84 17440 85 18189 86 18312 87 19045 88 19170 89 19933 90 20063 91 20802 92 21002 93 21713 94 21943 95 22659 96 22857 97 23665 98 23792 99 24636 100 24790 101 25664 102 25771 103 26718 104 26776 105 27765 106 27819 107 28786 108 28943 109 29850 110 30031 111 30968 112 31133 113 32062 114 32289 115 33177 116 33452 117 34351 118 34606 119 35565 120 35749 121 36772 122 36967 123 37986 124 38174 125 39296 126 39386 127 40566 128 40634 129 41842 130 41948 131 43098 132 43286 133 44437 134 44618 135 45746 136 46003 137 47078 138 47369 139 48457 140 48744 141 49911 142 50115 143 51355 144 51528 145 52801 146 52956 147 54282 148 54406 149 55784 150 55914 151 57252 152 57443 153 58756 154 58967 155 60278 156 60537 157 61846 158 62141 159 63395 160 63734 161 64998 162 65293 163 66648 164 66918 165 68314 166 68563 167 70009 168 70166 169 71738 170 71802 171 73449 172 73528 173 75150 174 75328 175 76849 176 77058 177 78609 178 78853 179 80319 180 80713 181 82121 182 82528 183 83943 184 84289 185 85862 186 86083 187 87697 188 88002 189 89607 190 89838 191 91570 192 91701 193 93498 194 93620 195 95396 196 95636 197 97338 198 97602 199 99356 200 99568 201 101309 202 101654 203 103252 204 103705 205 105323 206 105727 207 107445 208 107722 209 109557 210 109806 211 111636 212 111881 213 113872 214 113958 215 116017 216 116115 217 118123 218 118337 219 120221 220 120582 221 122449 222 122795 223 124646 224 125061 225 126835 226 127306 227 129102 228 129538 229 131476 230 131797 231 133784 232 134077 233 136117 234 136366 235 138498 236 138680 237 140927 238 141041 239 143255 240 143467 241 145632 242 145872 243 148026 244 148365 245 150432 246 150882 247 152831 248 153364 249 155313 250 155784 251 157886 252 158258 253 160438 254 160787 255 163021 256 163241 257 165656 258 165774 259 168215 260 168388 261 170782 262 171105 263 173338 264 173700 265 176025 266 176344 267 178587 268 179117 269 181272 270 181808 271 183977 272 184447 273 186781 274 187097 275 189492 276 189920 277 192292 278 192616 279 195192 280 195296 281 198001 282 198099 283 200754 284 201042 285 203556 286 203931 287 206424 288 206768 289 209230 290 209776 291 212018 292 212725 293 215020 294 215576 295 218046 296 218410 297 221055 298 221371 299 224006 300 224359 301 227131 302 227285 303 230164 304 230320 305 233129 306 233444 307 236119 308 236548 309 239243 310 239642 311 242312 312 242798 313 245354 314 245969 315 248454 316 249077 317 251742 318 252207 319 254930 320 255359 321 258185 322 258476 323 261454 324 261660 325 264789 326 264907 327 267974 328 268271 329 271170 330 271555 331 274432 332 274954 333 277711 334 278372 335 281021 336 281684 337 284384 338 284962 339 287864 340 288297 341 291314 342 291755 343 294745 344 295055 345 298283 346 298457 347 301706 348 301964 349 305192 350 305548 351 308606 352 309019 353 312182 354 312548 355 315588 356 316283 357 319101 358 319858 359 322686 360 323362 361 326393 362 326868 363 330024 364 330539 365 333718 366 334088 367 337539 368 337618 369 341231 370 341352 371 344792 372 345206 373 348463 374 348987 375 352211 376 352697 377 355929 378 356567 379 359564 380 360407 381 363467 382 364115 383 367396 384 367855 385 371242 386 371700 387 375064 388 375566 389 379104 390 379351 391 383068 392 383214 393 386891 394 387243 395 390743 396 391238 397 394758 398 395265 399 398639 400 399315 401 402543 402 403379 403 406519 404 407349 405 410779 406 411294 407 414844 408 415313 409 418995 410 419287 411 423161 412 423400 413 427337 414 427529 415 431373 416 431802 417 435427 418 435970 419 439619 420 440216 421 443761 422 444543 423 447938 424 448721 425 452183 426 452914 427 456510 428 457122 429 460853 430 461471 431 465166 432 465610 433 469675 434 469816 435 473973 436 474215 437 478342 438 478703 439 482614 440 483102 441 487020 442 487508 443 491270 444 492180 445 495651 446 496637 447 500179 448 500936 449 504786 450 505302 451 509296 452 509871 453 513879 454 514347 455 518550 456 518721 457 523122 458 523348 459 527524 460 528122 461 532130 462 532728 463 536766 464 537304 465 541356 466 542074 467 545840 468 546868 469 550585 470 551431 471 555426 472 556023 473 560154 474 560749 475 564909 476 565427 477 569867 478 570068 479 574729 480 574804 481 579404 482 579812 483 584037 484 584701 485 588941 486 589629 487 593677 488 594577 489 598500 490 599468 491 603341 492 604307 493 608530 494 609106 495 613480 496 614069 497 618454 498 618899 499 623516 500 623882 501 628591 502 628888 503 633561 504 633992 505 638477 506 639036 507 643553 508 644171 509 648566 510 649468 511 653541 512 654522 513 658667 514 659589 515 663887 516 664663 517 669189 518 669836 519 674376 520 674830 521 679798 522 679899 523 684960 524 685268 525 690132 526 690659 527 695256 528 695947 529 700543 530 701237 531 705720 532 706754 533 710971 534 712088 535 716394 536 717229 537 721912 538 722522 539 727236 540 727977 541 732715 542 733318 543 738292 544 738536 545 743824 546 743978 547 749079 548 749666 549 754563 550 755159 551 760070 552 760686 553 765447 554 766365 555 770774 556 772072 557 776403 558 777497 559 782223 560 782870 561 787828 562 788480 563 793469 564 794027 565 799342 566 799608 567 805014 568 805206 569 810552 570 811125 571 816037 572 816906 573 821919 574 822638 575 827516 576 828475 577 833214 578 834241 579 838930 580 840029 581 844967 582 845689 583 850795 584 851532 585 856647 586 857219 587 862681 588 863009 589 868643 590 868901 591 874479 592 874902 593 880249 594 880913 595 886116 596 886945 597 891995 598 893167 599 897827 600 899088 601 903920 602 904931 603 910033 604 910875 605 916244 606 916924 607 922322 608 922843 609 928578 610 928767 611 934611 612 935035 613 940654 614 941331 615 946729 616 947410 617 952897 618 953580 619 958926 620 960018 621 965042 622 966322 623 971271 624 972314 625 977688 626 978484 627 983877 628 984831 629 990333 630 990955 631 996815 632 997022 633 1003239 634 1003347 635 1009336 636 1010039 637 1015611 638 1016408 639 1022006 640 1022817 641 1028243 642 1029400 643 1034509 644 1035913 645 1041034 646 1042190 647 1047775 648 1048409 649 1054264 650 1054992 651 1060692 652 1061406 653 1067480 654 1067854 655 1074033 656 1074328 657 1080519 658 1081077 659 1086846 660 1087748 661 1093633 662 1094362 663 1100081 664 1101192 665 1106551 666 1107843 667 1113137 668 1114512 669 1120090 670 1121022 671 1126894 672 1127654 673 1133629 674 1134199 675 1140576 676 1140850 677 1147433 678 1147718 679 1154038 680 1154611 681 1160666 682 1161515 683 1167409 684 1168439 685 1174253 686 1175478 687 1180937 688 1182272 689 1187922 690 1188975 691 1194933 692 1195885 693 1201946 694 1202819 695 1208901 696 1209597 697 1216058 698 1216377 699 1223063 700 1223453 701 1229974 702 1230654 703 1236917 704 1237600 705 1243968 706 1244749 707 1250760 708 1252100 709 1257746 710 1259300 711 1264854 712 1266136 713 1272277 714 1273068 715 1279338 716 1280310 717 1286700 718 1287293 719 1294085 720 1294308 721 1301297 722 1301514 723 1308240 724 1309138 725 1315381 726 1316395 727 1322755 728 1323580 729 1329851 730 1331064 731 1336973 732 1338473 733 1344391 734 1345713 735 1351946 736 1352775 737 1359319 738 1360246 739 1366619 740 1367527 741 1374430 742 1374740 743 1381868 744 1382078 745 1389226 746 1389729 747 1396395 748 1397401 749 1403978 750 1404897 751 1411287 752 1412636 753 1418613 754 1420169 755 1426169 756 1427613 757 1434034 758 1434986 759 1441733 760 1442489 761 1449346 762 1450000 763 1457086 764 1457521 765 1464832 766 1465280 767 1472301 768 1473068 769 1479898 770 1480754 771 1487512 772 1488563 773 1495239 774 1496504 775 1502787 776 1504274 777 1510558 778 1511832 779 1518461 780 1519624 781 1526366 782 1527433 783 1534316 784 1534960 785 1542378 786 1542604 787 1550262 788 1550572 789 1558035 790 1558794 791 1565731 792 1566614 793 1573659 794 1574664 795 1581290 796 1582934 797 1589258 798 1590908 799 1597246 800 1598593 801 1605588 802 1606386 803 1613522 804 1614627 805 1621678 806 1622460 807 1629971 808 1630330 809 1638069 810 1638415 811 1645977 812 1646846 813 1653991 814 1654978 815 1662259 816 1663034 817 1670211 818 1671543 819 1678078 820 1679843 821 1686386 822 1687956 823 1694836 824 1695870 825 1703201 826 1704122 827 1711368 828 1712278 829 1720104 830 1720348 831 1728419 832 1728678 833 1736522 834 1737236 835 1744543 836 1745811 837 1753021 838 1754188 839 1761305 840 1762706 841 1769491 842 1771113 843 1777939 844 1779422 845 1786727 846 1787765 847 1795201 848 1796137 849 1803695 850 1804513 851 1812335 852 1812900 853 1821096 854 1821437 855 1829416 856 1830120 857 1837877 858 1838688 859 1846357 860 1847519 861 1854836 862 1856373 863 1863234 864 1865031 865 1871883 866 1873447 867 1880801 868 1881995 869 1889597 870 1890693 871 1898440 872 1899062 873 1907411 874 1907677 875 1916055 876 1916536 877 1924701 878 1925672 879 1933261 880 1934355 881 1942202 882 1943167 883 1950682 884 1952347 885 1959533 886 1961206 887 1968404 888 1969861 889 1977537 890 1978509 891 1986333 892 1987663 893 1995375 894 1996358 895 2004699 896 2004964 897 2013673 898 2013934 899 2022435 900 2023284 901 2031310 902 2032431 903 2040342 904 2041359 905 2049153 906 2050783 907 2057863 908 2059974 909 2067193 910 2068820 911 2076558 912 2077576 913 2085824 914 2086705 915 2094864 916 2095854 917 2104398 918 2104776 919 2113600 920 2113986 921 2122565 922 2123449 923 2131560 924 2132799 925 2140924 926 2142055 927 2150079 928 2151472 929 2159119 930 2160902 931 2168309 932 2170081 933 2178010 934 2179296 935 2187360 936 2188540 937 2196866 938 2197658 939 2206397 940 2206915 941 2216063 942 2216325 943 2225244 944 2226034 945 2234442 946 2235485 947 2243797 948 2245213 949 2253150 950 2254968 951 2262541 952 2264367 953 2272073 954 2273640 955 2281901 956 2283056 957 2291592 958 2292766 959 2301188 960 2301984 961 2311061 962 2311476 963 2320574 964 2321228 965 2330223 966 2331146 967 2339635 968 2340702 969 2349463 970 2350398 971 2358789 972 2360637 973 2368382 974 2370374 975 2378132 976 2379888 977 2388169 978 2389393 979 2397980 980 2399307 981 2407920 982 2408856 983 2418161 984 2418307 985 2428015 986 2428292 987 2437499 988 2438558 989 2447247 990 2448598 991 2457159 992 2458397 993 2466963 994 2468596 995 2476522 996 2478679 997 2486757 998 2488389 999 2497021 1000 2498135