1 1 2 1 3 0 4 0 5 1 6 0 7 0 8 2 9 0 10 0 11 0 12 1 13 1 14 1 15 0 16 0 17 2 18 1 19 2 20 1 21 0 22 0 23 1 24 2 25 4 26 1 27 2 28 1 29 0 30 2 31 1 32 7 33 4 34 4 35 4 36 1 37 0 38 1 39 2 40 7 41 7 42 9 43 10 44 8 45 3 46 0 47 2 48 3 49 12 50 10 51 17 52 19 53 20 54 17 55 6 56 0 57 1 58 2 59 12 60 14 61 28 62 37 63 45 64 46 65 35 66 15 67 0 68 2 69 1 70 18 71 21 72 46 73 60 74 87 75 106 76 103 77 78 78 29 79 0 80 1 81 4 82 16 83 24 84 61 85 99 86 152 87 211 88 252 89 245 90 169 91 67 92 0 93 2 94 3 95 24 96 33 97 91 98 148 99 253 100 385 101 528 102 613 103 561 104 379 105 139 106 0 107 1 108 2 109 21 110 35 111 109 112 209 113 400 114 652 115 997 116 1346 117 1481 118 1331 119 847 120 310 121 0 122 2 123 3 124 34 125 47 126 163 127 286 128 606 129 1047 130 1766 131 2627 132 3387 133 3640 134 3122 135 1923 136 667 137 0 138 1 139 3 140 25 141 52 142 175 143 382 144 845 145 1626 146 2921 147 4799 148 6904 149 8664 150 8937 151 7439 152 4376 153 1480 154 0 155 2 156 3 157 37 158 67 159 247 160 510 161 1222 162 2398 163 4669 164 8207 165 13048 166 18289 167 22081 168 22111 169 17682 170 10050 171 3244 172 0 173 1 174 4 175 32 176 66 177 273 178 622 179 1596 180 3431 181 7096 182 13435 183 23090 184 35738 185 48378 186 56651 187 54766 188 42376 189 23159 190 7241 191 0 192 2 193 2 194 47 195 79 196 372 197 816 198 2209 199 4811 200 10576 201 20990 202 38993 203 65225 204 97696 205 128395 206 145256 207 136164 208 101636 209 53692 210 16104 211 0 212 1 213 4 214 37 215 82 216 367 217 960 218 2732 219 6483 220 15050 221 31949 222 62714 223 113352 224 183953 225 267583 226 340562 227 373568 228 339045 229 244945 230 124926 231 36192 232 0 233 2 234 5 235 58 236 111 237 517 238 1237 239 3690 240 8750 241 21302 242 46920 243 97965 244 187568 245 328948 246 519006 247 731746 248 904163 249 960903 250 846175 251 591333 252 291922 253 81435 254 0 255 1 256 2 257 42 258 101 259 507 260 1376 261 4382 262 11283 263 28836 264 67336 265 147664 266 300235 267 559884 268 953971 269 1461324 270 2001042 271 2399463 272 2475077 273 2114604 274 1432118 275 684374 276 184452 277 0 278 2 279 1 280 61 281 125 282 686 283 1738 284 5779 285 14779 286 39422 287 94471 288 217677 289 464015 290 919495 291 1667968 292 2759180 293 4109536 294 5464498 295 6367694 296 6376942 297 5292375 298 3474733 299 1609850 300 418870 301 0 302 1 303 6 304 47 305 131 306 681 307 1946 308 6632 309 18360 310 51119 311 129731 312 311760 313 699256 314 1456744 315 2807590 316 4952264 317 7964502 318 11532755 319 14909780 320 16889847 321 16440346 322 13259811 323 8450187 324 3797534 325 955860 326 0 327 2 328 6 329 72 330 151 331 897 332 2421 333 8585 334 23596 335 67875 336 175630 337 440304 338 1025991 339 2246911 340 4557519 341 8541124 342 14659982 343 22925925 344 32306499 345 40625708 346 44780436 347 42391836 348 33256903 349 20584553 350 8982860 351 2187664 352 0 353 1 354 2 355 55 356 136 357 840 358 2571 359 9626 360 28311 361 85344 362 232256 363 605459 364 1475981 365 3371622 366 7188197 367 14195972 368 25888433 369 43245858 370 65827476 371 90311443 372 110563926 373 118654495 374 109336142 375 83481556 376 50233508 377 21300260 378 5025990 379 0 380 2 381 3 382 84 383 179 384 1160 385 3230 386 12421 387 35815 388 110826 389 305973 390 826181 391 2079413 392 4957148 393 11027046 394 22894530 395 44025058 396 78150338 397 127155185 398 188492714 399 251963221 400 300493183 401 314208392 402 282010207 403 209718955 404 122767251 405 50624387 406 11580130 407 0 408 1 409 4 410 60 411 167 412 1051 413 3381 414 13478 415 42061 416 135308 417 392719 418 1098753 419 2880397 420 7125646 421 16544781 422 35886642 423 72553010 424 135894001 425 235000394 426 372602974 427 538328919 428 701530045 429 815626429 430 831486690 431 727421411 432 527191619 433 300468845 434 120572569 435 26765230 436 0 437 2 438 3 439 87 440 208 441 1391 442 4162 443 17091 444 52364 445 172605 446 506080 447 1458898 448 3929247 449 10081548 450 24278568 451 54952695 452 116143559 453 228740911 454 417579624 455 703855451 456 1088279480 457 1533384992 458 1949380878 459 2210868617 460 2198846686 461 1876217665 462 1326038325 463 736315133 464 287738099 465 62027433 466 0 467 1 468 6 469 69 470 201 471 1333 472 4343 473 18494 474 60209 475 206314 476 632765 477 1887401 478 5274827 479 13995607 480 34989224 481 82257702 482 181414797 483 373749861 484 717524093 485 1277345501 486 2100099412 487 3168319599 488 4356572130 489 5406231659 490 5985011804 491 5810641193 492 4838913920 493 3337070289 494 1806548219 495 687924381 496 144133676 497 0 498 2 499 3 500 99 501 222 502 1723 503 5242 504 23135 505 74113 506 259193 507 800738 508 2451206 509 7007573 510 19194251 511 49535594 512 120828531 513 276885525 514 595308445 515 1196024053 516 2239481431 517 3890269267 518 6242553083 519 9195181513 520 12346564398 521 14964557751 522 16180713116 523 15344125348 524 12478340059 525 8401815690 526 4437158840 527 1647518696 528 335731381 529 0 530 1 531 4 532 72 533 215 534 1549 535 5385 536 24323 537 83531 538 303232 539 979818 540 3096179 541 9166638 542 25879705 543 69072192 544 174216663 545 414280506 546 925982019 547 1941688724 548 3806272449 549 6955838431 550 11797635902 551 18488798915 552 26605377450 553 34905217706 554 41344941581 555 43689225249 556 40489846600 557 32173734225 558 21161919068 559 10909424344 560 3951989952 561 783859852 562 0 563 2 564 6 565 110 566 287 567 2102 568 6689 569 30671 570 102334 571 376888 572 1221860 573 3946523 574 11913515 575 34592167 576 94930374 577 247347362 578 608259381 579 1410878441 580 3076670208 581 6295627277 582 12048782301 583 21502853169 584 35630507556 585 54566296799 586 76754160807 587 98447778576 588 114023362707 589 117815842627 590 106767225780 591 82940926701 592 53320277931 593 26847465150 594 9494140486 595 1834104934 596 0 597 1 598 2 599 78 600 229 601 1865 602 6580 603 31766 604 113215 605 433440 606 1466428 607 4886396 608 15235674 609 45510973 610 128758583 611 345709000 612 878493166 613 2108398316 614 4771760157 615 10157566379 616 20295389760 617 37943341602 618 66170175508 619 107181200010 620 160496193094 621 220799964944 622 277030045133 623 313906392623 624 317321347926 625 281332104228 626 213772866011 627 134390103152 628 66127717044 629 22840697400 630 4300433063 631 0 632 2 633 3 634 119 635 281 636 2449 637 7989 638 39390 639 136903 640 532607 641 1804601 642 6131645 643 19439742 644 59525931 645 172628411 646 477094807 647 1249000837 648 3097381356 649 7255145456 650 16030408793 651 33328527319 652 65062499119 653 118894386479 654 202728576154 655 321180565546 656 470521841836 657 633438212592 658 777829644209 659 862710053441 660 853636862314 661 740788109587 662 550864984211 663 338816813381 664 163010147469 665 55022677726 666 10102854473 667 0 668 1 669 7 670 87 671 293 672 2248 673 8211 674 40858 675 150761 676 604160 677 2132945 678 7457621 679 24386736 680 76671682 681 228688326 682 649528878 683 1751287772 684 4477029211 685 10836886056 686 24788388253 687 53501159219 688 108703899231 689 207457005291 690 370763754635 691 618481202952 692 958901986969 693 1375060819700 694 1812421202774 695 2179271656110 696 2367067201184 697 2293713247377 698 1949243993902 699 1419195868906 700 854420809041 701 402137245808 702 132714822287 703 23778351222 704 0 705 2 706 5 707 127 708 330 709 2880 710 9772 711 50104 712 180936 713 734942 714 2595914 715 9234072 716 30627726 717 98451567 718 300204302 719 875078002 720 2423348196 721 6379016412 722 15920122491 723 37634997754 724 84109384421 725 177431133994 726 352512031158 727 658072641978 728 1150864013868 729 1879165526749 730 2852686967104 731 4006273902656 732 5172551064864 733 6093103361658 734 6484255894756 735 6156166873405 736 5125556565639 737 3655442558123 738 2155143758495 739 992751161560 740 320488613032 741 56063415268 742 0 743 1 744 2 745 92 746 279 747 2535 748 9541 749 50946 750 195229 751 822429 752 3020222 753 11059204 754 37774774 755 124502049 756 389677491 757 1164822616 758 3313304302 759 8964494284 760 23040257220 761 56172669648 762 129755414282 763 283488147139 764 584850636198 765 1136828111634 766 2077088228984 767 3556459810014 768 5687200083257 769 8457591992147 770 11638172796759 771 14725859928504 772 17001873525007 773 17735180247676 774 16504435575562 775 13468643832806 776 9413161587169 777 5437104900349 778 2452415377180 779 774806651825 780 132404269770 781 0 782 2 783 3 784 140 785 366 786 3400 787 11756 788 63272 789 234575 790 996139 791 3645484 792 13538730 793 46802910 794 157349778 795 502328135 796 1537297585 797 4479794455 798 12444979704 799 32878157528 800 82554318759 801 196702247590 802 444238774470 803 949352489815 804 1916494710461 805 3646715230499 806 6524607786187 807 10943447780565 808 17147138579606 809 24992414110785 810 33713280578697 811 41823950946290 812 47349520193944 813 48434924663541 814 44200110419258 815 35368819642206 816 24234099323952 817 13719459734412 818 6062017485375 819 1875150767526 820 313192795443 821 0 822 1 823 6 824 99 825 332 826 2955 827 11445 828 63294 829 250532 830 1099297 831 4188924 832 15989752 833 56871709 834 195794456 835 640573389 836 2006636949 837 5993332837 838 17071816579 839 46318812117 840 119578929844 841 293469135336 842 683774652920 843 1510683571750 844 3159567496044 845 6244781506202 846 11638173599188 847 20401100865376 848 33535476563143 849 51511853923016 850 73619381491844 851 97394474081126 852 118515360394851 853 131620525437755 854 132083978543550 855 118247444491533 856 92819050304890 857 62375331952432 858 34623889665794 859 14993184767213 860 4542735870863 861 741954027808 862 0 863 2 864 5 865 145 866 397 867 3818 868 13757 869 77382 870 297920 871 1319383 872 5009844 873 19375437 874 69632383 875 244048159 876 812845510 877 2601382512 878 7942628592 879 23175153947 880 64469081615 881 170929920608 882 431371265577 883 1035339414565 884 2360214082030 885 5103971829127 886 10453000500498 887 20238082507445 888 36959945984977 889 63508251633133 890 102361790174462 891 154207270513916 892 216197188777470 893 280625875913272 894 335092477494608 895 365214822554134 896 359691724636147 897 316023150130515 898 243433144790730 899 160506518576041 900 87393053317330 901 37103017277675 902 11015784255967 903 1760217072440 904 0 905 1 906 6 907 110 908 376 909 3454 910 13557 911 78308 912 317147 913 1447818 914 5697049 915 22619633 916 83501149 917 299383667 918 1020414310 919 3337902011 920 10426480082 921 31132161493 922 88738038546 923 241296592419 924 625457333388 925 1543904535171 926 3625891671927 927 8091726385199 928 17136838457167 929 34384979145281 930 65246442077850 931 116822052875910 932 196860554491657 933 311257688581737 934 460089056552314 935 633039623002447 936 806533509820585 937 945428932433209 938 1011617648593610 939 978180734684616 940 843757247397991 941 638049766194972 942 412920119614852 943 220614265310661 944 91864915085677 945 26736817777112 946 4181684841136 947 0 948 2 949 3 950 160 951 408 952 4404 953 15920 954 94705 955 374211 956 1724790 957 6761548 958 27165223 959 101173993 960 368678490 961 1277061775 962 4260044391 963 13578108826 964 41446124226 965 120868557625 966 336749619510 967 895306303089 968 2270089926405 969 5483821629888 970 12609013440077 971 27561179204085 972 57193561411349 973 112488797002569 974 209299560696357 975 367574537559643 976 607729486152346 977 943004794132645 978 1368273262286125 979 1848338638812044 980 2312372174959975 981 2661947872361664 982 2797389919488093 983 2656653933413635 984 2250608780436292 985 1671351922991485 986 1062020851177017 987 556980518145669 988 227563545865858 989 64950361223837 990 9947298832729