0 1 1 4 2 10 3 21 4 37 5 55 6 76 7 103 8 149 9 191 10 218 11 266 12 326 13 374 14 433 15 520 16 603 17 653 18 716 19 809 20 910 21 1002 22 1091 23 1215 24 1320 25 1400 26 1520 27 1673 28 1824 29 1932 30 2039 31 2200 32 2362 33 2482 34 2631 35 2831 36 3006 37 3131 38 3291 39 3511 40 3696 41 3864 42 4057 43 4256 44 4449 45 4633 46 4832 47 5091 48 5355 49 5541 50 5728 51 5983 52 6248 53 6438 54 6700 55 7055 56 7274 57 7421 58 7674 59 8026 60 8333 61 8569 62 8854 63 9200 64 9441 65 9675 66 10031 67 10365 68 10712 69 11000 70 11256 71 11612 72 11942 73 12233 74 12638 75 13058 76 13376 77 13627 78 13960 79 14434 80 14763 81 15104 82 15566 83 15895 84 16208 85 16601 86 17037 87 17514 88 17961 89 18313 90 18656 91 19022 92 19509 93 19977 94 20354 95 20898 96 21331 97 21641 98 22093 99 22605 100 23111 101 23571 102 24015 103 24532 104 24932 105 25313 106 25891 107 26421 108 27017 109 27523 110 27836 111 28393 112 28966 113 29407 114 29987 115 30598 116 31130 117 31549 118 31953 119 32686 120 33339 121 33800 122 34444 123 34922 124 35380 125 35987 126 36578 127 37282 128 37962 129 38441 130 38949 131 39515 132 40192 133 40853 134 41360 135 42208 136 42902 137 43162 138 43749 139 44568 140 45331 141 45988 142 46548 143 47259 144 47857 145 48306 146 49126 147 49969 148 50705 149 51367 150 51804 151 52549 152 53346 153 53931 154 54766 155 55651 156 56263 157 56746 158 57364 159 58423 160 59293 161 59766 162 60679 163 61491 164 61951 165 62665 166 63495 167 64446 168 65340 169 65964 170 66686 171 67392 172 68134 173 69091 174 69957 175 70928 176 71732 177 72108 178 72865 179 73904 180 74807 181 75743 182 76595 183 77427 184 78125 185 78715 186 79786 187 80882 188 81727 189 82613 190 83253 191 84015 192 85025 193 85880 194 86938 195 88039 196 88853 197 89526 198 90231 199 91337 200 92456 201 93294 202 94345 203 95299 204 95873 205 96721 206 97827 207 99039 208 100203 209 101003 210 101787 211 102572 212 103512 213 104734 214 105798 215 106882 216 107970 217 108635 218 109397 219 110586 220 111799 221 112950 222 113915 223 114915 224 115832 225 116543 226 117649 227 119010 228 120275 229 121296 230 122097 231 123058 232 124193 233 125152 234 126362 235 127796 236 128890 237 129622 238 130320 239 131665 240 133158 241 134231 242 135347 243 136543 244 137432 245 138194 246 139401 247 140990 248 142367 249 143235 250 144221 251 145352 252 146422 253 147592 254 148959 255 150548 256 151657 257 152340 258 153319 259 154670 260 156040 261 157402 262 158671 263 159934 264 160942 265 161730 266 163050 267 164632 268 166179 269 167283 270 168245 271 169530 272 170633 273 171736 274 173345 275 175044 276 176172 277 176986 278 177996 279 179625 280 181104 281 182313 282 183852 283 185144 284 186202 285 187209 286 188492 287 190215 288 191808 289 192994 290 194251 291 195412 292 196551 293 197941 294 199577 295 201485 296 202634 297 203484 298 204801 299 206100 300 207554 301 209289 302 210893 303 212311 304 213369 305 214349 306 215938 307 217554 308 219358 309 220899 310 221757 311 223114 312 224553 313 225863 314 227631 315 229424 316 230931 317 232121 318 233108 319 234743 320 236406 321 237874 322 239711 323 241067 324 242319 325 243633 326 244841 327 246841 328 248934 329 250225 330 251490 331 252804 332 254208 333 255760 334 257305 335 259552 336 261259 337 262039 338 263477 339 265105 340 266753 341 268627 342 270303 343 272000 344 273317 345 274333 346 276014 347 277840 348 279844 349 281714 350 282779 351 284461 352 286183 353 287179 354 289050 355 291360 356 293144 357 294377 358 295366 359 297278 360 299258 361 300765 362 302913 363 304731 364 305948 365 307318 366 308709 367 310872 368 313139 369 314524 370 316124 371 317824 372 319275 373 320863 374 322676 375 325252 376 327170 377 327864 378 329587 379 331653 380 333072 381 335014 382 337137 383 339180 384 340676 385 341768 386 343698 387 345675 388 347633 389 349809 390 351369 391 352980 392 354726 393 356024 394 358177 395 360691 396 362460 397 363983 398 365426 399 367441 400 369389 401 371024 402 373410 403 375455 404 376767 405 378572 406 380307 407 382154 408 384590 409 386460 410 388271 411 390041 412 391724 413 393560 414 395398 415 397972 416 400267 417 401477 418 403129 419 405308 420 406923 421 408981 422 411381 423 413622 424 415360 425 416646 426 418702 427 420829 428 423024 429 425425 430 427081 431 428657 432 430849 433 432666 434 434564 435 437086 436 439332 437 441147 438 442680 439 444878 440 447076 441 448793 442 451074 443 453471 444 455294 445 456994 446 458908 447 461136 448 463759 449 465730 450 467607 451 469688 452 471714 453 473577 454 475350 455 478153 456 480820 457 482270 458 483852 459 486403 460 488674 461 490505 462 492825 463 495486 464 497412 465 498719 466 500995 467 503514 468 505769 469 507944 470 510099 471 512534 472 514577 473 516209 474 518387 475 521145 476 523518 477 525398 478 527192 479 529720 480 531999 481 533861 482 536533 483 539142 484 541152 485 542829 486 544987 487 547651 488 549986 489 552057 490 554431 491 556719 492 558796 493 560915 494 563171 495 566193 496 568599 497 570161 498 572368 499 574912 500 577247 501 579325 502 581663 503 584552 504 586805 505 588515 506 591082 507 593497 508 595797 509 598246 510 600610 511 603270 512 605213 513 607147 514 609956 515 612545 516 614897 517 617231 518 619369 519 622032 520 624394 521 626441 522 629272 523 631711 524 634012 525 636452 526 638515 527 641217 528 643922 529 646101 530 648566 531 650940 532 653502 533 656025 534 658097 535 661016 536 663730 537 665712 538 668256 539 670723 540 673245 541 675829 542 677965 543 680989 544 683740 545 685537 546 688088 547 690784 548 693593 549 696162 550 698084 551 701032 552 703871 553 705721 554 708539 555 711444 556 713917 557 716272 558 718510 559 721785 560 724533 561 726405 562 729190 563 731880 564 734345 565 737084 566 739348 567 742453 568 745537 569 747269 570 749887 571 752857 572 755631 573 758196 574 760302 575 763544 576 766528 577 768280 578 771077 579 774262 580 776859 581 779612 582 781956 583 784971 584 787720 585 789571 586 792641 587 795873 588 798537 589 800934 590 803195 591 806637 592 809836 593 811521 594 814651 595 818099 596 820113 597 822469 598 825175 599 828698 600 831597 601 833691 602 836923 603 839807 604 842060 605 845037 606 847939 607 850909 608 854019 609 856063 610 858805 611 861856 612 864550 613 867641 614 870568 615 873934 616 876643 617 878346 618 881406 619 884933 620 887515 621 890705 622 893469 623 895906 624 898892 625 901602 626 904931 627 908014 628 910897 629 913716 630 915940 631 919030 632 922567 633 925001 634 927966 635 931631 636 934068 637 936457 638 939319 639 943024 640 946280 641 948628 642 951822 643 954724 644 957146 645 960324 646 963515 647 966580 648 970251 649 972865 650 975045 651 977998 652 981395 653 984813 654 987641 655 991074 656 994075 657 996028 658 999004 659 1002918 660 1006121 661 1009040 662 1012001 663 1014943 664 1017962 665 1020557 666 1023886 667 1027461 668 1030948 669 1033833 670 1035817 671 1039055 672 1043007 673 1045767 674 1048653 675 1052687 676 1055788 677 1057618 678 1060326 679 1064773 680 1068446 681 1070815 682 1074103 683 1077328 684 1079730 685 1082620 686 1086418 687 1090474 688 1093795 689 1096117 690 1098737 691 1102063 692 1105612 693 1108964 694 1112058 695 1115968 696 1119019 697 1120889 698 1124112 699 1128294 700 1131832 701 1134796 702 1138221 703 1141697 704 1143975 705 1146543 706 1150675 707 1154555 708 1157913 709 1160959 710 1163437 711 1166816 712 1170493 713 1173690 714 1177478 715 1181218 716 1184229 717 1186367 718 1189007 719 1193590 720 1197578 721 1200432 722 1204095 723 1207269 724 1209780 725 1212911 726 1216821 727 1221153 728 1224368 729 1227066 730 1230338 731 1233108 732 1236442 733 1240472 734 1244284 735 1248506 736 1251567 737 1253472 738 1256694 739 1260580 740 1264561 741 1268532 742 1271598 743 1274880 744 1277601 745 1280454 746 1284848 747 1288795 748 1292701 749 1296170 750 1298316 751 1301509 752 1305407 753 1308928 754 1313065 755 1316774 756 1320188 757 1323061 758 1325313 759 1329895 760 1334436 761 1337425 762 1341124 763 1344483 764 1347353 765 1350515 766 1353822 767 1358654 768 1363282 769 1365873 770 1368905 771 1371866 772 1375376 773 1379500 774 1383252 775 1388024 776 1391521 777 1393151 778 1396375 779 1400810 780 1404983 781 1409104 782 1412302 783 1416197 784 1419413 785 1421377 786 1425745 787 1430433 788 1434595 789 1438228 790 1440611 791 1444114 792 1448139 793 1451318 794 1455811 795 1460446 796 1463737 797 1466599 798 1468993 799 1473520 800 1478246 801 1481521 802 1485830 803 1489638 804 1492164 805 1495096 806 1498904 807 1504259 808 1509098 809 1511268 810 1514660 811 1518548 812 1521624 813 1525674 814 1529898 815 1534882 816 1538520 817 1540400 818 1544045 819 1548496 820 1552265 821 1556775 822 1560992 823 1564737 824 1567854 825 1570129 826 1574584 827 1579355 828 1583432 829 1587588 830 1590738 831 1594181 832 1597893 833 1601245 834 1606264 835 1611339 836 1614367 837 1617529 838 1620453 839 1624332 840 1629231 841 1633371 842 1637884 843 1641476 844 1644381 845 1648004 846 1651820 847 1656528 848 1661648 849 1664884 850 1667998 851 1671825 852 1675206 853 1679311 854 1683803 855 1689141 856 1693416 857 1695550 858 1698838 859 1703164 860 1707290 861 1712119 862 1716481 863 1720086 864 1723741 865 1726688 866 1730599 867 1735555 868 1740566 869 1744862 870 1747683 871 1751176 872 1755258 873 1758790 874 1763515 875 1768973 876 1772788 877 1775756 878 1779079 879 1783518 880 1788263 881 1792231 882 1796784 883 1800962 884 1804406 885 1807816 886 1811188 887 1816108 888 1822037 889 1825924 890 1828800 891 1832852 892 1836967 893 1840319 894 1844651 895 1850879 896 1855405 897 1857330 898 1860731 899 1865687 900 1869982 901 1874382 902 1879388 903 1884131 904 1887244 905 1889866 906 1894194 907 1899289 908 1904358 909 1908688 910 1912037 911 1916234 912 1920332 913 1923589 914 1928484 915 1934292 916 1938620 917 1941417 918 1944980 919 1950034 920 1953863 921 1957930 922 1963721 923 1968315 924 1971319 925 1974727 926 1978836 927 1984000 928 1989326 929 1993464 930 1997402 931 2001054 932 2005223 933 2009267 934 2013481 935 2019562 936 2024318 937 2026978 938 2030870 939 2035517 940 2039726 941 2044332 942 2049448 943 2054685 944 2057887 945 2060954 946 2065909 947 2070196 948 2075027 949 2080175 950 2084176 951 2088529 952 2092533 953 2095863 954 2101000 955 2106638 956 2111424 957 2115227 958 2118200 959 2123084 960 2127546 961 2131825 962 2137635 963 2142060 964 2145720 965 2149971 966 2153943 967 2158772 968 2164185 969 2168605 970 2172926 971 2176497 972 2181043 973 2185814 974 2189392 975 2195525 976 2201177 977 2204089 978 2207916 979 2212725 980 2217308 981 2221941 982 2226345 983 2231967 984 2236570 985 2239334 986 2244115 987 2248921 988 2254191 989 2259423 990 2263072 991 2267840 992 2272414 993 2275615 994 2280600 995 2286561 996 2291428 997 2295412 998 2298701 999 2304593 1000 2309753