1 1 2 1 3 2 4 3 5 5 6 8 7 13 8 3 9 12 10 27 11 29 12 36 13 33 14 41 15 58 16 51 17 31 18 64 19 89 20 45 21 74 22 83 23 39 24 168 25 145 26 193 27 170 28 129 29 149 30 104 31 211 32 289 33 274 34 175 35 257 36 252 37 125 38 161 39 318 40 347 41 447 42 316 43 317 44 285 45 450 46 107 47 253 48 648 49 363 50 301 51 498 52 409 53 773 54 522 55 429 56 515 57 782 58 649 59 641 60 760 61 425 62 1093 63 646 64 623 65 1165 66 804 67 893 68 717 69 850 70 899 71 529 72 1020 73 1453 74 1369 75 1244 76 983 77 985 78 1484 79 1421 80 1245 81 870 82 1051 83 1467 84 1440 85 1079 86 1431 87 930 88 1443 89 1209 90 1672 91 1631 92 1583 93 1982 94 2267 95 1903 96 2072 97 1709 98 2249 99 1712 100 1695 101 1727 102 2140 103 2001 104 2581 105 2320 106 1783 107 2281 108 2080 109 1705 110 2705 111 2614 112 2859 113 2829 114 2932 115 2165 116 2477 117 3176 118 2639 119 2097 120 2940 121 3301 122 3121 123 3014 124 2049 125 3215 126 2568 127 2449 128 3171 129 4060 130 2983 131 3041 132 4392 133 3803 134 4481 135 3530 136 4491 137 3209 138 3034 139 3197 140 2773 141 3296 142 5411 143 4105 144 3990 145 4141 146 4281 147 5054 148 5139 149 4181 150 2538 151 4309 152 5589 153 5074 154 5357 155 4535 156 4302 157 6659 158 5049 159 5650 160 4935 161 5985 162 4488 163 6113 164 4773 165 5490 166 5549 167 5293 168 4980 169 7489 170 4829 171 5610 172 4059 173 6493 174 6320 175 6919 176 7613 177 6532 178 6539 179 6731 180 8280 181 7241 182 5661 183 7006 184 7875 185 5135 186 6744 187 6089 188 6753 189 6770 190 6945 191 6913 192 6860 193 7633 194 9597 195 7456 196 6067 197 9077 198 8180 199 7373 200 8011 201 7178 202 8611 203 9893 204 8016 205 8011 206 7653 207 7954 208 9051 209 8037 210 8440 211 7781 212 7669 213 8930 214 9539 215 9291 216 9072 217 8671 218 9249 219 9986 220 8915 221 11081 222 9464 223 12509 224 11163 225 12018 226 9031 227 10649 228 13078 229 8765 230 11115 231 10858 232 12975 233 11353 234 11552 235 11477 236 11289 237 13394 238 11323 239 13035 240 11270 241 11757 242 15211 243 14810 244 11811 245 14453 246 11734 247 11605 248 14621 249 11488 250 12739 251 13529 252 14224 253 14159 254 12089 255 11026 256 12409 257 15817 258 15574 259 13385 260 15045 261 12530 262 13315 263 14689 264 12852 265 18545 266 8527 267 15370 268 14451 269 14849 270 14216 271 17869 272 14025 273 13546 274 14383 275 18281 276 14814 277 14377 278 14849 279 14146 280 16345 281 16399 282 13276 283 21231 284 13893 285 15002 286 17883 287 16705 288 22092 289 15745 290 14337 291 17634 292 16563 293 15597 294 25252 295 19333 296 12633 297 18952 298 19027 299 21939 300 14658 301 22433 302 17417 303 24532 304 21343 305 20545 306 20728 307 18641 308 21957 309 21870 310 17711 311 24047 312 19108 313 24913 314 19027 315 21614 316 18291 317 13871 318 26534 319 22045 320 20517 321 24826 322 19423 323 22897 324 19890 325 21457 326 23273 327 24928 328 24831 329 19841 330 26284 331 23369 332 22045 333 21788 334 21335 335 20665 336 21612 337 20665 338 25345 339 26906 340 25833 341 26705 342 22016 343 25529 344 29043 345 30662 346 21097 347 22553 348 24846 349 30599 350 25861 351 24814 352 28491 353 27553 354 29230 355 23285 356 23509 357 33090 358 26029 359 30385 360 27132 361 28741 362 26841 363 26154 364 29403 365 24791 366 29288 367 24237 368 27939 369 23794 370 30305 371 27305 372 30648 373 25709 374 29957 375 29230 376 28167 377 33487 378 31096 379 36389 380 31173 381 25186 382 36847 383 30493 384 26208 385 27625 386 32249 387 34388 388 25179 389 30983 390 31442 391 26893 392 33105 393 35532 394 28405 395 35825 396 30480 397 29447 398 31393 399 27196 400 37915 401 29593 402 34392 403 30515 404 30861 405 36618 406 31553 407 25897 408 37296 409 24277 410 35581 411 33458 412 31695 413 36437 414 40052 415 35869 416 37177 417 31502 418 32005 419 36553 420 36004 421 37029 422 42713 423 33816 424 41915 425 42061 426 38172 427 35881 428 32645 429 36884 430 34247 431 37369 432 31584 433 40795 434 42737 435 34226 436 50467 437 34757 438 44684 439 44827 440 33879 441 33476 442 35815 443 41081 444 47648 445 44345 446 37337 447 47122 448 44585 449 37885 450 41380 451 39173 452 47389 453 39520 454 46287 455 42721 456 37352 457 47641 458 46829 459 35714 460 39963 461 46787 462 36776 463 44239 464 49173 465 41878 466 39367 467 40133 468 39126 469 39065 470 39005 471 46618 472 42539 473 48635 474 43672 475 45465 476 46365 477 43122 478 55679 479 43825 480 58720 481 58609 482 44857 483 40322 484 55563 485 51221 486 53748 487 49333 488 45841 489 41020 490 49465 491 47429 492 57298 493 45089 494 43565 495 52582 496 42627 497 46309 498 46740 499 52829 500 44775 501 46966 502 43379 503 55321 504 42180 505 57553 506 41553 507 57356 508 53151 509 54473 510 42176 511 54251 512 56349 513 47770 514 55143 515 57815 516 61344 517 65397 518 59741 519 59786 520 58767 521 51973 522 56062 523 60437 524 65223 525 49874 526 50513 527 58849 528 48344 529 46763 530 57125 531 57500 532 53035 533 65555 534 60712 535 63553 536 57509 537 51682 538 58319 539 52649 540 57474 541 60861 542 56981 543 68284 544 58197 545 64925 546 60478 547 73859 548 64025 549 57506 550 71827 551 62449 552 56442 553 68419 554 67289 555 54248 556 61047 557 67355 558 79848 559 61591 560 54717 561 60538 562 71947 563 63307 564 62736 565 71687 566 76823 567 68670 568 62955 569 74485 570 69470 571 64205 572 67233 573 58214 574 58319 575 78625 576 61322 577 67593 578 72277 579 67118 580 77835 581 73861 582 76196 583 56773 584 62047 585 63310 586 66723 587 73145 588 75834 589 76265 590 81833 591 72430 592 84411 593 77107 594 66984 595 69701 596 68589 597 76298 598 70979 599 66653 600 80416 601 75841 602 76033 603 74042 604 74307 605 75205 606 73704 607 73633 608 74501 609 71224 610 76223 611 78215 612 90384 613 74725 614 92051 615 82690 616 89997 617 81901 618 90904 619 82757 620 86423 621 91766 622 77603 623 70525 624 78708 625 86493 626 92845 627 88200 628 86019 629 81779 630 88760 631 83047 632 70645 633 80276 634 86407 635 75257 636 88912 637 93113 638 93689 639 81866 640 94105 641 85555 642 86518 643 80323 644 88917 645 88218 646 77551 647 88273 648 88752 649 93393 650 94345 651 98174 652 99889 653 106853 654 85400 655 91327 656 99069 657 84540 658 101239 659 89765 660 85824 661 91733 662 89981 663 78742 664 105773 665 102685 666 80132 667 80627 668 92349 669 91730 670 88505 671 100865 672 102204 673 87153 674 87859 675 90260 676 97557 677 91049 678 96452 679 86501 680 89993 681 98284 682 108391 683 91169 684 87408 685 99035 686 101305 687 98498 688 99897 689 120319 690 99484 691 97441 692 87897 693 87050 694 97661 695 112095 696 119472 697 86253 698 104929 699 91402 700 101413 701 88661 702 106168 703 107637 704 110753 705 91846 706 97955 707 88739 708 92946 709 107549 710 87871 711 112626 712 92005 713 91813 714 102820 715 115341 716 102183 717 108602 718 100583 719 111521 720 89862 721 114385 722 104591 723 116142 724 100653 725 100115 726 129368 727 113329 728 112397 729 117834 730 115975 731 107081 732 113614 733 116405 734 136673 735 110242 736 119455 737 118777 738 101234 739 103355 740 112581 741 101666 742 107999 743 112337 744 105372 745 108681 746 98761 747 130398 748 123357 749 103757 750 131796 751 111649 752 108179 753 110158 754 129151 755 112345 756 135198 757 117689 758 98225 759 133286 760 113655 761 117861 762 122032 763 107193 764 114873 765 130424 766 140237 767 105157 768 123224 769 118819 770 114625 771 143254 772 131645 773 118121 774 133574 775 134245 776 109381 777 124150 778 124417 779 117687 780 135346 781 139625 782 127061 783 132346 784 148239 785 151855 786 127300 787 104273 788 117987 789 128802 790 133143 791 124129 792 130824 793 126925 794 152153 795 109100 796 138847 797 132309 798 127304 799 132801 800 144333 801 155694 802 123001 803 140837 804 146216 805 156637 806 112439 807 138886 808 135771 809 150205 810 154820 811 141233 812 163437 813 129538 814 143595 815 144825 816 130842 817 143173 818 129011 819 140434 820 140115 821 147481 822 136792 823 165447 824 126077 825 140002 826 153103 827 150505 828 151062 829 154289 830 142757 831 150442 832 136623 833 135745 834 134308 835 127745 836 164139 837 154754 838 165119 839 138865 840 167944 841 163441 842 128701 843 126682 844 153171 845 138659 846 149528 847 130117 848 143751 849 160378 850 155755 851 154697 852 174884 853 139211 854 141191 855 172102 856 159579 857 131049 858 171328 859 159341 860 153357 861 166952 862 138623 863 153487 864 150748 865 170191 866 155713 867 158480 868 148719 869 163957 870 171120 871 159403 872 155567 873 140458 874 123017 875 156425 876 163050 877 150893 878 180153 879 158638 880 161595 881 156181 882 145600 883 165861 884 156977 885 159320 886 171425 887 178009 888 159372 889 199579 890 180445 891 170060 892 191703 893 172139 894 159992 895 163021 896 174417 897 176098 898 171533 899 165341 900 171336 901 186401 902 159493 903 164298 904 166359 905 166027 906 173242 907 165317 908 176721 909 183728 910 183189 911 171069 912 173584 913 189295 914 172153 915 164510 916 156573 917 163397 918 175838 919 176789 920 173325 921 169546 922 187831 923 173447 924 150540 925 188981 926 182321 927 194888 928 190575 929 211597 930 180568 931 175331 932 190725 933 203738 934 227587 935 166957 936 196512 937 191617 938 193033 939 173570 940 202695 941 207437 942 177816 943 186837 944 212517 945 214582 946 207103 947 196473 948 195236 949 172889 950 192823 951 210778 952 181999 953 200113 954 191400 955 187157 956 211877 957 196044 958 180095 959 199023 960 199080 961 188293 962 202281 963 196486 964 197095 965 204935 966 200516 967 203607 968 191541 969 216868 970 197379 971 194425 972 182520 973 188225 974 186617 975 215818 976 193237 977 216961 978 188778 979 180485 980 196053 981 198474 982 194651 983 191305 984 176372 985 215479 986 196765 987 186610 988 181667 989 206377 990 198208 991 235229 992 220741 993 189394 994 208231 995 215341 996 214824 997 210229 998 195249 999 184962 1000 202423