0 1 1 4 2 12 3 24 4 36 5 61 6 101 7 133 8 156 9 204 10 256 11 314 12 391 13 444 14 492 15 589 16 686 17 760 18 843 19 951 20 1063 21 1157 22 1285 23 1416 24 1461 25 1630 26 1841 27 1903 28 2058 29 2214 30 2347 31 2555 32 2713 33 2901 34 3024 35 3172 36 3446 37 3655 38 3804 39 4002 40 4213 41 4391 42 4684 43 4938 44 5088 45 5314 46 5549 47 5848 48 6135 49 6354 50 6577 51 6812 52 7132 53 7476 54 7737 55 7954 56 8252 57 8554 58 8868 59 9288 60 9517 61 9746 62 10162 63 10491 64 10839 65 11191 66 11486 67 11854 68 12180 69 12558 70 13042 71 13304 72 13618 73 14130 74 14427 75 14845 76 15359 77 15667 78 16044 79 16434 80 16903 81 17438 82 17767 83 18159 84 18633 85 19024 86 19583 87 20128 88 20442 89 20856 90 21373 91 21899 92 22471 93 22893 94 23259 95 23809 96 24344 97 24925 98 25491 99 25845 100 26365 101 26951 102 27490 103 28167 104 28626 105 29017 106 29675 107 30280 108 30861 109 31500 110 31978 111 32486 112 33118 113 33756 114 34470 115 35011 116 35441 117 36175 118 36822 119 37458 120 38188 121 38693 122 39256 123 39942 124 40674 125 41428 126 42008 127 42523 128 43281 129 44019 130 44698 131 45488 132 46081 133 46668 134 47415 135 48205 136 49028 137 49669 138 50238 139 51051 140 51829 141 52574 142 53449 143 54117 144 54669 145 55525 146 56426 147 57247 148 57990 149 58581 150 59434 151 60287 152 61138 153 62073 154 62682 155 63367 156 64307 157 65236 158 66150 159 66915 160 67561 161 68462 162 69418 163 70353 164 71244 165 71956 166 72758 167 73687 168 74670 169 75693 170 76477 171 77162 172 78181 173 79188 174 80127 175 81103 176 81926 177 82735 178 83679 179 84798 180 85870 181 86657 182 87460 183 88521 184 89529 185 90571 186 91640 187 92512 188 93330 189 94362 190 95551 191 96647 192 97528 193 98391 194 99471 195 100525 196 101687 197 102823 198 103680 199 104586 200 105688 201 106910 202 108109 203 109065 204 109899 205 111052 206 112235 207 113431 208 114621 209 115494 210 116479 211 117656 212 118918 213 120243 214 121161 215 122056 216 123341 217 124564 218 125805 219 127011 220 127999 221 129026 222 130252 223 131607 224 132930 225 133924 226 134891 227 136267 228 137499 229 138777 230 140134 231 141125 232 142192 233 143499 234 144885 235 146296 236 147380 237 148372 238 149763 239 151080 240 152428 241 153872 242 154888 243 155985 244 157395 245 158821 246 160316 247 161458 248 162453 249 163935 250 165325 251 166721 252 168223 253 169290 254 170439 255 171913 256 173405 257 174964 258 176160 259 177213 260 178750 261 180182 262 181663 263 183237 264 184320 265 185536 266 187073 267 188617 268 190260 269 191517 270 192586 271 194171 272 195730 273 197271 274 198822 275 200017 276 201287 277 202855 278 204528 279 206178 280 207475 281 208589 282 210271 283 211950 284 213420 285 215086 286 216398 287 217651 288 219297 289 221043 290 222733 291 224063 292 225310 293 227040 294 228669 295 230260 296 232046 297 233380 298 234633 299 236391 300 238195 301 239915 302 241378 303 242634 304 244356 305 246079 306 247817 307 249628 308 250938 309 252303 310 254104 311 255974 312 257782 313 259296 314 260565 315 262330 316 264209 317 265978 318 267780 319 269190 320 270631 321 272447 322 274390 323 276306 324 277797 325 279142 326 281024 327 282931 328 284745 329 286599 330 288103 331 289571 332 291439 333 293487 334 295422 335 296965 336 298373 337 300340 338 302277 339 304131 340 306109 341 307628 342 309148 343 311109 344 313173 345 315187 346 316787 347 318268 348 320289 349 322233 350 324208 351 326231 352 327778 353 329397 354 331362 355 333514 356 335630 357 337264 358 338781 359 340842 360 342862 361 344921 362 347011 363 348579 364 350241 365 352276 366 354509 367 356710 368 358353 369 359922 370 362056 371 364154 372 366271 373 368406 374 370029 375 371722 376 373871 377 376144 378 378372 379 380118 380 381700 381 383915 382 386083 383 388248 384 390438 385 392119 386 393887 387 396064 388 398409 389 400716 390 402517 391 404108 392 406417 393 408669 394 410808 395 413146 396 414863 397 416650 398 418941 399 421311 400 423697 401 425510 402 427189 403 429606 404 431829 405 434065 406 436484 407 438229 408 440061 409 442443 410 444862 411 447260 412 449224 413 450948 414 453324 415 455656 416 458000 417 460450 418 462240 419 464136 420 466546 421 469025 422 471550 423 473574 424 475242 425 477703 426 480197 427 482560 428 485034 429 486903 430 488824 431 491297 432 493894 433 496473 434 498471 435 500191 436 502814 437 505351 438 507696 439 510276 440 512215 441 514157 442 516715 443 519396 444 521967 445 524029 446 525899 447 528523 448 531063 449 533508 450 536167 451 538166 452 540139 453 542772 454 545493 455 548131 456 550283 457 552199 458 554838 459 557427 460 560026 461 562688 462 564718 463 566784 464 569424 465 572260 466 574943 467 577171 468 579123 469 581778 470 584518 471 587120 472 589834 473 591951 474 594039 475 596761 476 599645 477 602413 478 604677 479 606666 480 609397 481 612203 482 614875 483 617640 484 619809 485 621937 486 624728 487 627688 488 630534 489 632817 490 634828 491 637676 492 640519 493 643272 494 646089 495 648274 496 650513 497 653338 498 656361 499 659289 500 661582 501 663668 502 666607 503 669486 504 672258 505 675169 506 677429 507 679702 508 682584 509 685680 510 688669 511 690998 512 693175 513 696165 514 699036 515 701929 516 704936 517 707200 518 709521 519 712470 520 715630 521 718670 522 721087 523 723327 524 726306 525 729280 526 732266 527 735307 528 737595 529 739992 530 743032 531 746174 532 749350 533 751845 534 754014 535 757135 536 760196 537 763207 538 766308 539 768663 540 771112 541 774164 542 777439 543 780687 544 783159 545 785386 546 788624 547 791740 548 794766 549 797976 550 800356 551 802832 552 805999 553 809358 554 812595 555 815104 556 817478 557 820741 558 823893 559 826995 560 830251 561 832691 562 835213 563 838500 564 841836 565 845128 566 847817 567 850165 568 853458 569 856692 570 859855 571 863192 572 865696 573 868257 574 871548 575 874975 576 878369 577 881131 578 883458 579 886803 580 890182 581 893360 582 896770 583 899328 584 901890 585 905281 586 908795 587 912262 588 915015 589 917385 590 920863 591 924269 592 927502 593 930981 594 933573 595 936217 596 939662 597 943249 598 946755 599 949545 600 952018 601 955529 602 958981 603 962289 604 965817 605 968494 606 971162 607 974671 608 978351 609 981885 610 984736 611 987275 612 990820 613 994356 614 997740 615 1001290 616 1004033 617 1006747 618 1010322 619 1014096 620 1017646 621 1020569 622 1023175 623 1026777 624 1030350 625 1033798 626 1037441 627 1040200 628 1043007 629 1046625 630 1050418 631 1054067 632 1057057 633 1059729 634 1063317 635 1066987 636 1070546 637 1074211 638 1077039 639 1079877 640 1083541 641 1087394 642 1091176 643 1094208 644 1096830 645 1100536 646 1104296 647 1107919 648 1111599 649 1114500 650 1117414 651 1121066 652 1125085 653 1128918 654 1131894 655 1134628 656 1138454 657 1142239 658 1145862 659 1149663 660 1152610 661 1155536 662 1159318 663 1163391 664 1167219 665 1170274 666 1173116 667 1176982 668 1180776 669 1184493 670 1188391 671 1191326 672 1194319 673 1198221 674 1202262 675 1206178 676 1209368 677 1212202 678 1216116 679 1219986 680 1223779 681 1227719 682 1230691 683 1233801 684 1237698 685 1241782 686 1245857 687 1249048 688 1251894 689 1255911 690 1259833 691 1263695 692 1267708 693 1270740 694 1273854 695 1277806 696 1282010 697 1286146 698 1289367 699 1292232 700 1296343 701 1300328 702 1304242 703 1308351 704 1311378 705 1314550 706 1318604 707 1322887 708 1327041 709 1330302 710 1333261 711 1337399 712 1341487 713 1345434 714 1349565 715 1352701 716 1355900 717 1360057 718 1364358 719 1368558 720 1371928 721 1374905 722 1379128 723 1383249 724 1387245 725 1391476 726 1394663 727 1397902 728 1402104 729 1406469 730 1410736 731 1414193 732 1417186 733 1421472 734 1425672 735 1429714 736 1434029 737 1437241 738 1440534 739 1444809 740 1449244 741 1453568 742 1457059 743 1460130 744 1464429 745 1468735 746 1472849 747 1477174 748 1480503 749 1483815 750 1488133 751 1492649 752 1497037 753 1500606 754 1503678 755 1508053 756 1512440 757 1516594 758 1521003 759 1524384 760 1527709 761 1532087 762 1536727 763 1541184 764 1544736 765 1547869 766 1552343 767 1556785 768 1560990 769 1565472 770 1568878 771 1572221 772 1576744 773 1581459 774 1585878 775 1589515 776 1592762 777 1597276 778 1601730 779 1606038 780 1610572 781 1613984 782 1617487 783 1622028 784 1626714 785 1631251 786 1634984 787 1638298 788 1642791 789 1647333 790 1651747 791 1656281 792 1659793 793 1663368 794 1667871 795 1672648 796 1677359 797 1681081 798 1684380 799 1688976 800 1693603 801 1698065 802 1702645 803 1706265 804 1709814 805 1714378 806 1719332 807 1724029 808 1727772 809 1731138 810 1735837 811 1740509 812 1744996 813 1749702 814 1753296 815 1756918 816 1761593 817 1766584 818 1771341 819 1775112 820 1778575 821 1783316 822 1788028 823 1792614 824 1797363 825 1800988 826 1804676 827 1809442 828 1814448 829 1819290 830 1823137 831 1826606 832 1831450 833 1836207 834 1840839 835 1845673 836 1849334 837 1853098 838 1857912 839 1862964 840 1867870 841 1871780 842 1875310 843 1880202 844 1885011 845 1889719 846 1894625 847 1898341 848 1902144 849 1907004 850 1912117 851 1917110 852 1921099 853 1924635 854 1929573 855 1934470 856 1939235 857 1944220 858 1947972 859 1951818 860 1956757 861 1961927 862 1966999 863 1971039 864 1974561 865 1979617 866 1984610 867 1989367 868 1994451 869 1998243 870 2002117 871 2007155 872 2012380 873 2017533 874 2021574 875 2025175 876 2030327 877 2035330 878 2040183 879 2045310 880 2049160 881 2053064 882 2058172 883 2063514 884 2068644 885 2072779 886 2076455 887 2081635 888 2086710 889 2091636 890 2096818 891 2100677 892 2104690 893 2109870 894 2115222 895 2120416 896 2124644 897 2128369 898 2133549 899 2138763 900 2143714 901 2148914 902 2152933 903 2156952 904 2162139 905 2167567 906 2172872 907 2177173 908 2180886 909 2186145 910 2191423 911 2196404 912 2201713 913 2205819 914 2209785 915 2215039 916 2220644 917 2225977 918 2230272 919 2234049 920 2239396 921 2244707 922 2249782 923 2255187 924 2259228 925 2263279 926 2268683 927 2274316 928 2279664 929 2284011 930 2287897 931 2293280 932 2298646 933 2303823 934 2309202 935 2313322 936 2317502 937 2322919 938 2328582 939 2333991 940 2338441 941 2342372 942 2347777 943 2353248 944 2358453 945 2363893 946 2368106 947 2372323 948 2377761 949 2383500 950 2389036 951 2393483 952 2397448 953 2402943 954 2408445 955 2413753 956 2419250 957 2423506 958 2427768 959 2433264 960 2439079 961 2444675 962 2449180 963 2453169 964 2458761 965 2464309 966 2469659 967 2475253 968 2479530 969 2483868 970 2489392 971 2495288 972 2500987 973 2505501 974 2509551 975 2515198 976 2520803 977 2526229 978 2531901 979 2536212 980 2540569 981 2546174 982 2552158 983 2557929 984 2562429 985 2566570 986 2572307 987 2577928 988 2583465 989 2589165 990 2593507 991 2597930 992 2603638 993 2609679 994 2615418 995 2620054 996 2624243 997 2630023 998 2635737 999 2641287 1000 2647078