1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 8 10 8 11 8 12 8 13 8 14 12 15 20 16 20 17 12 18 20 19 38 20 38 21 40 22 26 23 20 24 46 25 58 26 70 27 82 28 101 29 65 30 113 31 63 32 137 33 130 34 111 35 169 36 141 37 102 38 97 39 130 40 125 41 91 42 163 43 145 44 177 45 213 46 177 47 149 48 298 49 244 50 278 51 378 52 296 53 260 54 301 55 393 56 390 57 407 58 335 59 378 60 449 61 298 62 321 63 572 64 681 65 585 66 489 67 447 68 529 69 514 70 539 71 311 72 629 73 476 74 559 75 743 76 667 77 812 78 718 79 515 80 952 81 793 82 687 83 647 84 892 85 866 86 654 87 870 88 816 89 575 90 1009 91 1170 92 1066 93 974 94 687 95 1063 96 1358 97 854 98 1038 99 1440 100 1319 101 864 102 1337 103 926 104 1243 105 1560 106 1085 107 1092 108 1519 109 1069 110 1328 111 1237 112 1795 113 1039 114 1426 115 1620 116 1386 117 1734 118 1042 119 1834 120 1876 121 1649 122 1512 123 2027 124 1807 125 1623 126 2145 127 1437 128 2683 129 1913 130 2152 131 1680 132 2394 133 2453 134 1705 135 2627 136 2210 137 1665 138 2455 139 1827 140 2802 141 2339 142 1665 143 2686 144 3258 145 2466 146 2264 147 2830 148 2601 149 1954 150 2823 151 2078 152 2863 153 3413 154 3177 155 3200 156 3434 157 2170 158 2490 159 2907 160 4152 161 3431 162 3254 163 2667 164 3204 165 4014 166 2304 167 2205 168 3946 169 2996 170 4077 171 4352 172 3527 173 2617 174 3940 175 4594 176 5072 177 4069 178 3376 179 3151 180 5095 181 2944 182 4475 183 3929 184 4380 185 4389 186 4110 187 5153 188 4559 189 4961 190 4382 191 2819 192 6132 193 3535 194 3945 195 5842 196 5013 197 3511 198 5393 199 3518 200 5267 201 4677 202 3879 203 5707 204 5476 205 5116 206 3851 207 6293 208 6629 209 5946 210 6094 211 4302 212 5160 213 5256 214 3835 215 5827 216 6202 217 6226 218 4735 219 5867 220 6904 221 6184 222 5905 223 4243 224 7826 225 6948 226 4841 227 4903 228 6732 229 4507 230 6653 231 7350 232 5922 233 4552 234 6992 235 6913 236 6172 237 6038 238 7176 239 4466 240 8908 241 5308 242 5535 243 7116 244 6766 245 8613 246 7635 247 8412 248 7730 249 7432 250 7078 251 6152 252 9915 253 8661 254 6054 255 9523 256 10647 257 5658 258 7886 259 9127 260 9608 261 9289 262 5444 263 5783 264 9825 265 9107 266 9468 267 9441 268 8102 269 6076 270 9981 271 6320 272 11406 273 10870 274 7439 275 10964 276 10940 277 6883 278 6811 279 11126 280 11553 281 6831 282 10151 283 7981 284 10261 285 11587 286 10908 287 11294 288 13748 289 8603 290 11232 291 10857 292 10229 293 7411 294 11004 295 11164 296 10595 297 13065 298 8450 299 12565 300 13314 301 12299 302 8314 303 11366 304 14227 305 12006 306 12630 307 9467 308 13941 309 11147 310 12042 311 7734 312 13881 313 9094 314 9843 315 15659 316 12416 317 9354 318 12648 319 13994 320 17505 321 11904 322 13703 323 14630 324 14276 325 14827 326 10188 327 12530 328 12773 329 14046 330 15603 331 10252 332 12914 333 14831 334 10122 335 14282 336 18547 337 11213 338 12177 339 15196 340 16527 341 15578 342 15879 343 13041 344 15109 345 17487 346 11470 347 11794 348 17261 349 11674 350 17549 351 18932 352 21030 353 11671 354 15349 355 17084 356 15642 357 19726 358 11414 359 10997 360 20627 361 13929 362 13103 363 17896 364 20317 365 18485 366 17501 367 12376 368 21994 369 19725 370 18927 371 19889 372 19996 373 12548 374 19771 375 19106 376 19109 377 19555 378 21039 379 14346 380 22937 381 17068 382 13683 383 12924 384 25489 385 23859 386 15581 387 22338 388 19454 389 14217 390 22614 391 22236 392 21219 393 19187 394 15210 395 21798 396 24812 397 14688 398 15197 399 23641 400 25970 401 14720 402 19816 403 22913 404 18710 405 24383 406 21947 407 22791 408 24062 409 15900 410 23558 411 22024 412 20858 413 23374 414 24446 415 23452 416 28837 417 20941 418 24367 419 16788 420 28028 421 16495 422 16442 423 26092 424 22552 425 26635 426 22861 427 25843 428 22388 429 27894 430 24014 431 15976 432 30781 433 17988 434 26210 435 29410 436 22608 437 26862 438 23578 439 17568 440 29046 441 28092 442 26806 443 18486 444 28086 445 25191 446 17696 447 24112 448 34058 449 18541 450 28679 451 29164 452 24401 453 24510 454 18273 455 32055 456 29351 457 19956 458 20649 459 31231 460 30460 461 18310 462 32013 463 19329 464 33482 465 31454 466 20589 467 21348 468 33531 469 29113 470 28584 471 25378 472 26464 473 30868 474 27019 475 32282 476 34245 477 30680 478 20844 479 19207 480 38678 481 32249 482 23158 483 36192 484 28309 485 31182 486 27734 487 21512 488 28724 489 27908 490 32387 491 23435 492 33477 493 33141 494 33685 495 39634 496 38332 497 32651 498 29184 499 23644 500 32494 501 29350 502 21179 503 22078 504 39714 505 31916 506 35579 507 31793 508 31306 509 22620 510 37110 511 35581 512 42157 513 38272 514 26864 515 34780 516 36331 517 36142 518 36083 519 31633 520 38913 521 22931 522 37042 523 26733 524 32726 525 42487 526 25919 527 38837 528 46512 529 28366 530 37915 531 39833 532 42282 533 40070 534 35003 535 38062 536 35117 537 35569 538 28043 539 43113 540 45736 541 27472 542 27743 543 35615 544 48096 545 38236 546 44077 547 28433 548 36296 549 40956 550 44078 551 42570 552 44973 553 41888 554 30837 555 47408 556 36952 557 28985 558 43005 559 43734 560 53552 561 47943 562 31432 563 30618 564 45642 565 41691 566 29823 567 48611 568 42154 569 29893 570 48459 571 31606 572 50638 573 38755 574 43978 575 48496 576 57866 577 31488 578 35671 579 42903 580 49546 581 45703 582 42024 583 48161 584 42094 585 53851 586 33385 587 34284 588 50748 589 48950 590 44611 591 40099 592 54290 593 31005 594 52309 595 56503 596 41868 597 42463 598 47905 599 31265 600 55062 601 34498 602 49458 603 51678 604 45792 605 52744 606 47085 607 35366 608 61400 609 55347 610 50424 611 53602 612 58889 613 34138 614 35635 615 57221 616 57295 617 36552 618 47401 619 36882 620 57265 621 57952 622 35677 623 52932 624 64990 625 44299 626 40192 627 62620 628 47289 629 54638 630 61579 631 35946 632 51233 633 48428 634 38482 635 54006 636 57770 637 58887 638 56236 639 59642 640 70767 641 36596 642 49404 643 41229 644 62676 645 61206 646 58060 647 37546 648 59482 649 58914 650 61817 651 65825 652 50123 653 41229 654 54120 655 57076 656 67829 657 60999 658 59527 659 41971 660 70002 661 41034 662 41632 663 68561 664 54564 665 70515 666 61022 667 63316 668 57316 669 54537 670 58080 671 62209 672 77133 673 43579 674 46614 675 70095 676 57448 677 41859 678 56789 679 63246 680 68529 681 55782 682 64140 683 44919 684 72792 685 61460 686 50826 687 58022 688 73460 689 63855 690 70212 691 46424 692 55733 693 76147 694 43782 695 63164 696 70214 697 69608 698 47691 699 63196 700 76818 701 45187 702 71035 703 68907 704 86034 705 72958 706 49611 707 69272 708 71138 709 47030 710 66662 711 71245 712 61886 713 70820 714 76967 715 79575 716 60275 717 61773 718 47168 719 43063 720 88592 721 70457 722 52302 723 66662 724 60971 725 76460 726 67883 727 49854 728 80122 729 65706 730 71028 731 78054 732 75456 733 49489 734 51441 735 84474 736 90124 737 75141 738 76634 739 53416 740 81644 741 84390 742 71864 743 49918 744 80794 745 72392 746 57861 747 81050 748 84727 749 76186 750 76003 751 53312 752 90806 753 72031 754 79934 755 77563 756 91217 757 54171 758 54866 759 86560 760 88324 761 51453 762 71143 763 80521 764 73724 765 93713 766 54707 767 81403 768 101304 769 57125 770 92043 771 76798 772 72585 773 54599 774 82963 775 90491 776 75472 777 89558 778 59631 779 87599 780 98262 781 85545 782 85917 783 92439 784 99816 785 84045 786 74113 787 60684 788 74797 789 73064 790 80758 791 83152 792 100045 793 88086 794 61480 795 96035 796 77619 797 57881 798 97020 799 89500 800 107452 801 90615 802 63028 803 91317 804 90453 805 100874 806 91290 807 81343 808 80287 809 60299 810 96494 811 65279 812 97990 813 79115 814 90750 815 85346 816 111082 817 95330 818 65749 819 107870 820 98139 821 63663 822 83458 823 61868 824 85816 825 105397 826 90949 827 64994 828 106424 829 63525 830 89270 831 78286 832 119078 833 100532 834 83569 835 92683 836 105216 837 103201 838 62970 839 62914 840 113346 841 70128 842 70882 843 92870 844 84319 845 96785 846 103921 847 103141 848 113760 849 85982 850 107421 851 107098 852 108199 853 69092 854 102717 855 122218 856 93561 857 67307 858 114819 859 71826 860 114961 861 113104 862 69755 863 69198 864 128491 865 99337 866 77093 867 97419 868 117203 869 106565 870 112951 871 106434 872 96211 873 109281 874 108584 875 115391 876 110102 877 72231 878 74411 879 95495 880 133423 881 71443 882 115652 883 75739 884 118766 885 119020 886 75295 887 72103 888 117226 889 110750 890 109695 891 123289 892 99368 893 115335 894 102560 895 107373 896 141323 897 125540 898 80389 899 117823 900 133187 901 114081 902 113474 903 125442 904 102971 905 107564 906 102397 907 80106 908 98867 909 116312 910 127504 911 73451 912 140176 913 117971 914 85842 915 129688 916 98910 917 117624 918 124455 919 79356 920 128700 921 104017 922 83930 923 121147 924 139521 925 125538 926 81537 927 124286 928 143373 929 78981 930 129568 931 129056 932 105848 933 106226 934 82244 935 140228 936 142370 937 83077 938 121216 939 112589 940 130884 941 80064 942 111449 943 127540 944 142323 945 144971 946 125882 947 86744 948 127220 949 128007 950 133560 951 107620 952 141170 953 83683 954 127391 955 121910 956 116764 957 139488 958 85859 959 123302 960 163396 961 92598 962 132868 963 132876 964 114147 965 125775 966 143858 967 89568 968 124254 969 146480 970 125948 971 93724 972 131215 973 128928 974 89689 975 154137 976 151026 977 90498 978 119112 979 137435 980 148193 981 133929 982 84953 983 89727 984 141070 985 127852 986 139355 987 152568 988 148993 989 140215 990 156261 991 92131 992 164786 993 122486 994 135555 995 131624 996 140991 997 91083 998 94990 999 150730 1000 137299