0 1 1 4 2 12 3 24 4 38 5 66 6 100 7 118 8 162 9 220 10 262 11 300 12 376 13 456 14 516 15 566 16 648 17 774 18 848 19 936 20 1024 21 1126 22 1300 23 1366 24 1500 25 1628 26 1726 27 1916 28 2016 29 2218 30 2348 31 2428 32 2694 33 2874 34 3020 35 3120 36 3322 37 3624 38 3804 39 3924 40 4088 41 4372 42 4624 43 4852 44 5016 45 5214 46 5506 47 5718 48 6046 49 6274 50 6422 51 6708 52 7054 53 7422 54 7606 55 7706 56 8076 57 8574 58 8828 59 9028 60 9214 61 9616 62 10162 63 10322 64 10648 65 10906 66 11238 67 11784 68 12030 69 12446 70 12610 71 12932 72 13642 73 14016 74 14256 75 14368 76 14888 77 15598 78 16002 79 16164 80 16384 81 17040 82 17620 83 18064 84 18270 85 18576 86 19228 87 19726 88 20310 89 20624 90 20782 91 21380 92 22148 93 22790 94 23008 95 23038 96 23804 97 24768 98 25160 99 25444 100 25600 101 26430 102 27416 103 27666 104 28104 105 28330 106 29070 107 30044 108 30472 109 30972 110 31064 111 31748 112 32910 113 33582 114 33796 115 33848 116 34762 117 35946 118 36604 119 36628 120 36916 121 38014 122 39040 123 39684 124 39788 125 40158 126 41178 127 42154 128 42986 129 43296 130 43354 131 44320 132 45658 133 46480 134 46730 135 46594 136 47844 137 49374 138 49864 139 50172 140 50122 141 51554 142 53082 143 53426 144 53880 145 53936 146 55210 147 56632 148 57306 149 57822 150 57754 151 58876 152 60562 153 61542 154 61560 155 61532 156 62964 157 64728 158 65610 159 65384 160 65636 161 67216 162 68864 163 69720 164 69658 165 69942 166 71416 167 72966 168 73986 169 74278 170 74146 171 75620 172 77548 173 78562 174 78748 175 78270 176 80204 177 82382 178 83024 179 83188 180 82848 181 84976 182 87052 183 87606 184 87948 185 87818 186 89646 187 91608 188 92544 189 92866 190 92668 191 94300 192 96690 193 97896 194 97612 195 97432 196 99342 197 101934 198 103016 199 102516 200 102568 201 104696 202 107092 203 108028 204 107860 205 107936 206 110030 207 112186 208 113346 209 113576 210 113022 211 115244 212 117850 213 119110 214 119074 215 118118 216 120884 217 123664 218 124600 219 124524 220 123838 221 126714 222 129394 223 130194 224 130200 225 129914 226 132398 227 135048 228 136198 229 136188 230 135794 231 137908 232 141210 233 142670 234 142044 235 141548 236 144008 237 147534 238 148694 239 147948 240 147732 241 150562 242 153724 243 154724 244 154346 245 154014 246 156952 247 159822 248 161202 249 161172 250 160090 251 163156 252 166428 253 168064 254 167716 255 166278 256 169848 257 173338 258 174568 259 174028 260 173052 261 176758 262 180240 263 181166 264 180752 265 180212 266 183310 267 186908 268 188240 269 187930 270 187120 271 189808 272 194134 273 195686 274 194796 275 193864 276 197102 277 201528 278 202756 279 201692 280 200928 281 204756 282 208756 283 209940 284 209140 285 208274 286 212182 287 215682 288 217486 289 217074 290 215486 291 219380 292 223366 293 225430 294 224490 295 222666 296 227128 297 231526 298 232940 299 231800 300 230490 301 234932 302 239502 303 240554 304 239712 305 238730 306 242498 307 247176 308 248514 309 247982 310 246666 311 250124 312 255474 313 257076 314 255856 315 254220 316 258492 317 263942 318 265342 319 263748 320 262316 321 267248 322 272012 323 273552 324 272262 325 270872 326 275720 327 279930 328 282150 329 281108 330 279094 331 283924 332 288848 333 291190 334 289552 335 287246 336 292540 337 298120 338 299724 339 298028 340 296116 341 301402 342 307156 343 308158 344 306992 345 305458 346 310142 347 315828 348 317184 349 316332 350 314228 351 318764 352 325202 353 327030 354 325212 355 322772 356 328190 357 334550 358 336344 359 334100 360 332084 361 338038 362 343652 363 345572 364 343464 365 341702 366 347562 367 352746 368 355218 369 353420 370 350914 371 356548 372 362758 373 365352 374 363086 375 360042 376 366216 377 373126 378 374688 379 372580 380 369962 381 376338 382 383214 383 384126 384 382592 385 380172 386 386106 387 392896 388 394406 389 392998 390 389970 391 395716 392 403114 393 405390 394 402884 395 399692 396 406208 397 413532 398 415750 399 412540 400 410052 401 417152 402 423864 403 426000 404 422954 405 420734 406 427484 407 433958 408 436710 409 434214 410 430946 411 437464 412 445048 413 447694 414 444928 415 441062 416 448388 417 456526 418 458036 419 455420 420 451796 421 459584 422 467684 423 468694 424 466476 425 463086 426 470366 427 478132 428 480044 429 477970 430 474120 431 480956 432 489422 433 492144 434 488620 435 484840 436 492518 437 501126 438 503548 439 499272 440 496232 441 504316 442 512492 443 514820 444 510968 445 507968 446 515694 447 523578 448 526330 449 523336 450 519186 451 526900 452 535742 453 538410 454 535078 455 530018 456 538892 457 548328 458 550000 459 546572 460 541798 461 551146 462 560286 463 561682 464 558676 465 554418 466 562934 467 571732 468 574098 469 570976 470 566494 471 574516 472 584330 473 587310 474 582632 475 578204 476 586868 477 597126 478 599758 479 594516 480 590636 481 599758 482 609524 483 611776 484 607278 485 603430 486 612428 487 621606 488 624334 489 620756 490 615362 491 624636 492 634860 493 637752 494 633536 495 627170 496 637680 497 648262 498 650368 499 646044 500 640248 501 651006 502 661272 503 663054 504 658912 505 653964 506 663818 507 673980 508 676532 509 672278 510 667068 511 676100 512 687654 513 690878 514 685196 515 679760 516 689518 517 701520 518 704080 519 698084 520 693236 521 703764 522 714948 523 717120 524 711896 525 706798 526 717482 527 728026 528 731006 529 726474 530 719730 531 730684 532 742058 533 745518 534 740298 535 732794 536 744776 537 756570 538 759140 539 753500 540 746934 541 759172 542 770922 543 772834 544 767412 545 761730 546 772690 547 784648 548 787378 549 782142 550 775854 551 785952 552 799394 553 802528 554 796080 555 789540 556 800720 557 814326 558 816774 559 809964 560 803732 561 816080 562 828784 563 831120 564 824834 565 818348 566 830844 567 842534 568 846070 569 840516 570 832574 571 845044 572 857640 573 861678 574 855044 575 846622 576 860200 577 873552 578 876316 579 869248 580 861808 581 875326 582 888976 583 891030 584 884504 585 877698 586 889850 587 903700 588 906308 589 900316 590 892860 591 904404 592 919514 593 922570 594 915260 595 907200 596 920242 597 935534 598 938164 599 930132 600 922432 601 936694 602 950684 603 953540 604 946064 605 938414 606 952502 607 965430 608 969538 609 962512 610 953642 611 967700 612 981938 613 986232 614 978078 615 968666 616 983560 617 998958 618 1001892 619 993612 620 984894 621 999758 622 1015434 623 1017258 624 1009928 625 1001876 626 1015626 627 1031160 628 1033598 629 1026806 630 1017710 631 1031180 632 1048046 633 1051318 634 1042748 635 1033032 636 1048084 637 1064776 638 1067970 639 1058620 640 1049636 641 1065624 642 1080956 643 1084368 644 1075238 645 1066694 646 1082476 647 1097030 648 1101422 649 1092786 650 1082922 651 1098300 652 1114628 653 1119206 654 1109732 655 1098926 656 1115208 657 1132758 658 1135500 659 1126276 660 1116212 661 1132816 662 1150296 663 1151874 664 1143636 665 1133898 666 1149710 667 1167036 668 1169624 669 1161594 670 1150752 671 1166244 672 1184614 673 1188472 674 1178552 675 1167416 676 1184210 677 1202410 678 1206168 679 1195036 680 1185064 681 1202860 682 1219972 683 1223580 684 1212712 685 1203176 686 1220370 687 1237050 688 1241694 689 1231720 690 1220402 691 1237192 692 1255722 693 1260182 694 1249706 695 1237386 696 1255524 697 1274952 698 1277492 699 1267252 700 1255322 701 1274202 702 1293558 703 1295250 704 1285652 705 1274102 706 1292102 707 1310896 708 1314078 709 1304688 710 1292362 711 1309620 712 1329542 713 1334038 714 1322248 715 1310028 716 1328652 717 1348798 718 1352770 719 1339720 720 1328716 721 1347986 722 1367404 723 1371208 724 1358834 725 1347878 726 1366540 727 1385478 728 1389958 729 1378964 730 1366102 731 1384740 732 1405232 733 1409532 734 1397988 735 1383646 736 1404136 737 1425566 738 1428248 739 1416540 740 1402624 741 1423886 742 1444804 743 1447022 744 1435996 745 1422884 746 1442802 747 1463144 748 1466912 749 1455674 750 1442184 751 1461316 752 1483254 753 1487998 754 1474232 755 1460832 756 1480986 757 1503592 758 1507784 759 1493100 760 1480556 761 1501408 762 1523228 763 1526812 764 1513276 765 1500790 766 1521406 767 1542290 768 1546618 769 1534506 770 1519578 771 1540612 772 1563130 773 1567686 774 1554566 775 1538102 776 1561056 777 1584134 778 1587420 779 1574124 780 1558546 781 1581868 782 1604434 783 1607202 784 1594180 785 1579898 786 1601806 787 1624200 788 1628150 789 1614938 790 1600218 791 1620852 792 1645394 793 1650360 794 1634928 795 1619852 796 1641584 797 1666798 798 1670738 799 1654804 800 1640616 801 1663536 802 1687456 803 1690780 804 1676038 805 1661448 806 1684592 807 1707518 808 1712070 809 1698364 810 1681234 811 1704796 812 1728972 813 1734246 814 1719460 815 1701166 816 1726296 817 1751076 818 1754996 819 1739556 820 1722668 821 1748174 822 1772876 823 1775790 824 1760652 825 1745114 826 1768650 827 1793652 828 1797812 829 1782924 830 1766464 831 1788680 832 1815914 833 1820662 834 1803932 835 1787096 836 1810918 837 1838398 838 1842076 839 1824796 840 1808424 841 1833974 842 1860096 843 1863588 844 1847084 845 1830306 846 1856074 847 1880674 848 1885938 849 1870528 850 1851538 851 1877268 852 1903210 853 1909200 854 1892178 855 1872458 856 1899828 857 1926870 858 1930964 859 1913280 860 1895002 861 1922290 862 1949734 863 1952770 864 1935888 865 1918532 866 1943782 867 1971512 868 1975362 869 1959238 870 1940918 871 1965268 872 1994838 873 1999338 874 1981244 875 1962036 876 1988584 877 2018400 878 2022270 879 2003100 880 1984400 881 2012728 882 2040628 883 2044816 884 2026446 885 2007822 886 2035864 887 2062194 888 2068222 889 2050486 890 2030066 891 2058060 892 2086288 893 2092566 894 2073172 895 2051966 896 2081160 897 2111070 898 2115344 899 2095756 900 2075560 901 2104684 902 2134996 903 2137646 904 2119420 905 2100178 906 2127678 907 2157780 908 2161296 909 2143850 910 2123068 911 2150156 912 2182186 913 2186880 914 2166864 915 2145172 916 2174534 917 2206294 918 2210868 919 2189724 920 2169064 921 2199780 922 2229544 923 2234428 924 2213604 925 2193552 926 2223970 927 2252602 928 2258886 929 2238740 930 2216794 931 2246636 932 2277782 933 2284334 934 2262958 935 2239666 936 2270792 937 2303664 938 2307596 939 2286556 940 2264314 941 2295882 942 2328650 943 2330910 944 2311260 945 2289490 946 2319894 947 2352440 948 2356138 949 2336760 950 2313410 951 2343356 952 2377374 953 2382846 954 2360788 955 2337020 956 2368792 957 2402562 958 2407870 959 2384092 960 2361964 961 2395138 962 2427364 963 2432448 964 2409026 965 2387502 966 2419824 967 2451430 968 2457962 969 2435796 970 2411734 971 2443480 972 2477692 973 2483944 974 2461064 975 2435590 976 2469216 977 2504670 978 2508220 979 2485668 980 2460724 981 2495390 982 2530716 983 2533070 984 2511420 985 2486984 986 2520418 987 2554948 988 2559372 989 2537994 990 2512468 991 2544868 992 2580946 993 2587206 994 2562456 995 2537072 996 2571378 997 2607744 998 2613276 999 2586752 1000 2563052