1 1 2 3 3 3 4 9 5 5 6 13 7 7 8 24 9 14 10 23 11 11 12 49 13 15 14 33 15 31 16 66 17 21 18 70 19 25 20 89 21 49 22 61 23 33 24 162 25 50 26 81 27 75 28 137 29 49 30 177 31 55 32 193 33 97 34 123 35 99 36 296 37 75 38 147 39 129 40 312 41 89 42 291 43 97 44 269 45 218 46 203 47 113 48 534 49 146 50 302 51 203 52 357 53 141 54 451 55 207 56 508 57 247 58 307 59 171 60 789 61 183 62 345 63 374 64 619 65 279 66 611 67 217 68 559 69 347 70 621 71 241 72 1118 73 255 74 477 75 510 76 677 77 361 78 819 79 295 80 1098 81 530 82 575 83 323 84 1337 85 449 86 627 87 531 88 1058 89 369 90 1386 91 489 92 949 93 601 94 739 95 549 96 1839 97 435 98 942 99 810 100 1398 101 469 102 1321 103 487 104 1416 105 1077 106 927 107 523 108 2098 109 543 110 1353 111 837 112 1872 113 581 114 1617 115 781 116 1449 117 1098 118 1133 119 795 120 3138 121 732 122 1209 123 1015 124 1637 125 922 126 2430 127 727 128 2154 129 1111 130 1833 131 771 132 2889 133 979 134 1443 135 1719 136 2276 137 841 138 2301 139 865 140 2937 141 1315 142 1611 143 1089 144 4176 145 1209 146 1701 147 1670 148 2277 149 989 150 3370 151 1015 152 2782 153 1794 154 2403 155 1371 156 3897 157 1095 158 1977 159 1655 160 4001 161 1399 162 3508 163 1177 164 2759 165 2405 166 2173 167 1233 168 5470 169 1374 170 2999 171 2210 172 3017 173 1321 174 3557 175 2046 176 4074 177 2033 178 2487 179 1411 180 6596 181 1443 182 3267 183 2169 184 3952 185 1923 186 4035 187 1795 188 3569 189 3077 190 3687 191 1601 192 6675 193 1635 194 2937 195 3273 196 4534 197 1701 198 5426 199 1735 200 5792 201 2599 202 3175 203 2175 204 6359 205 2341 206 3297 207 3166 208 5508 209 2215 210 7215 211 1945 212 4489 213 2907 214 3549 215 2565 216 8700 217 2473 218 3681 219 3069 220 6529 221 2451 222 5655 223 2167 224 7043 225 4628 226 3947 227 2243 228 7817 229 2283 230 5287 231 4327 232 6100 233 2361 234 7386 235 3045 236 5509 237 3577 238 5385 239 2481 240 12186 241 2523 242 4972 243 4353 244 5877 245 3858 246 6885 247 3027 248 6916 249 3937 250 6246 251 2731 252 11728 253 3187 254 4953 255 5407 256 7956 257 2861 258 7545 259 3477 260 8877 261 4930 262 5261 263 2993 264 12152 265 3845 266 6645 267 4511 268 7037 269 3129 270 11607 271 3175 272 9012 273 5907 274 5743 275 4654 276 11189 277 3315 278 5907 279 5606 280 12372 281 3409 282 8957 283 3457 284 7869 285 6675 286 7419 287 4239 288 15862 289 3834 290 8235 291 5337 292 8307 293 3701 294 11346 295 4735 296 9684 297 6991 298 6767 299 4359 300 16358 301 4651 302 6945 303 5775 304 11088 305 5055 306 12202 307 4057 308 11717 309 6001 310 9357 311 4161 312 16506 313 4215 314 7497 315 10002 316 9677 317 4321 318 11305 319 4979 320 15107 321 6465 322 9561 323 5025 324 17075 325 6366 326 8067 327 6705 328 11784 329 5527 330 16375 331 4705 332 10649 333 7890 334 8459 335 6069 336 21708 337 4875 338 9402 339 7195 340 14639 341 5665 342 15066 343 6014 344 12910 345 9615 346 9067 347 5163 348 17389 349 5223 350 13962 351 9561 352 15799 353 5341 354 13923 355 6797 356 12199 357 9801 358 9693 359 5521 360 27946 361 5900 362 9909 363 9064 364 15981 365 7179 366 14859 367 5767 368 15894 369 9626 370 13173 371 6987 372 19757 373 5955 374 12313 375 11366 376 15320 377 6819 378 20973 379 6145 380 18057 381 9049 382 11011 383 6273 384 25228 385 10101 386 11241 387 10562 388 14427 389 6469 390 22371 391 7253 392 19412 393 9617 394 11703 395 8379 396 26536 397 6735 398 11937 399 12121 400 23232 401 6869 402 17841 403 7761 404 15609 405 14698 406 14937 407 7989 408 27218 409 7143 410 16075 411 10503 412 16217 413 8617 414 21702 415 9231 416 21519 417 10807 418 15225 419 7491 420 35277 421 7563 422 13395 423 12558 424 19328 425 10586 426 19981 427 9201 428 17469 429 13551 430 17631 431 7921 432 34899 433 7995 434 16995 435 15035 436 18117 437 8977 438 21099 439 8215 440 28010 441 15892 442 16857 443 8363 444 27777 445 10589 446 14937 447 12391 448 27127 449 8589 450 31684 451 9759 452 19439 453 12721 454 15469 455 13833 456 33580 457 8895 458 15741 459 15895 460 25989 461 9049 462 29697 463 9127 464 24738 465 17109 466 16287 467 9283 468 36228 469 11059 470 20967 471 13737 472 23794 473 10711 474 24627 475 13098 476 26487 477 15882 478 17123 479 9761 480 47527 481 10953 482 17409 483 17497 484 24488 485 12543 486 29899 487 10087 488 25392 489 14791 490 26526 491 10251 492 33879 493 11365 494 20853 495 22950 496 28116 497 12391 498 27131 499 10585 500 30718 501 15515 502 18861 503 10753 504 50318 505 13581 506 21981 507 17226 508 24437 509 11009 510 37173 511 13089 512 30483 513 19673 514 19763 515 14115 516 37157 517 12747 518 23967 519 16635 520 38244 521 11529 522 33938 523 11617 524 25969 525 25530 526 20683 527 12939 528 49218 529 12430 530 26519 531 19594 532 32741 533 13383 534 31117 535 15215 536 30478 537 17793 538 21627 539 16118 540 56998 541 12423 542 21945 543 18189 544 35609 545 15783 546 40653 547 12697 548 28359 549 20922 550 32074 551 14073 552 48322 553 15289 554 22917 555 24141 556 29177 557 13161 558 38622 559 14691 560 50184 561 22581 562 23575 563 13443 564 44169 565 16945 566 23907 567 26766 568 34128 569 13729 570 45981 571 13825 572 36597 573 20227 574 29277 575 18930 576 61448 577 14115 578 26502 579 20649 580 40609 581 16849 582 36855 583 16135 584 36036 585 31446 586 25607 587 14603 588 55894 589 16027 590 32713 591 21503 592 39564 593 14901 594 48167 595 23055 596 33449 597 21937 598 30129 599 15201 600 70556 601 15303 602 32133 603 25154 604 34337 605 21344 606 39905 607 15607 608 43985 609 27417 610 34929 611 17487 612 60136 613 15915 614 28083 615 29499 616 50734 617 16121 618 41475 619 16225 620 46197 621 28427 622 28811 623 19335 624 67212 625 21555 626 29181 627 27961 628 37077 629 18279 630 68850 631 16855 632 42052 633 24631 634 29923 635 21339 636 55829 637 22110 638 34445 639 28190 640 58490 641 17389 642 44707 643 17497 644 47237 645 32379 646 34767 647 17713 648 73832 649 19921 650 43962 651 31219 652 39917 653 18041 654 46371 655 22687 656 48276 657 29778 658 38241 659 18371 660 80729 661 18483 662 32595 663 30969 664 46322 665 28551 666 54498 667 20361 668 41869 669 27481 670 41991 671 21273 672 85865 673 19155 674 33777 675 41470 676 46494 677 19381 678 49785 679 22917 680 63492 681 28465 682 39219 683 19723 684 74368 685 24789 686 41610 687 28965 688 52956 689 22143 690 66425 691 20185 692 44889 693 41858 694 35789 695 25509 696 75478 697 22349 698 36201 699 29975 700 68934 701 20769 702 66009 703 22647 704 61967 705 38543 706 37027 707 24819 708 68849 709 21243 710 47063 711 34790 712 53120 713 23191 714 67743 715 31953 716 48009 717 31523 718 38283 719 21841 720 113820 721 25801 722 40884 723 32049 724 49077 725 29698 726 62712 727 22327 728 69420 729 37964 730 49713 731 24537 732 73497 733 22695 734 39993 735 48726 736 63409 737 25591 738 66594 739 23065 740 65157 741 38361 742 48405 743 23313 744 85870 745 29269 746 41301 747 38346 748 60939 749 27817 750 78578 751 23815 752 62970 753 34737 754 47253 755 30051 756 103534 757 24195 758 42627 759 40449 760 78510 761 24449 762 62691 763 28857 764 54569 765 52454 766 43523 767 27345 768 97840 769 24963 770 69879 771 36403 772 55707 773 25221 774 73098 775 33822 776 62904 777 44103 778 44887 779 27693 780 110517 781 28691 782 50291 783 44591 784 79668 785 32463 786 66651 787 26137 788 58009 789 38107 790 58077 791 30987 792 115210 793 29205 794 46737 795 48799 796 59177 797 26801 798 83883 799 29221 800 92554 801 44010 802 47675 803 30309 804 88337 805 41307 806 53811 807 39851 808 68104 809 27609 810 101604 811 27745 812 73977 813 40441 814 55407 815 34965 816 111648 817 30409 818 49581 819 57426 820 79599 821 28429 822 72821 823 28567 824 70780 825 58994 826 59763 827 28843 828 107376 829 28983 830 64017 831 42237 832 84795 833 36930 834 74937 835 36685 836 75437 837 50789 838 52013 839 29681 840 153126 841 30898 842 52509 843 43455 844 66437 845 40710 846 87014 847 39032 848 79626 849 44071 850 73358 851 32787 852 98989 853 30675 854 63819 855 64974 856 76290 857 30961 858 93873 859 31105 860 87357 861 53925 862 55011 863 31393 864 139005 865 39345 866 55521 867 48838 868 84221 869 35425 870 104149 871 35139 872 79128 873 52170 874 62307 875 48886 876 104547 877 32415 878 57057 879 47215 880 115086 881 32709 882 110004 883 32857 884 83547 885 60261 886 58093 887 33153 888 121086 889 39049 890 73475 891 61896 892 74117 893 36217 894 85977 895 42095 896 106218 897 55521 898 59667 899 36423 900 156672 901 37017 902 67749 903 59209 904 84948 905 43035 906 88275 907 34657 908 76769 909 56506 910 95859 911 34961 912 138096 913 39057 914 61797 915 64353 916 78117 917 41521 918 110143 919 35575 920 113368 921 51799 922 62875 923 39399 924 147017 925 47814 926 63417 927 58742 928 99221 929 36349 930 118599 931 45770 932 80839 933 53147 934 64509 935 53391 936 157746 937 36975 938 76773 939 53829 940 103969 941 37289 942 95355 943 40105 944 98226 945 90465 946 74385 947 37763 948 122117 949 41625 950 90870 951 55203 952 115608 953 38241 954 110170 955 47877 956 85009 957 63505 958 67843 959 45375 960 187039 961 40190 962 76059 963 63338 964 86427 965 48879 966 121347 967 39367 968 107006 969 64107 970 87093 971 39691 972 148117 973 46699 974 70113 975 80970 976 104868 977 40181 978 102705 979 44839 980 131454 981 65706 982 71261 983 40673 984 147918 985 50909 986 78955 987 70513 988 103461 989 44041 990 158998 991 41335 992 112931 993 60151 994 86073 995 51939 996 134589 997 41835 998 73587 999 71793 1000 134096