9 1 10 0 11 0 12 9 13 0 14 0 15 36 16 0 17 0 18 93 19 0 20 0 21 198 22 0 23 0 24 378 25 0 26 0 27 624 28 9 29 0 30 918 31 72 32 0 33 1269 34 252 35 0 36 1597 37 576 38 0 39 1836 40 1134 41 0 42 2025 43 2025 44 0 45 2058 46 3096 47 36 48 1926 49 4356 50 252 51 1764 52 5877 53 756 54 1470 55 7182 56 1512 57 1134 58 8388 59 2772 60 882 61 9576 62 4608 63 588 64 10035 65 6552 66 462 67 10413 68 9108 69 756 70 10584 71 12096 72 1380 73 9972 74 14616 75 2256 76 9828 77 17928 78 3816 79 9450 80 20664 81 5805 82 8820 83 22320 84 7905 85 9018 86 25200 87 11340 88 9207 89 26208 90 14617 91 9522 92 27225 93 18060 94 9846 95 29808 96 23184 97 10458 98 30348 99 25704 100 10845 101 32580 102 29652 103 11592 104 34848 105 34776 106 13806 107 36540 108 36540 109 14436 110 38844 111 42744 112 17262 113 39636 114 47124 115 20421 116 41211 117 51408 118 20916 119 40302 120 59220 121 26838 122 40644 123 63588 124 29862 125 39888 126 72648 127 34092 128 35667 129 78708 130 42030 131 36486 132 85836 133 44352 134 32760 135 92484 136 54945 137 31572 138 93156 139 61992 140 34848 141 100296 142 71856 143 33012 144 96264 145 86382 146 38628 147 95388 148 93402 149 39384 150 97356 151 111456 152 42723 153 89964 154 116118 155 51354 156 93744 157 127638 158 53064 159 91224 160 142038 161 67113 162 91548 163 139608 164 69822 165 94584 166 155610 167 79632 168 92418 169 155736 170 94509 171 100044 172 160524 173 94005 174 96924 175 171144 176 118458 177 100464 178 171864 179 123426 180 101179 181 187362 182 132912 183 90024 184 190134 185 151902 186 100296 187 203868 188 151956 189 93312 190 210042 191 177606 192 94656 193 209160 194 187632 195 108537 196 222300 197 207225 198 100548 199 206892 200 228645 201 116592 202 207396 203 239220 204 122796 205 209664 206 269964 207 134388 208 188748 209 273294 210 158352 211 193104 212 299250 213 162948 214 185976 215 317142 216 188127 217 179172 218 306432 219 195300 220 191268 221 330372 222 217812 223 191772 224 322182 225 247944 226 207648 227 316512 228 250671 229 211302 230 331254 231 293388 232 215658 233 320796 234 296928 235 227556 236 336870 237 301968 238 220410 239 342540 240 340704 241 250110 242 351288 243 332388 244 245331 245 367677 246 367992 247 239796 248 365778 249 379530 250 272862 251 394380 252 384345 253 249012 254 380772 255 419778 256 284652 257 387072 258 417132 259 310104 260 404082 261 463626 262 313056 263 351918 264 465894 265 360774 266 371772 267 496356 268 348246 269 365472 270 529932 271 393372 272 350784 273 490644 274 412218 275 393318 276 549234 277 438804 278 380016 279 523152 280 488457 281 411273 282 509292 283 457776 284 422865 285 547842 286 528192 287 443268 288 508368 289 506268 290 494433 291 541440 292 510624 293 487620 294 533733 295 580428 296 545706 297 547920 298 528192 299 513702 300 585288 301 578088 302 512640 303 593952 304 568080 305 575514 306 667242 307 567504 308 520038 309 649350 310 614988 311 580752 312 687162 313 599400 314 587286 315 718009 316 663714 317 558684 318 651177 319 653508 320 615006 321 729738 322 703584 323 600012 324 720960 325 746253 326 661500 327 684684 328 707688 329 675360 330 737550 331 823284 332 683244 333 699792 334 794376 335 717948 336 741897 337 785268 338 677628 339 781734 340 870984 341 768474 342 814254 343 794052 344 740070 345 872298 346 839484 347 728856 348 855876 349 845928 350 829206 351 916776 352 855792 353 722358 354 890820 355 941292 356 793170 357 911340 358 939240 359 822528 360 992490 361 1036620 362 793422 363 859572 364 1024083 365 891954 366 913245 367 1093932 368 836082 369 910716 370 1182150 371 927108 372 831819 373 1100232 374 924282 375 947706 376 1248102 377 964098 378 905520 379 1182888 380 1068903 381 954648 382 1095570 383 998424 384 959070 385 1200798 386 1208718 387 957390 388 1120770 389 1154736 390 1053108 391 1181016 392 1147680 393 995514 394 1198800 395 1316520 396 1129053 397 1204128 398 1160280 399 1046430 400 1262979 401 1266804 402 1031172 403 1250244 404 1277892 405 1190826 406 1390554 407 1267308 408 1019088 409 1349208 410 1354572 411 1166454 412 1404828 413 1294524 414 1206396 415 1455300 416 1434276 417 1128246 418 1261512 419 1412712 420 1264566 421 1410264 422 1550376 423 1199856 424 1382976 425 1653696 426 1313298 427 1261476 428 1541052 429 1303218 430 1387278 431 1776924 432 1329798 433 1309644 434 1649664 435 1455120 436 1349028 437 1600776 438 1375236 439 1401876 440 1793178 441 1625484 442 1447110 443 1619352 444 1549629 445 1542501 446 1659429 447 1547388 448 1470618 449 1651437 450 1811208 451 1592766 452 1655145 453 1577520 454 1532736 455 1740960 456 1747620 457 1543752 458 1743921 459 1782900 460 1738044 461 1915776 462 1664580 463 1483029 464 1845900 465 1789200 466 1649430 467 1956528 468 1675509 469 1727478 470 2059632 471 1863792 472 1557180 473 1872864 474 1835568 475 1804014 476 2122992 477 1933962 478 1720656 479 1999188 480 2087082 481 1792476 482 1802952 483 1920249 484 1796958 485 2028834 486 2309526 487 1783665 488 1907766 489 2164428 490 1986336 491 1946520 492 2157624 493 1809936 494 2017710 495 2469768 496 2071512 497 2035350 498 2113776 499 1964718 500 2126889 501 2243640 502 1950480 503 2069496 504 2257543 505 2345814 506 2306304 507 2213148 508 1982178 509 2226672 510 2315400 511 2248920 512 2233296 513 2233620 514 2300958 515 2395512 516 2508690 517 2057706 518 2067624 519 2397738 520 2323314 521 2360250 522 2618100 523 2181816 524 2399049 525 2785260 526 2395710 527 2124864 528 2542596 529 2281050 530 2428974 531 2954238 532 2319435 533 2306052 534 2710920 535 2553849 536 2338758 537 2603076 538 2335788 539 2416446 540 2933700 541 2886858 542 2425500 543 2620296 544 2703834 545 2553084 546 2633544 547 2743344 548 2307312 549 2686896 550 3211362 551 2578158 552 2752722 553 2697660 554 2523096 555 2809758 556 3035088 557 2522844 558 2805672 559 3055500 560 2925144 561 3067668 562 2875572 563 2451960 564 2883972 565 3015432 566 2803257 567 2983236 568 2861856 569 2941344 570 3167976 571 3185856 572 2652930 573 2878344 574 2986704 575 3121434 576 3193038 577 3225996 578 2932776 579 3053520 580 3452688 581 3011094 582 2736792 583 3174444 584 2916144 585 3166116 586 3785292 587 2929896 588 3054312 589 3479184 590 3284478 591 3015576 592 3432699 593 2935872 594 3169152 595 3830400 596 3480048 597 3150000 598 3272040 599 3316158 600 3224376 601 3427200 602 3311928 603 3085224 604 3523212 605 3992760 606 3483396 607 3454668 608 3386988 609 3380052 610 3455244 611 3909150 612 3230700 613 3412485 614 3963708 615 3601917 616 3801744 617 3516660 618 3131172 619 3554280 620 3879540 621 3641526 622 3842568 623 3582324 624 3841422 625 4059720 626 3865302 627 3399876 628 3637782 629 3569904 630 4023870 631 4099104 632 3747348 633 3752772 634 3833496 635 4128138 636 3799278 637 3701628 638 3688146 639 3926916 640 4230333 641 4511754 642 3921828 643 3820644 644 4142583 645 4168980 646 3798972 647 4179492 648 3614328 649 4008186 650 4794498 651 4163256 652 4099032 653 4012092 654 4057848 655 4152330 656 4484718 657 3994272 658 4134096 659 4418568 660 4776576 661 4517982 662 4113522 663 4088952 664 4164624 665 4235382 666 4742640 667 4133052 668 4170861 669 4846536 670 4596228 671 4662756 672 4305744 673 4202613 674 4240278 675 4956294 676 4643739 677 4631454 678 4511880 679 4634244 680 4905432 681 4598496 682 4229721 683 4408362 684 4405170 685 4990770 686 5204502 687 4478616 688 4820085 689 4840920 690 4896684 691 4820328 692 4771125 693 4231740 694 5156928 695 5230890 696 5119860 697 5000004 698 4543128 699 4864482 700 5062590 701 4807674 702 4885062 703 4648212 704 5095206 705 5788650 706 5206320 707 5041341 708 4842882 709 5044932 710 5027670 711 5556726 712 4700421 713 5058216 714 5443650 715 5521644 716 5564790 717 4860744 718 4902300 719 5135130 720 5436381 721 5582556 722 5432724 723 5069904 724 5799348 725 5905116 726 5460840 727 5149116 728 5231799 729 4966740 730 6103944 731 5694192 732 5375430 733 5509224 734 5573745 735 5888727 736 5573862 737 5373900 738 5180364 739 5649966 740 6157368 741 6342966 742 5437404 743 5739264 744 5818806 745 5718204 746 5822712 747 5778360 748 4873122 749 6220872 750 6522378 751 5900724 752 6111756 753 5580108 754 5751036 755 6087060 756 6301819 757 5605632 758 5938128 759 6206802 760 6746823 761 6372576 762 5868522 763 5715180 764 5875146 765 6083028 766 6718896 767 5656896 768 6119400 769 6692184 770 6466770 771 6751152 772 6064632 773 5817744 774 6146856 775 7046802 776 6289614 777 6692520 778 6198696 779 6494292 780 7020300 781 6439356 782 6087186 783 6139224 784 6180696 785 7228818 786 6956712 787 6427584 788 6700248 789 6676992 790 6992568 791 6751404 792 6527385 793 6015996 794 7107156 795 7070730 796 7405524 797 6577200 798 6452820 799 6951168 800 6866748 801 6858306 802 6910596 803 6277320 804 7207326 805 8045856 806 7163874 807 7037970 808 6846912 809 6872508 810 7119630 811 7743024 812 6339393 813 7167384 814 7389900 815 7748640 816 7620480 817 6805926 818 6874632 819 6918786 820 7554474 821 7942860 822 6971580 823 7131348 824 8187561 825 7611732 826 7675614 827 7403580 828 6612408 829 7031502 830 8742456 831 7176582 832 7703172 833 7535376 834 7504380 835 8135694 836 7876638 837 7239969 838 7092540 839 7999488 840 8271150 841 8470098 842 7611192 843 7645140 844 7826112 845 8094132 846 7989912 847 7565112 848 7010883 849 8601264 850 8257860 851 8546598 852 8129508 853 7332012 854 8135712 855 8507592 856 8118306 857 7930260 858 8072976 859 8040312 860 9431388 861 8488008 862 7816536 863 7997220 864 7918350 865 8287038 866 9189180 867 7551924 868 8311248 869 8842302 870 9078528 871 8781066 872 8195292 873 8113956 874 8033328 875 9309708 876 8916480 877 8474256 878 8053740 879 9336312 880 8964432 881 8596548 882 8768244 883 7770924 884 8325018 885 10280076 886 8716932 887 8762112 888 9164484 889 8750088 890 9352800 891 9596328 892 8277201 893 8136072 894 9894600 895 9145980 896 9907011 897 8813142 898 8705412 899 9025884 900 9428514 901 9501912 902 8735076 903 8513829 904 10083348 905 9913050 906 9671148 907 9551700 908 8560314 909 9128016 910 10106748 911 9570204 912 8710128 913 9761724 914 9174564 915 10643544 916 10064394 917 8880264 918 9238188 919 9517536 920 9870354 921 10607622 922 9341388 923 9312912 924 10526334 925 10420344 926 10048068 927 9666468 928 8952084 929 9525672 930 11119362 931 9765720 932 10250856 933 9303000 934 10401624 935 10743840 936 10196550 937 9910152 938 9319752 939 10185966 940 11355318 941 10735704 942 9751884 943 10334592 944 10136142 945 10540980 946 11136888 947 9514512 948 9383892 949 11441556 950 10667538 951 11394558 952 10241010 953 10024452 954 10501848 955 11140038 956 10937448 957 10249668 958 10171989 959 10929636 960 12043581 961 10709631 962 10665162 963 10141488 964 10158615 965 11586078 966 11523192 967 9905436 968 11286324 969 11062548 970 11899287 971 11706408 972 10587042 973 10299420 974 11122776 975 11806746 976 11730681 977 11090781 978 10395084 979 12018132 980 11576817 981 11540034 982 11359404 983 9899568 984 11375532 985 13086936 986 11001906 987 11803068 988 11175264 989 11300310 990 12379626 991 12268188 992 10629108 993 10920672 994 12245652 995 12001131 996 12806922 997 11014794 998 11405088 999 11720100 1000 12367026