0 1 1 4 2 9 3 16 4 25 5 39 6 58 7 80 8 107 9 143 10 185 11 220 12 254 13 293 14 330 15 368 16 414 17 486 18 577 19 660 20 727 21 775 22 834 23 911 24 970 25 1027 26 1124 27 1269 28 1411 29 1512 30 1587 31 1656 32 1756 33 1866 34 1950 35 2059 36 2232 37 2430 38 2577 39 2671 40 2765 41 2870 42 3000 43 3147 44 3302 45 3502 46 3728 47 3924 48 4057 49 4162 50 4285 51 4403 52 4560 53 4795 54 5060 55 5317 56 5540 57 5727 58 5879 59 6012 60 6137 61 6266 62 6504 63 6856 64 7178 65 7423 66 7636 67 7858 68 8055 69 8195 70 8333 71 8536 72 8886 73 9293 74 9584 75 9800 76 10046 77 10328 78 10547 79 10708 80 10937 81 11261 82 11658 83 12023 84 12270 85 12505 86 12802 87 13105 88 13353 89 13622 90 13991 91 14362 92 14710 93 15032 94 15298 95 15575 96 15878 97 16208 98 16571 99 16987 100 17407 101 17718 102 18018 103 18373 104 18690 105 18970 106 19296 107 19746 108 20263 109 20724 110 21069 111 21315 112 21644 113 22065 114 22394 115 22697 116 23154 117 23777 118 24341 119 24710 120 24975 121 25238 122 25626 123 26060 124 26416 125 26861 126 27504 127 28184 128 28657 129 28939 130 29219 131 29530 132 29918 133 30383 134 30886 135 31520 136 32220 137 32808 138 33197 139 33498 140 33831 141 34135 142 34548 143 35171 144 35872 145 36555 146 37146 147 37645 148 38057 149 38416 150 38745 151 39068 152 39646 153 40488 154 41242 155 41801 156 42288 157 42812 158 43285 159 43631 160 43977 161 44468 162 45272 163 46177 164 46806 165 47256 166 47770 167 48360 168 48819 169 49178 170 49691 171 50403 172 51262 173 52039 174 52558 175 53037 176 53626 177 54215 178 54695 179 55226 180 55965 181 56716 182 57422 183 58080 184 58626 185 59181 186 59772 187 60396 188 61073 189 61847 190 62627 191 63204 192 63768 193 64451 194 65068 195 65610 196 66232 197 67072 198 68017 199 68842 200 69447 201 69873 202 70458 203 71213 204 71808 205 72369 206 73202 207 74319 208 75321 209 75968 210 76425 211 76872 212 77534 213 78278 214 78892 215 79661 216 80770 217 81940 218 82751 219 83237 220 83717 221 84244 222 84896 223 85673 224 86514 225 87568 226 88726 227 89694 228 90331 229 90832 230 91387 231 91891 232 92574 233 93599 234 94746 235 95853 236 96802 237 97597 238 98253 239 98822 240 99343 241 99864 242 100792 243 102138 244 103342 245 104233 246 105008 247 105832 248 106569 249 107105 250 107639 251 108398 252 109644 253 111049 254 112026 255 112728 256 113532 257 114452 258 115165 259 115718 260 116503 261 117583 262 118880 263 120049 264 120826 265 121551 266 122446 267 123343 268 124081 269 124896 270 126017 271 127144 272 128192 273 129162 274 129964 275 130775 276 131640 277 132564 278 133573 279 134731 280 135897 281 136760 282 137600 283 138603 284 139500 285 140280 286 141172 287 142380 288 143743 289 144942 290 145829 291 146461 292 147326 293 148435 294 149304 295 150111 296 151300 297 152885 298 154299 299 155206 300 155849 301 156494 302 157452 303 158530 304 159426 305 160535 306 162114 307 163762 308 164889 309 165553 310 166211 311 166940 312 167854 313 168957 314 170156 315 171654 316 173290 317 174650 318 175539 319 176226 320 176981 321 177663 322 178598 323 180015 324 181606 325 183149 326 184476 327 185587 328 186503 329 187294 330 188009 331 188714 332 189974 333 191806 334 193446 335 194659 336 195718 337 196854 338 197871 339 198613 340 199351 341 200388 342 202078 343 203973 344 205284 345 206224 346 207304 347 208542 348 209505 349 210260 350 211329 351 212793 352 214542 353 216113 354 217154 355 218119 356 219310 357 220501 358 221481 359 222568 360 224063 361 225570 362 226972 363 228268 364 229340 365 230421 366 231570 367 232792 368 234123 369 235649 370 237185 371 238318 372 239422 373 240749 374 241936 375 242968 376 244148 377 245742 378 247537 379 249108 380 250265 381 251087 382 252212 383 253655 384 254786 385 255841 386 257396 387 259467 388 261315 389 262504 390 263347 391 264186 392 265428 393 266820 394 267974 395 269403 396 271438 397 273566 398 275023 399 275887 400 276749 401 277702 402 278890 403 280315 404 281856 405 283774 406 285864 407 287594 408 288721 409 289600 410 290573 411 291459 412 292672 413 294501 414 296548 415 298519 416 300204 417 301607 418 302757 419 303748 420 304647 421 305546 422 307160 423 309504 424 311604 425 313159 426 314510 427 315946 428 317223 429 318145 430 319061 431 320358 432 322486 433 324885 434 326552 435 327754 436 329134 437 330706 438 331923 439 332868 440 334199 441 336021 442 338200 443 340159 444 341462 445 342681 446 344188 447 345697 448 346939 449 348310 450 350183 451 352056 452 353790 453 355390 454 356714 455 358055 456 359486 457 361018 458 362691 459 364605 460 366527 461 367942 462 369312 463 370949 464 372408 465 373674 466 375128 467 377098 468 379321 469 381276 470 382719 471 383747 472 385148 473 386935 474 388330 475 389623 476 391530 477 394073 478 396341 479 397800 480 398839 481 399880 482 401418 483 403140 484 404566 485 406325 486 408822 487 411424 488 413201 489 414251 490 415301 491 416466 492 417920 493 419671 494 421566 495 423918 496 426476 497 428590 498 429965 499 431034 500 432215 501 433289 502 434764 503 436989 504 439480 505 441883 506 443936 507 445645 508 447047 509 448256 510 449353 511 450444 512 452400 513 455240 514 457780 515 459657 516 461288 517 463026 518 464573 519 465693 520 466809 521 468388 522 470968 523 473867 524 475878 525 477322 526 478978 527 480864 528 482321 529 483458 530 485065 531 487267 532 489902 533 492271 534 493848 535 495317 536 497124 537 498927 538 500407 539 502040 540 504277 541 506522 542 508606 543 510536 544 512138 545 513759 546 515484 547 517318 548 519313 549 521591 550 523873 551 525548 552 527174 553 529131 554 530884 555 532410 556 534162 557 536528 558 539187 559 541514 560 543223 561 544431 562 546082 563 548195 564 549848 565 551393 566 553674 567 556713 568 559425 569 561170 570 562409 571 563640 572 565452 573 567478 574 569154 575 571229 576 574186 577 577276 578 579393 579 580653 580 581911 581 583300 582 585024 583 587087 584 589314 585 592078 586 595086 587 597574 588 599195 589 600466 590 601875 591 603157 592 604910 593 607543 594 610480 595 613301 596 615704 597 617701 598 619341 599 620758 600 622049 601 623344 602 625658 603 629010 604 632006 605 634215 606 636128 607 638158 608 639961 609 641265 610 642567 611 644416 612 647444 613 650851 614 653218 615 654920 616 656866 617 659076 618 660779 619 662102 620 663975 621 666543 622 669618 623 672385 624 674228 625 675951 626 678070 627 680181 628 681913 629 683822 630 686433 631 689048 632 691472 633 693716 634 695580 635 697465 636 699472 637 701612 638 703939 639 706595 640 709255 641 711208 642 713104 643 715379 644 717414 645 719184 646 721214 647 723956 648 727039 649 729740 650 731725 651 733131 652 735054 653 737515 654 739440 655 741233 656 743876 657 747391 658 750523 659 752534 660 753959 661 755382 662 757482 663 759834 664 761786 665 764199 666 767628 667 771202 668 773643 669 775089 670 776531 671 778122 672 780102 673 782483 674 785060 675 788262 676 791746 677 794628 678 796507 679 797972 680 799589 681 801055 682 803060 683 806079 684 809452 685 812701 686 815476 687 817787 688 819689 689 821334 690 822827 691 824314 692 826966 693 830804 694 834230 695 836753 696 838942 697 841278 698 843359 699 844871 700 846383 701 848518 702 851998 703 855901 704 858602 705 860536 706 862750 707 865270 708 867217 709 868740 710 870899 711 873857 712 877392 713 880569 714 882682 715 884645 716 887054 717 889451 718 891417 719 893592 720 896575 721 899572 722 902356 723 904934 724 907076 725 909237 726 911528 727 913960 728 916601 729 919617 730 922641 731 924862 732 927024 733 929629 734 931962 735 933992 736 936316 737 939444 738 942953 739 946018 740 948265 741 949855 742 952036 743 954833 744 957026 745 959075 746 962092 747 966099 748 969665 749 971952 750 973569 751 975178 752 977556 753 980220 754 982432 755 985171 756 989064 757 993126 758 995903 759 997549 760 999189 761 1000996 762 1003242 763 1005939 764 1008856 765 1012480 766 1016424 767 1019684 768 1021809 769 1023472 770 1025307 771 1026971 772 1029246 773 1032669 774 1036492 775 1040167 776 1043302 777 1045911 778 1048055 779 1049908 780 1051591 781 1053272 782 1056272 783 1060614 784 1064492 785 1067351 786 1069830 787 1072468 788 1074815 789 1076515 790 1078213 791 1080614 792 1084532 793 1088933 794 1091982 795 1094170 796 1096678 797 1099530 798 1101733 799 1103452 800 1105881 801 1109205 802 1113176 803 1116741 804 1119110 805 1121319 806 1124036 807 1126745 808 1128971 809 1131432 810 1134799 811 1138170 812 1141294 813 1144182 814 1146576 815 1148991 816 1151556 817 1154290 818 1157267 819 1160669 820 1164081 821 1166590 822 1169026 823 1171949 824 1174560 825 1176824 826 1179416 827 1182912 828 1186841 829 1190284 830 1192815 831 1194613 832 1197076 833 1200225 834 1202690 835 1204983 836 1208352 837 1212825 838 1216803 839 1219352 840 1221159 841 1222968 842 1225644 843 1228644 844 1231136 845 1234213 846 1238574 847 1243110 848 1246201 849 1248025 850 1249845 851 1251858 852 1254368 853 1257393 854 1260670 855 1264736 856 1269156 857 1272806 858 1275179 859 1277026 860 1279061 861 1280905 862 1283436 863 1287253 864 1291522 865 1295635 866 1299146 867 1302069 868 1304471 869 1306542 870 1308417 871 1310282 872 1313616 873 1318448 874 1322764 875 1325947 876 1328712 877 1331660 878 1334285 879 1336189 880 1338087 881 1340764 882 1345126 883 1350019 884 1353406 885 1355834 886 1358620 887 1361792 888 1364243 889 1366162 890 1368873 891 1372577 892 1376998 893 1380965 894 1383600 895 1386053 896 1389068 897 1392073 898 1394543 899 1397274 900 1401013 901 1404762 902 1408236 903 1411448 904 1414112 905 1416799 906 1419652 907 1422686 908 1425987 909 1429759 910 1433539 911 1436316 912 1439014 913 1442257 914 1445156 915 1447672 916 1450554 917 1454440 918 1458803 919 1462620 920 1465423 921 1467409 922 1470130 923 1473611 924 1476334 925 1478873 926 1482608 927 1487569 928 1491985 929 1494818 930 1496827 931 1498832 932 1501790 933 1505102 934 1507850 935 1511243 936 1516058 937 1521074 938 1524497 939 1526525 940 1528551 941 1530790 942 1533576 943 1536921 944 1540538 945 1545022 946 1549892 947 1553910 948 1556521 949 1558562 950 1560819 951 1562869 952 1565680 953 1569911 954 1574634 955 1579173 956 1583040 957 1586251 958 1588885 959 1591156 960 1593217 961 1595280 962 1598970 963 1604316 964 1609094 965 1612617 966 1615672 967 1618918 968 1621799 969 1623881 970 1625957 971 1628896 972 1633700 973 1639099 974 1642844 975 1645536 976 1648620 977 1652124 978 1654827 979 1656932 980 1659903 981 1663965 982 1668818 983 1673177 984 1676076 985 1678785 986 1682118 987 1685439 988 1688169 989 1691182 990 1695295 991 1699408 992 1703214 993 1706732 994 1709652 995 1712601 996 1715738 997 1719084 998 1722725 999 1726883 1000 1731047