1 1 2 1 3 2 4 3 5 6 6 5 7 12 8 13 9 18 10 15 11 32 12 21 13 46 14 35 15 42 16 49 17 80 18 49 19 102 20 71 21 88 22 85 23 150 24 89 25 156 26 125 27 164 28 137 29 242 30 113 31 278 32 213 33 230 34 217 35 272 36 191 37 396 38 275 39 320 40 261 41 490 42 237 43 542 44 369 45 386 46 401 47 650 48 355 49 640 50 431 51 560 52 507 53 830 54 449 55 704 56 551 57 696 58 643 59 1028 60 459 61 1102 62 759 63 794 64 825 65 996 66 605 67 1328 68 891 69 1042 70 719 71 1494 72 791 73 1588 74 1089 75 1080 76 1111 77 1454 78 863 79 1856 80 1095 81 1494 82 1317 83 2060 84 951 85 1734 86 1461 87 1666 88 1429 89 2368 90 1035 91 2054 92 1653 93 1906 94 1733 95 2170 96 1379 97 2806 98 1695 99 2042 100 1663 101 3044 102 1495 103 3176 104 2053 105 1832 106 2205 107 3426 108 1783 109 3568 110 1929 111 2746 112 2243 113 3836 114 1913 115 3228 116 2659 117 2906 118 2757 119 3574 120 1827 121 4066 122 2961 123 3366 124 3011 125 3952 126 2097 127 4832 128 3327 129 3712 130 2651 131 5154 132 2433 133 4484 134 3583 135 3456 136 3513 137 5634 138 2787 139 5814 140 2911 141 4442 142 4017 143 5308 144 3155 145 5150 146 4247 147 4296 148 4295 149 6670 150 2843 151 6858 152 4467 153 5062 154 3849 155 5892 156 3433 157 7404 158 4995 159 5660 160 4293 161 6618 162 3973 163 7992 164 5351 165 4736 166 5469 167 8396 168 3761 169 8058 170 4669 171 6346 172 5855 173 9022 174 4489 175 6798 176 5773 177 7010 178 6301 179 9654 180 4115 181 9880 182 5475 183 7524 184 6581 185 8464 186 5101 187 9222 188 7033 189 7132 190 5781 191 10976 192 5601 193 11230 194 7565 195 6726 196 6809 197 11698 198 5489 199 11954 200 6827 201 9104 202 8183 203 10640 204 6019 205 10404 206 8509 207 9370 208 8143 209 11580 210 4895 211 13414 212 8977 213 10216 214 9167 215 11462 216 7073 217 12150 218 9513 219 10774 220 7393 221 13018 222 7265 223 14990 224 8883 225 9584 226 10187 227 15540 228 7515 229 15838 230 8651 231 9748 232 10509 233 16386 234 7753 235 13698 236 11115 237 12650 238 9469 239 17242 240 7307 241 17544 242 10963 243 13490 244 11905 245 13328 246 8983 247 16360 248 12079 249 13950 250 10509 251 19024 252 8473 253 17122 254 12977 255 11674 256 13231 257 19948 258 9915 259 17420 260 10587 261 15002 262 13741 263 20898 264 9703 265 17472 266 11911 267 16038 268 14319 269 21864 270 9235 271 22204 272 14271 273 13832 274 15063 275 17566 276 11087 277 23170 278 15537 279 17222 280 11611 281 23860 282 11875 283 24232 284 16207 285 14740 286 14149 287 21438 288 12627 289 23974 290 13849 291 19112 292 17049 293 25974 294 11559 295 21714 296 17321 297 18456 298 17821 299 24230 300 11411 301 23570 302 18335 303 20730 304 17803 305 23184 306 13379 307 28480 308 15415 309 21536 310 15709 311 29230 312 13715 313 29636 314 19901 315 16530 316 19967 317 30404 318 15163 319 27488 320 17377 321 23306 322 17659 323 28488 324 15991 325 24856 326 21375 327 24124 328 21233 329 28226 330 12611 331 33106 332 22113 333 24622 334 22409 335 28034 336 14941 337 34342 338 21519 339 25968 340 18323 341 31426 342 16855 343 31250 344 23447 345 21630 346 23997 347 36404 348 17789 349 36862 350 18117 351 26076 352 22939 353 37706 354 18787 355 31514 356 25447 357 23970 358 25725 359 39000 360 16415 361 37618 362 26423 363 27574 364 21825 365 33292 366 20045 367 40748 368 26399 369 30348 370 22509 371 35956 372 20393 373 42106 374 24665 375 26696 376 28003 377 38806 378 18965 379 43466 380 23151 381 32846 382 29377 383 44430 384 22491 385 30114 386 29997 387 33346 388 30153 389 45816 390 17923 391 42124 392 27287 393 34942 394 31245 395 39080 396 21863 397 47708 398 31951 399 30196 400 26945 401 48678 402 24249 403 44470 404 32825 405 31208 406 28251 407 45002 408 23859 409 50642 410 27873 411 38248 412 34075 413 44684 414 24977 415 43098 416 32489 417 39316 418 30825 419 53142 420 19531 421 53656 422 35961 423 39992 424 35771 425 43258 426 27191 427 47760 428 36809 429 35676 430 30453 431 56210 432 28331 433 56784 434 32361 435 34762 436 38129 437 52874 438 28799 439 58376 440 30139 441 38778 442 34715 443 59418 444 29283 445 49604 446 40111 447 45252 448 35559 449 61066 450 25699 451 55414 452 41141 453 46512 454 41551 455 42594 456 29907 457 63216 458 42293 459 45370 460 34099 461 64364 462 26061 463 64944 464 42359 465 39904 466 43739 467 66102 468 31067 469 57778 470 36755 471 50298 472 44391 473 61032 474 33797 475 54354 476 37963 477 50878 478 45999 479 69514 480 29237 481 63688 482 46907 483 44636 484 43391 485 58980 486 35841 487 71822 488 47501 489 54208 490 35487 491 73040 492 35977 493 67562 494 43747 495 42690 496 48313 497 64832 498 37275 499 75418 500 42329 501 56880 502 50783 503 76698 504 33867 505 64032 506 45805 507 54432 508 51869 509 78528 510 31197 511 68574 512 53187 513 57062 514 53255 515 66580 516 39551 517 72976 518 46249 519 61028 520 42375 521 82220 522 40041 523 82908 524 55375 525 45832 526 55743 527 77328 528 38855 529 81532 530 46791 531 63278 532 47745 533 78342 534 42961 535 71842 536 57385 537 65350 538 58331 539 70788 540 36841 541 88642 542 59289 543 66844 544 56495 545 74564 546 36691 547 90644 548 60489 549 67630 550 46641 551 84792 552 44287 553 80372 554 61953 555 56918 556 62103 557 94010 558 45821 559 86262 560 46287 561 62030 562 63617 563 96042 564 47391 565 80148 566 64625 567 64096 568 64321 569 98122 570 39037 571 98834 572 56445 573 74536 574 57027 575 80250 576 50383 577 100896 578 64021 579 76060 580 54709 581 88750 582 50971 583 93012 584 68225 585 60280 586 69157 587 104424 588 45927 589 97096 590 57965 591 79226 592 69203 593 106630 594 49189 595 74060 596 71499 597 80782 598 64455 599 108742 600 45563 601 109500 602 62869 603 81704 604 73483 605 85060 606 55211 607 111688 608 71127 609 71532 610 61851 611 103194 612 53797 613 113902 614 76173 615 70228 616 61685 617 115380 618 57587 619 116200 620 63019 621 84320 622 78119 623 102218 624 54971 625 98956 626 79145 627 78042 628 79349 629 110720 630 43953 631 120688 632 80009 633 91010 634 81127 635 101438 636 60361 637 100188 638 73291 639 91774 640 68983 641 124538 642 62067 643 125390 644 70551 645 77244 646 75861 647 126920 648 63885 649 115546 650 66283 651 81884 652 85589 653 129286 654 64577 655 107866 656 85287 657 97110 658 75143 659 131702 660 50623 661 132520 662 88667 663 88050 664 88315 665 93146 666 65623 667 125324 668 89931 669 101594 670 74707 671 123486 672 60125 673 137318 674 91809 675 86626 676 85953 677 138998 678 69391 679 121556 680 74029 681 105278 682 83699 683 141482 684 67753 685 118064 686 83501 687 107094 688 93833 689 131586 690 57821 691 144810 692 96689 693 87880 694 97219 695 121502 696 71127 697 136254 698 98409 699 110966 700 72383 701 149018 702 69559 703 139116 704 92249 705 92530 706 100585 707 131762 708 74989 709 152454 710 84195 711 113874 712 101569 713 143624 714 64113 715 110194 716 103319 717 116650 718 103971 719 156784 720 65693 721 137018 722 100367 723 118676 724 105599 725 128788 726 73345 727 160268 728 87271 729 121090 730 88791 731 149992 732 80083 733 162968 734 108949 735 89824 736 104943 737 149242 738 80775 739 165654 740 90117 741 110558 742 95819 743 167424 744 81545 745 139714 746 112443 747 125728 748 97927 749 147910 750 71211 751 171018 752 112439 753 128778 754 103605 755 143476 756 75891 757 173788 758 116171 759 115326 760 92705 761 175650 762 87679 763 153514 764 117827 765 104964 766 118399 767 163380 768 89653 769 179408 770 80371 771 134998 772 120181 773 181312 774 89135 775 147548 776 120881 777 117262 778 122173 779 171204 780 71561 781 167752 782 112401 783 135218 784 108927 785 155108 786 93187 787 187828 788 125307 789 141424 790 104073 791 164990 792 87335 793 174698 794 127415 795 117836 796 127633 797 192682 798 80305 799 179582 800 108167 801 144712 802 129887 803 177374 804 96881 805 137528 806 118281 807 147768 808 130771 809 198486 810 83019 811 199510 812 113095 813 150118 814 119849 815 167268 816 95365 817 188384 818 135225 819 124162 820 110457 821 204376 822 101957 823 205468 824 136381 825 118516 826 118887 827 207446 828 100061 829 208536 830 115363 831 156978 832 130377 833 174316 834 105095 835 175568 836 123269 837 154690 838 141771 839 213558 840 78153 841 207812 842 143419 843 161538 844 143769 845 168044 846 106469 847 174936 848 143135 849 163654 850 114879 851 205526 852 108705 853 220732 854 127269 855 131778 856 146945 857 222800 858 95223 859 223896 860 122167 861 144364 862 150087 863 226000 864 113603 865 188538 866 151635 867 161924 868 129499 869 207938 870 92671 871 211086 872 152779 873 172064 874 141055 875 169678 876 114951 877 233262 878 155797 879 175518 880 119603 881 235480 882 103537 883 236612 884 139069 885 146408 886 158603 887 238784 888 116783 889 208830 890 132727 891 165924 892 160561 893 225622 894 120831 895 201878 896 142409 897 163182 898 162847 899 230174 900 102603 901 228822 902 147867 903 158964 904 164015 905 206250 906 123925 907 249530 908 166419 909 186618 910 113651 911 251776 912 120083 913 229570 914 168971 915 156576 916 169223 917 222078 918 120891 919 256254 920 137289 921 192786 922 171757 923 237328 924 104071 925 211040 926 173315 927 194044 928 168397 929 261918 930 106147 931 218962 932 175377 933 197856 934 176227 935 191644 936 123341 937 266320 938 153561 939 200290 940 145715 941 268644 942 133989 943 253094 944 177871 945 148438 946 162415 947 272092 948 134957 949 250862 950 144835 951 205524 952 151893 953 275590 954 135863 955 229934 956 184585 957 184900 958 185381 959 242960 960 116627 961 271860 962 169521 963 209476 964 187521 965 234730 966 118659 967 283710 968 174255 969 192178 970 157239 971 286076 972 143621 973 250098 974 191863 975 167550 976 189889 977 289644 978 144615 979 264228 980 141843 981 217434 982 194843 983 293298 984 143727 985 244660 986 180211 987 190218 988 174443 989 278570 990 113663 991 297980 992 193145 993 224248 994 172749 995 249554 996 149055 997 301650 998 201515 999 221710 1000 168733