0 1 1 4 2 10 3 20 4 34 5 58 6 82 7 108 8 144 9 186 10 222 11 268 12 330 13 386 14 430 15 500 16 592 17 658 18 706 19 804 20 930 21 1002 22 1050 23 1180 24 1344 25 1418 26 1462 27 1628 28 1834 29 1906 30 1942 31 2148 32 2400 33 2466 34 2490 35 2740 36 3042 37 3098 38 3106 39 3404 40 3760 41 3802 42 3790 43 4140 44 4554 45 4578 46 4542 47 4948 48 5424 49 5426 50 5362 51 5828 52 6370 53 6346 54 6250 55 6780 56 7392 57 7338 58 7206 59 7804 60 8490 61 8402 62 8230 63 8900 64 9664 65 9538 66 9322 67 10068 68 10914 69 10746 70 10482 71 11308 72 12240 73 12026 74 11710 75 12620 76 13642 77 13378 78 13006 79 14004 80 15120 81 14802 82 14370 83 15460 84 16674 85 16298 86 15802 87 16988 88 18304 89 17866 90 17302 91 18588 92 20010 93 19506 94 18870 95 20260 96 21792 97 21218 98 20506 99 22004 100 23650 101 23002 102 22210 103 23820 104 25584 105 24858 106 23982 107 25708 108 27594 109 26786 110 25822 111 27668 112 29680 113 28786 114 27730 115 29700 116 31842 117 30858 118 29706 119 31804 120 34080 121 33002 122 31750 123 33980 124 36394 125 35218 126 33862 127 36228 128 38784 129 37506 130 36042 131 38548 132 41250 133 39866 134 38290 135 40940 136 43792 137 42298 138 40606 139 43404 140 46410 141 44802 142 42990 143 45940 144 49104 145 47378 146 45442 147 48548 148 51874 149 50026 150 47962 151 51228 152 54720 153 52746 154 50550 155 53980 156 57642 157 55538 158 53206 159 56804 160 60640 161 58402 162 55930 163 59700 164 63714 165 61338 166 58722 167 62668 168 66864 169 64346 170 61582 171 65708 172 70090 173 67426 174 64510 175 68820 176 73392 177 70578 178 67506 179 72004 180 76770 181 73802 182 70570 183 75260 184 80224 185 77098 186 73702 187 78588 188 83754 189 80466 190 76902 191 81988 192 87360 193 83906 194 80170 195 85460 196 91042 197 87418 198 83506 199 89004 200 94800 201 91002 202 86910 203 92620 204 98634 205 94658 206 90382 207 96308 208 102544 209 98386 210 93922 211 100068 212 106530 213 102186 214 97530 215 103900 216 110592 217 106058 218 101206 219 107804 220 114730 221 110002 222 104950 223 111780 224 118944 225 114018 226 108762 227 115828 228 123234 229 118106 230 112642 231 119948 232 127600 233 122266 234 116590 235 124140 236 132042 237 126498 238 120606 239 128404 240 136560 241 130802 242 124690 243 132740 244 141154 245 135178 246 128842 247 137148 248 145824 249 139626 250 133062 251 141628 252 150570 253 144146 254 137350 255 146180 256 155392 257 148738 258 141706 259 150804 260 160290 261 153402 262 146130 263 155500 264 165264 265 158138 266 150622 267 160268 268 170314 269 162946 270 155182 271 165108 272 175440 273 167826 274 159810 275 170020 276 180642 277 172778 278 164506 279 175004 280 185920 281 177802 282 169270 283 180060 284 191274 285 182898 286 174102 287 185188 288 196704 289 188066 290 179002 291 190388 292 202210 293 193306 294 183970 295 195660 296 207792 297 198618 298 189006 299 201004 300 213450 301 204002 302 194110 303 206420 304 219184 305 209458 306 199282 307 211908 308 224994 309 214986 310 204522 311 217468 312 230880 313 220586 314 209830 315 223100 316 236842 317 226258 318 215206 319 228804 320 242880 321 232002 322 220650 323 234580 324 248994 325 237818 326 226162 327 240428 328 255184 329 243706 330 231742 331 246348 332 261450 333 249666 334 237390 335 252340 336 267792 337 255698 338 243106 339 258404 340 274210 341 261802 342 248890 343 264540 344 280704 345 267978 346 254742 347 270748 348 287274 349 274226 350 260662 351 277028 352 293920 353 280546 354 266650 355 283380 356 300642 357 286938 358 272706 359 289804 360 307440 361 293402 362 278830 363 296300 364 314314 365 299938 366 285022 367 302868 368 321264 369 306546 370 291282 371 309508 372 328290 373 313226 374 297610 375 316220 376 335392 377 319978 378 304006 379 323004 380 342570 381 326802 382 310470 383 329860 384 349824 385 333698 386 317002 387 336788 388 357154 389 340666 390 323602 391 343788 392 364560 393 347706 394 330270 395 350860 396 372042 397 354818 398 337006 399 358004 400 379600 401 362002 402 343810 403 365220 404 387234 405 369258 406 350682 407 372508 408 394944 409 376586 410 357622 411 379868 412 402730 413 383986 414 364630 415 387300 416 410592 417 391458 418 371706 419 394804 420 418530 421 399002 422 378850 423 402380 424 426544 425 406618 426 386062 427 410028 428 434634 429 414306 430 393342 431 417748 432 442800 433 422066 434 400690 435 425540 436 451042 437 429898 438 408106 439 433404 440 459360 441 437802 442 415590 443 441340 444 467754 445 445778 446 423142 447 449348 448 476224 449 453826 450 430762 451 457428 452 484770 453 461946 454 438450 455 465580 456 493392 457 470138 458 446206 459 473804 460 502090 461 478402 462 454030 463 482100 464 510864 465 486738 466 461922 467 490468 468 519714 469 495146 470 469882 471 498908 472 528640 473 503626 474 477910 475 507420 476 537642 477 512178 478 486006 479 516004 480 546720 481 520802 482 494170 483 524660 484 555874 485 529498 486 502402 487 533388 488 565104 489 538266 490 510702 491 542188 492 574410 493 547106 494 519070 495 551060 496 583792 497 556018 498 527506 499 560004 500 593250 501 565002 502 536010 503 569020 504 602784 505 574058 506 544582 507 578108 508 612394 509 583186 510 553222 511 587268 512 622080 513 592386 514 561930 515 596500 516 631842 517 601658 518 570706 519 605804 520 641680 521 611002 522 579550 523 615180 524 651594 525 620418 526 588462 527 624628 528 661584 529 629906 530 597442 531 634148 532 671650 533 639466 534 606490 535 643740 536 681792 537 649098 538 615606 539 653404 540 692010 541 658802 542 624790 543 663140 544 702304 545 668578 546 634042 547 672948 548 712674 549 678426 550 643362 551 682828 552 723120 553 688346 554 652750 555 692780 556 733642 557 698338 558 662206 559 702804 560 744240 561 708402 562 671730 563 712900 564 754914 565 718538 566 681322 567 723068 568 765664 569 728746 570 690982 571 733308 572 776490 573 739026 574 700710 575 743620 576 787392 577 749378 578 710506 579 754004 580 798370 581 759802 582 720370 583 764460 584 809424 585 770298 586 730302 587 774988 588 820554 589 780866 590 740302 591 785588 592 831760 593 791506 594 750370 595 796260 596 843042 597 802218 598 760506 599 807004 600 854400 601 813002 602 770710 603 817820 604 865834 605 823858 606 780982 607 828708 608 877344 609 834786 610 791322 611 839668 612 888930 613 845786 614 801730 615 850700 616 900592 617 856858 618 812206 619 861804 620 912330 621 868002 622 822750 623 872980 624 924144 625 879218 626 833362 627 884228 628 936034 629 890506 630 844042 631 895548 632 948000 633 901866 634 854790 635 906940 636 960042 637 913298 638 865606 639 918404 640 972160 641 924802 642 876490 643 929940 644 984354 645 936378 646 887442 647 941548 648 996624 649 948026 650 898462 651 953228 652 1008970 653 959746 654 909550 655 964980 656 1021392 657 971538 658 920706 659 976804 660 1033890 661 983402 662 931930 663 988700 664 1046464 665 995338 666 943222 667 1000668 668 1059114 669 1007346 670 954582 671 1012708 672 1071840 673 1019426 674 966010 675 1024820 676 1084642 677 1031578 678 977506 679 1037004 680 1097520 681 1043802 682 989070 683 1049260 684 1110474 685 1056098 686 1000702 687 1061588 688 1123504 689 1068466 690 1012402 691 1073988 692 1136610 693 1080906 694 1024170 695 1086460 696 1149792 697 1093418 698 1036006 699 1099004 700 1163050 701 1106002 702 1047910 703 1111620 704 1176384 705 1118658 706 1059882 707 1124308 708 1189794 709 1131386 710 1071922 711 1137068 712 1203280 713 1144186 714 1084030 715 1149900 716 1216842 717 1157058 718 1096206 719 1162804 720 1230480 721 1170002 722 1108450 723 1175780 724 1244194 725 1183018 726 1120762 727 1188828 728 1257984 729 1196106 730 1133142 731 1201948 732 1271850 733 1209266 734 1145590 735 1215140 736 1285792 737 1222498 738 1158106 739 1228404 740 1299810 741 1235802 742 1170690 743 1241740 744 1313904 745 1249178 746 1183342 747 1255148 748 1328074 749 1262626 750 1196062 751 1268628 752 1342320 753 1276146 754 1208850 755 1282180 756 1356642 757 1289738 758 1221706 759 1295804 760 1371040 761 1303402 762 1234630 763 1309500 764 1385514 765 1317138 766 1247622 767 1323268 768 1400064 769 1330946 770 1260682 771 1337108 772 1414690 773 1344826 774 1273810 775 1351020 776 1429392 777 1358778 778 1287006 779 1365004 780 1444170 781 1372802 782 1300270 783 1379060 784 1459024 785 1386898 786 1313602 787 1393188 788 1473954 789 1401066 790 1327002 791 1407388 792 1488960 793 1415306 794 1340470 795 1421660 796 1504042 797 1429618 798 1354006 799 1436004 800 1519200 801 1444002 802 1367610 803 1450420 804 1534434 805 1458458 806 1381282 807 1464908 808 1549744 809 1472986 810 1395022 811 1479468 812 1565130 813 1487586 814 1408830 815 1494100 816 1580592 817 1502258 818 1422706 819 1508804 820 1596130 821 1517002 822 1436650 823 1523580 824 1611744 825 1531818 826 1450662 827 1538428 828 1627434 829 1546706 830 1464742 831 1553348 832 1643200 833 1561666 834 1478890 835 1568340 836 1659042 837 1576698 838 1493106 839 1583404 840 1674960 841 1591802 842 1507390 843 1598540 844 1690954 845 1606978 846 1521742 847 1613748 848 1707024 849 1622226 850 1536162 851 1629028 852 1723170 853 1637546 854 1550650 855 1644380 856 1739392 857 1652938 858 1565206 859 1659804 860 1755690 861 1668402 862 1579830 863 1675300 864 1772064 865 1683938 866 1594522 867 1690868 868 1788514 869 1699546 870 1609282 871 1706508 872 1805040 873 1715226 874 1624110 875 1722220 876 1821642 877 1730978 878 1639006 879 1738004 880 1838320 881 1746802 882 1653970 883 1753860 884 1855074 885 1762698 886 1669002 887 1769788 888 1871904 889 1778666 890 1684102 891 1785788 892 1888810 893 1794706 894 1699270 895 1801860 896 1905792 897 1810818 898 1714506 899 1818004 900 1922850 901 1827002 902 1729810 903 1834220 904 1939984 905 1843258 906 1745182 907 1850508 908 1957194 909 1859586 910 1760622 911 1866868 912 1974480 913 1875986 914 1776130 915 1883300 916 1991842 917 1892458 918 1791706 919 1899804 920 2009280 921 1909002 922 1807350 923 1916380 924 2026794 925 1925618 926 1823062 927 1933028 928 2044384 929 1942306 930 1838842 931 1949748 932 2062050 933 1959066 934 1854690 935 1966540 936 2079792 937 1975898 938 1870606 939 1983404 940 2097610 941 1992802 942 1886590 943 2000340 944 2115504 945 2009778 946 1902642 947 2017348 948 2133474 949 2026826 950 1918762 951 2034428 952 2151520 953 2043946 954 1934950 955 2051580 956 2169642 957 2061138 958 1951206 959 2068804 960 2187840 961 2078402 962 1967530 963 2086100 964 2206114 965 2095738 966 1983922 967 2103468 968 2224464 969 2113146 970 2000382 971 2120908 972 2242890 973 2130626 974 2016910 975 2138420 976 2261392 977 2148178 978 2033506 979 2156004 980 2279970 981 2165802 982 2050170 983 2173660 984 2298624 985 2183498 986 2066902 987 2191388 988 2317354 989 2201266 990 2083702 991 2209188 992 2336160 993 2219106 994 2100570 995 2227060 996 2355042 997 2237018 998 2117506 999 2245004 1000 2374000