0 1 1 1 2 0 3 1 4 1 5 0 6 1 7 2 8 1 9 0 10 1 11 2 12 5 13 1 14 0 15 1 16 2 17 8 18 8 19 1 20 0 21 1 22 2 23 9 24 19 25 13 26 1 27 0 28 1 29 2 30 9 31 27 32 42 33 18 34 1 35 0 36 1 37 2 38 9 39 30 40 74 41 78 42 25 43 1 44 0 45 1 46 2 47 9 48 31 49 95 50 168 51 139 52 32 53 1 54 0 55 1 56 2 57 9 58 31 59 105 60 248 61 363 62 224 63 41 64 1 65 0 66 1 67 2 68 9 69 31 70 108 71 300 72 614 73 703 74 350 75 50 76 1 77 0 78 1 79 2 80 9 81 31 82 109 83 325 84 814 85 1367 86 1297 87 517 88 61 89 1 90 0 91 1 92 2 93 9 94 31 95 109 96 335 97 938 98 1996 99 2879 100 2247 101 744 102 72 103 1 104 0 105 1 106 2 107 9 108 31 109 109 110 338 111 1002 112 2457 113 4642 114 5674 115 3742 116 1032 117 85 118 1 119 0 120 1 121 2 122 9 123 31 124 109 125 339 126 1029 127 2741 128 6128 129 10105 130 10681 131 5967 132 1405 133 98 134 1 135 0 136 1 137 2 138 9 139 31 140 109 141 339 142 1039 143 2889 144 7168 145 14358 146 20975 147 19169 148 9241 149 1862 150 113 151 1 152 0 153 1 154 2 155 9 156 31 157 109 158 339 159 1042 160 2957 161 7797 162 17685 163 32123 164 41455 165 33203 166 13859 167 2432 168 128 169 1 170 0 171 1 172 2 173 9 174 31 175 109 176 339 177 1043 178 2984 179 8135 180 19928 181 41801 182 68488 183 78849 184 55478 185 20307 186 3115 187 145 188 1 189 0 190 1 191 2 192 9 193 31 194 109 195 339 196 1043 197 2994 198 8295 199 21280 200 48965 201 94377 202 140478 203 144371 204 90067 205 29052 206 3942 207 162 208 1 209 0 210 1 211 2 212 9 213 31 214 109 215 339 216 1043 217 2997 218 8365 219 22013 220 53688 221 115275 222 205277 223 277278 224 256079 225 142224 226 40786 227 4914 228 181 229 1 230 0 231 1 232 2 233 9 234 31 235 109 236 339 237 1043 238 2998 239 8392 240 22377 241 56517 242 130174 243 262034 244 430087 245 529624 246 440704 247 219388 248 56187 249 6067 250 200 251 1 252 0 253 1 254 2 255 9 256 31 257 109 258 339 259 1043 260 2998 261 8402 262 22541 263 58077 264 139820 265 305539 266 574803 267 872302 268 980476 269 738772 270 330943 271 76233 272 7400 273 221 274 1 275 0 276 1 277 2 278 9 279 31 280 109 281 339 282 1043 283 2998 284 8405 285 22611 286 58868 287 145597 288 335683 289 693598 290 1222170 291 1714941 292 1765492 293 1208149 294 489716 295 101858 296 8954 297 242 298 1 299 0 300 1 301 2 302 9 303 31 304 109 305 339 306 1043 307 2998 308 8406 309 22638 310 59244 311 148810 312 354987 313 781194 314 1528901 315 2521350 316 3278477 317 3097071 318 1932864 319 711518 320 134377 321 10729 322 265 323 1 324 0 325 1 326 2 327 9 328 31 329 109 330 339 331 1043 332 2998 333 8406 334 22648 335 59410 336 150484 337 366531 338 840679 339 1768732 340 3274785 341 5060938 342 6103521 343 5306548 344 3029214 345 1017241 346 175068 347 12768 348 288 349 1 350 0 351 1 352 2 353 9 354 31 355 109 356 339 357 1043 358 2998 359 8406 360 22651 361 59480 362 151301 363 373028 364 878434 365 1940610 366 3897957 367 6832548 368 9896451 369 11091375 370 8893500 371 4660063 372 1432328 373 225640 374 15072 375 313 376 1 377 0 378 1 379 2 380 9 381 31 382 109 383 339 384 1043 385 2998 386 8406 387 22652 388 59507 389 151681 390 376471 391 901054 392 2055537 393 4367759 394 8379854 395 13900570 396 18891871 397 19700943 398 14607217 399 7045203 400 1989400 401 287772 402 17689 403 338 404 1 405 0 406 1 407 2 408 9 409 31 410 109 411 339 412 1043 413 2998 414 8406 415 22652 416 59517 417 151847 418 378205 419 913884 420 2128102 421 4697170 422 9604328 423 17588233 424 27626151 425 35249977 426 34265319 427 23542097 428 10483231 429 2727644 430 363673 431 20618 432 365 433 1 434 0 435 1 436 2 437 9 438 31 439 109 440 339 441 1043 442 2998 443 8406 444 22652 445 59520 446 151917 447 379034 448 920809 449 2171631 450 4915009 451 10501926 452 20646864 453 36098456 454 53692474 455 64390786 456 58429093 457 37285849 458 15368227 459 3696314 460 455482 461 23912 462 392 463 1 464 0 465 1 466 2 467 9 468 31 469 109 470 339 471 1043 472 2998 473 8406 474 22652 475 59521 476 151944 477 379416 478 924370 479 2196551 480 5052010 481 11121074 482 22986139 483 43455087 484 72515255 485 102193925 486 115284416 487 97816791 488 58094004 489 22222681 490 4953733 491 565977 492 27571 493 421 494 1 495 0 496 1 497 2 498 9 499 31 500 109 501 339 502 1043 503 2998 504 8406 505 22652 506 59521 507 151954 508 379582 509 926130 510 2210183 511 5134419 512 11527059 513 24664511 514 49316969 515 89610005 516 142752387 517 190678199 518 202560300 519 160944051 520 89148980 521 31722589 522 6571851 523 697875 524 31650 525 450 526 1 527 0 528 1 529 2 530 9 531 31 532 109 533 339 534 1043 535 2998 536 8406 537 22652 538 59521 539 151957 540 379652 541 926963 542 2217348 543 5181942 544 11781881 545 25807608 546 53683234 547 103786605 548 181249495 549 275637170 550 349172204 551 349637130 552 260558245 553 134862913 554 44745412 555 8635136 556 854594 557 36150 558 481 559 1 560 0 561 1 562 2 563 9 564 31 565 109 566 339 567 1043 568 2998 569 8406 570 22652 571 59521 572 151958 573 379679 574 927345 575 2220969 576 5208302 577 11935558 578 26552676 579 56763846 580 114734313 581 214450024 582 359860453 583 522556363 584 628122125 585 593499173 586 415434960 587 201312513 588 62407716 589 11245971 590 1039500 591 41131 592 512 593 1 594 0 595 1 596 2 597 9 598 31 599 109 600 339 601 1043 602 2998 603 8406 604 22652 605 59521 606 151958 607 379689 608 927511 609 2222741 610 5222384 611 12024875 612 27019758 613 58841925 614 122721149 615 241005379 616 435349240 617 701965823 618 973479621 619 1111050987 620 991625986 621 652940560 622 296746270 623 86132422 624 14523411 625 1256787 626 46592 627 545 628 1 629 0 630 1 631 2 632 9 633 31 634 109 635 339 636 1043 637 2998 638 8406 639 22652 640 59521 641 151958 642 379692 643 927581 644 2223576 645 5229669 646 12074970 647 27302392 648 60190387 649 128283353 650 261011238 651 497842227 652 868998639 653 1346276798 654 1783587678 655 1934048642 656 1632248998 657 1012418264 658 432288197 659 117703074 660 18610003 661 1510547 662 52598 663 578 664 1 665 0 666 1 667 2 668 9 669 31 670 109 671 339 672 1043 673 2998 674 8406 675 22652 676 59521 677 151958 678 379693 679 927608 680 2223958 681 5233316 682 12102178 683 27467767 684 61035671 685 132007653 686 275369819 687 546413060 688 1012036872 689 1706639000 690 2540512664 691 3216317682 692 3315905471 693 2648936320 694 1549884617 695 622756805 696 159357465 697 23669939 698 1805833 699 59149 700 613 701 1 702 0 703 1 704 2 705 9 706 31 707 109 708 339 709 1043 710 2998 711 8406 712 22652 713 59521 714 151958 715 379693 716 927618 717 2224124 718 5235092 719 12116504 720 27561552 721 61548817 722 134417127 723 285267523 724 582293218 725 1126649564 726 2025719643 727 3299882491 728 4720228418 729 5712745966 730 5603441375 731 4241607523 732 2344153951 733 887772827 734 213863183 735 29897469 736 2147607 737 66312 738 648 739 1 740 0 741 1 742 2 743 9 744 31 745 109 746 339 747 1043 748 2998 749 8406 750 22652 751 59521 752 151958 753 379693 754 927621 755 2224194 756 5235927 757 12123849 758 27613173 759 61851147 760 135928105 761 291857913 762 607712692 763 1213711771 764 2289164775 765 3994857895 766 6285512415 767 8640703441 768 10000978395 769 9339723645 770 6705867270 771 3505141354 772 1253040268 773 284644763 774 37514880 775 2541870 776 74088 777 685 778 1 779 0 780 1 781 2 782 9 783 31 784 109 785 339 786 1043 787 2998 788 8406 789 22652 790 59521 791 151958 792 379693 793 927622 794 2224221 795 5236309 796 12127508 797 27640841 798 62024238 799 136848733 800 296112961 801 625095457 802 1277023901 803 2494803570 804 4585868244 805 7765748283 806 11801165906 807 15593369747 808 17267743116 809 15364504830 810 10474314965 811 5184546097 812 1752042943 813 375888134 814 46782198 815 2994543 816 82549 817 722 818 1 819 0 820 1 821 2 822 9 823 31 824 109 825 339 826 1043 827 2998 828 8406 829 22652 830 59521 831 151958 832 379693 833 927622 834 2224231 835 5236475 836 12129286 837 27655287 838 62120759 839 137394525 840 298784144 841 636620878 842 1321417365 843 2648159993 844 5059679193 845 9061902863 846 14888560567 847 21851533830 848 27758244790 849 29422753723 850 24961855396 851 16173212478 852 7590054618 853 2427998488 854 492709247 855 57994976 856 3512737 857 91694 858 761 859 1 860 0 861 1 862 2 863 9 864 31 865 109 866 339 867 1043 868 2998 869 8406 870 22652 871 59521 872 151958 873 379693 874 927622 875 2224234 876 5236545 877 12130121 878 27662658 879 62173250 880 137709907 881 300417506 882 644053794 883 1351585270 884 2758284923 885 5421789067 886 10128730644 887 17671532954 888 28165234727 889 39924580625 890 48768651224 891 49503511401 892 40073255710 893 24700700855 894 11003402527 895 3336392381 896 641295272 897 71496023 898 4103423 899 101600 900 800 901 1 902 0 903 1 904 2 905 9 906 31 907 109 908 339 909 1043 910 2998 911 8406 912 22652 913 59521 914 151958 915 379693 916 927622 917 2224235 918 5236572 919 12130503 920 27666321 921 62201164 922 137887758 923 301391886 924 648726349 925 1371526394 926 2834868815 927 5687846815 928 10963837865 929 20022501227 930 34022574165 931 52597886266 932 72013039016 933 84608677119 934 82285808163 935 63604318283 936 37332426796 937 15803961277 938 4547887512 939 829126706 940 87672326 941 4774923 942 112267 943 841 944 1 945 0 946 1 947 2 948 9 949 31 950 109 951 339 952 1043 953 2998 954 8406 955 22652 956 59521 957 151958 958 379693 959 927622 960 2224235 961 5236582 962 12130669 963 27668099 964 62215670 965 137985851 966 301959602 967 651594306 968 1384380052 969 2886659590 970 5876969045 971 11591211503 972 21906751003 973 39099961413 974 64696259111 975 97007391317 976 128292152163 977 145019803527 978 135198479984 979 99859584615 980 55864732241 981 22498414878 982 6152034088 983 1065163328 984 106969083 985 5535432 986 123774 987 882 988 1 989 0 990 1 991 2 992 9 993 31 994 109 995 339 996 1043 997 2998 998 8406 999 22652 1000 59521 1001 151958 1002 379693 1003 927622 1004 2224235 1005 5236585 1006 12130739 1007 27668934 1008 62223053 1009 138038806 1010 302283216 1011 653315100 1012 1392474574 1013 2920818061 1014 6007629992 1015 12046632305 1016 23353328072 1017 43265285194 1018 75455744001 1019 121556095194 1020 176769222364 1021 225839417655 1022 245687410326 1023 219676313038 1024 155156667404 1025 82805264671 1026 31758924955 1027 8261506191 1028 1360132044 1029 129886383 1030 6394586 1031 136122 1032 925 1033 1 1034 0 1035 1 1036 2 1037 9 1038 31 1039 109 1040 339 1041 1043 1042 2998 1043 8406 1044 22652 1045 59521 1046 151958 1047 379693 1048 927622 1049 2224235 1050 5236586 1051 12130766 1052 27669316 1053 62226718 1054 138066840 1055 302463891 1056 654325758 1057 1397461379 1058 2942837200 1059 6095659650 1060 12367712298 1061 24424955714 1062 46531895205 1063 84488515219 1064 143951298311 1065 225747822979 1066 318380187329 1067 393003466073 1068 411598679344 1069 353147677332 1070 238682547108 1071 121627287959 1072 44470651305 1073 11017427723 1074 1726771002 1075 156994999 1076 7361907 1077 149395 1078 968 1079 1 1080 0