1 1 2 2 3 4 4 5 5 7 6 11 7 12 8 21 9 15 10 19 11 26 12 38 13 36 14 30 15 52 16 64 17 74 18 45 19 98 20 92 21 105 22 52 23 109 24 141 25 67 26 171 27 198 28 165 29 135 30 212 31 250 32 97 33 289 34 392 35 254 36 296 37 382 38 249 39 426 40 139 41 444 42 467 43 371 44 424 45 719 46 381 47 592 48 662 49 560 50 696 51 195 52 907 53 737 54 203 55 850 56 783 57 1261 58 562 59 1098 60 1097 61 1150 62 1106 63 272 64 1713 65 1131 66 566 67 1763 68 1386 69 1311 70 2116 71 813 72 1075 73 1903 74 1940 75 1768 76 2179 77 2022 78 1711 79 1481 80 373 81 3079 82 1704 83 1315 84 3377 85 2343 86 2776 87 3444 88 1162 89 2569 90 3681 91 3281 92 2770 93 1663 94 3930 95 4323 96 2593 97 2673 98 508 99 5288 100 2515 101 2752 102 6135 103 3845 104 5413 105 5447 106 1636 107 5518 108 6756 109 5372 110 3188 111 4250 112 4028 113 6767 114 877 115 8511 116 3852 117 4605 118 6033 119 684 120 8785 121 3661 122 5317 123 6367 124 7279 125 10644 126 6126 127 10001 128 3274 129 9484 130 8425 131 4908 132 2279 133 10903 134 11830 135 8547 136 6957 137 6386 138 8727 139 11273 140 2610 141 15834 142 5635 143 7683 144 12042 145 915 146 14166 147 5133 148 5246 149 9722 150 14086 151 13616 152 17834 153 9547 154 10105 155 17617 156 8148 157 19108 158 12759 159 8592 160 3139 161 20350 162 20003 163 13285 164 13946 165 9446 166 17386 167 18217 168 6393 169 28082 170 8118 171 12436 172 22711 173 1212 174 22301 175 12940 176 7430 177 16972 178 28587 179 24270 180 28985 181 15576 182 14559 183 22541 184 29945 185 18102 186 8155 187 36282 188 19000 189 14546 190 16343 191 24560 192 4285 193 36191 194 32789 195 20217 196 26385 197 13750 198 32653 199 31957 200 28742 201 25904 202 13960 203 47994 204 11548 205 19661 206 40774 207 1597 208 21007 209 39312 210 34346 211 28988 212 15274 213 10396 214 28582 215 54613 216 41702 217 45948 218 31951 219 21834 220 46093 221 49320 222 36858 223 20778 224 65568 225 27840 226 23870 227 37218 228 47194 229 5794 230 62013 231 52412 232 33748 233 30231 234 47516 235 19758 236 58414 237 66336 238 44350 239 46902 240 28009 241 79459 242 16601 243 16231 244 30400 245 51551 246 4140 247 70520 248 2087 249 48034 250 76037 251 51947 252 59486 253 26215 254 14405 255 46677 256 99235 257 69396 258 71229 259 61691 260 32204 261 88579 262 79177 263 70627 264 46897 265 114004 266 40241 267 38223 268 77525 269 86222 270 7776 271 102900 272 35766 273 81892 274 77777 275 44477 276 82384 277 28037 278 100582 279 26683 280 129296 281 67203 282 81756 283 52902 284 128130 285 43492 286 66932 287 22577 288 46173 289 107792 290 13082 291 118041 292 2714 293 100387 294 54725 295 139778 296 77256 297 114668 298 43582 299 86879 300 92213 301 19760 302 74304 303 173377 304 112484 305 108362 306 113202 307 56031 308 46856 309 161834 310 140544 311 124207 312 86172 313 128663 314 96885 315 191789 316 57426 317 59822 318 151529 319 151500 320 10353 321 112566 322 166281 323 75055 324 149525 325 125542 326 163710 327 45562 328 64521 329 138230 330 39362 331 167663 332 70610 333 239312 334 100111 335 137891 336 95129 337 201854 338 100628 339 131639 340 31092 341 68943 342 211309 343 33645 344 192371 345 90962 346 3506 347 196793 348 127024 349 246858 350 113239 351 210062 352 70628 353 185029 354 171094 355 26884 356 115643 357 292951 358 178091 359 183662 360 162051 361 199668 362 131781 363 67286 364 284056 365 278952 366 191109 367 152228 368 225335 369 187770 370 313907 371 117750 372 81040 373 91901 374 229964 375 281184 376 43263 377 257381 378 13694 379 240505 380 262460 381 147867 382 279104 383 189121 384 322739 385 76644 386 92397 387 225733 388 54690 389 272017 390 164542 391 425240 392 146980 393 226330 394 164528 395 311740 396 212505 397 245724 398 42447 399 101469 400 393173 401 76464 402 306091 403 215533 404 4508 405 366114 406 269052 407 421383 408 163774 409 369607 410 111811 411 368878 412 304928 413 36269 414 176551 415 481392 416 160805 417 276412 418 395104 419 238737 420 340413 421 282483 422 95544 423 482012 424 56135 425 192943 426 525030 427 288880 428 259988 429 381550 430 207813 431 345669 432 501517 433 280066 434 263214 435 113161 436 138722 437 458974 438 500748 439 115500 440 425254 441 17992 442 91226 443 480849 444 406069 445 276422 446 302033 447 499908 448 280604 449 603521 450 125583 451 402037 452 130805 453 359878 454 322055 455 75309 456 430967 457 349685 458 729916 459 212887 460 362619 461 275375 462 472904 463 420142 464 440230 465 57464 466 317515 467 147332 468 701774 469 562770 470 158926 471 477280 472 465062 473 5763 474 272252 475 653531 476 533136 477 699111 478 234066 479 628551 480 173609 481 697062 482 154436 483 524966 484 48583 485 264909 486 524235 487 771932 488 21147 489 322651 490 528401 491 421334 492 794254 493 130378 494 346937 495 564234 496 566280 497 134208 498 795056 499 152623 500 462024 501 947375 502 429988 503 431748 504 628234 505 452389 506 610779 507 784828 508 606246 509 498891 510 156542 511 206288 512 868216 513 861279 514 270920 515 685506 516 523049 517 23502 518 250377 519 910916 520 617023 521 495924 522 653692 523 864635 524 410576 525 1082040 526 200900 527 815975 528 183212 529 562120 530 581590 531 102799 532 669017 533 694913 534 1217160 535 329117 536 304700 537 569147 538 866830 539 149410 540 448391 541 706169 542 787653 543 761576 544 77213 545 695541 546 211408 547 1209543 548 1075289 549 309546 550 730652 551 937251 552 7338 553 470371 554 1126422 555 1001570 556 1131339 557 682147 558 330850 559 1038848 560 264754 561 930988 562 1262260 563 318223 564 373372 565 878201 566 64614 567 391463 568 1066967 569 1212092 570 70631 571 613466 572 958850 573 632160 574 1512087 575 215852 576 498058 577 912244 578 1075362 579 186748 580 1279381 581 364347 582 1006046 583 1649624 584 631040 585 699432 586 1009226 587 919721 588 1042702 589 1205587 590 1225195 591 906456 592 214636 593 302506 594 1573406 595 1438827 596 351632 597 579059 598 1082006 599 1153032 600 30520 601 601765 602 1653287 603 922828 604 859001 605 1320616 606 1452267 607 593345 608 1872503 609 315025 610 543923 611 1567554 612 254163 613 861953 614 1013733 615 139245 616 1019795 617 1308817 618 1978932 619 804219 620 658098 621 431268 622 876842 623 1773516 624 413482 625 712800 626 1039530 627 1415414 628 1279554 629 103009 630 1421639 631 299980 632 2024312 633 428379 634 1132706 635 1967420 636 572402 637 1100700 638 1788373 639 9296 640 789607 641 1885431 642 1004483 643 1802895 644 1791906 645 1508427 646 959083 647 463035 648 1674768 649 397530 650 1787568 651 2205059 652 766789 653 820379 654 1432367 655 85399 656 708850 657 570530 658 2054767 659 1867795 660 190085 661 1117769 662 1442500 663 1678772 664 783470 665 934897 666 2756007 667 348737 668 1683020 669 706992 670 1443817 671 1063141 672 1955844 673 257502 674 2015264 675 791123 676 2043067 677 2787810 678 914519 679 1109288 680 1587397 681 1769520 682 1729285 683 1821812 684 2343564 685 1588882 686 291941 687 1553773 688 438191 689 2750526 690 2343299 691 718440 692 2083389 693 1156196 694 1675765 695 2368822 696 39433 697 821520 698 1314437 699 2894057 700 1360459 701 1444965 702 2525369 703 2377618 704 847673 705 3145411 706 484955 707 1337640 708 2881907 709 349437 710 1300446 711 924341 712 1715526 713 187214 714 1529640 715 2206755 716 2361363 717 3148035 718 246218 719 1783408 720 1270374 721 1761081 722 604360 723 1328996 724 3431586 725 360847 726 999974 727 1109913 728 1510757 729 2454480 730 2095451 731 1299576 732 136529 733 2748252 734 421459 735 3302383 736 1050496 737 2518997 738 3470553 739 1015356 740 1634005 741 3266100 742 11732 743 1292325 744 3076125 745 2078622 746 3131350 747 325269 748 2784285 749 3107357 750 1765467 751 642033 752 2642589 753 588390 754 3284448 755 3737489 756 1678692 757 1681025 758 2286030 759 2591297 760 112170 761 1749411 762 821244 763 3786089 764 2830824 765 448603 766 1964318 767 2965523 768 2852101 769 1753388 770 1364892 771 4843022 772 551941 773 3281670 774 993395 775 2241849 776 1874359 777 3430290 778 352198 779 3114683 780 1603186 781 3925008 782 4590111 783 2011535 784 1310002 785 1726061 786 3686836 787 2449983 788 3257714 789 1179721 790 2796751 791 2712472 792 4289577 793 2702583 794 394084 795 3232049 796 627460 797 4664645 798 3733421 799 1389046 800 3861254 801 2186844 802 2552421 803 4600394 804 50687 805 1393143 806 2676615 807 4914618 808 948807 809 1979924 810 2368925 811 4620713 812 3807440 813 3400292 814 1198527 815 5148763 816 537813 817 734713 818 3479885 819 2982760 820 5106096 821 476501 822 1891242 823 1933295 824 2074689 825 2828819 826 250020 827 2261216 828 4313267 829 4109807 830 4911316 831 686558 832 3682617 833 2347265 834 3118377 835 839013 836 1984594 837 6348743 838 588396 839 2196037 840 1696713 841 2169894 842 4130862 843 3356704 844 2926040 845 179830 846 5081109 847 586591 848 5269437 849 2336582 850 5213505 851 5936855 852 1739545 853 2394129 854 5749861 855 14742 856 2069533 857 4909142 858 4064968 859 5277222 860 924698 861 4253482 862 6049131 863 3132623 864 882715 865 4090743 866 859880 867 5816057 868 6170612 869 1491994 870 3424462 871 3257066 872 3578020 873 5416878 874 146526 875 3912760 876 1168733 877 6721612 878 4226451 879 963913 880 3349045 881 5762619 882 4720090 883 3653264 884 1969108 885 8252542 886 1240031 887 857255 888 3366430 889 6116768 890 1382651 891 3422784 892 3206062 893 5835291 894 477992 895 2274343 896 4733512 897 3073951 898 7211428 899 7389116 900 4555083 901 2486997 902 1856890 903 2640955 904 7239230 905 3718738 906 5779215 907 2928717 908 4425770 909 3985065 910 7566844 911 4477605 912 528278 913 2068371 914 6349923 915 889288 916 7705255 917 2636583 918 5833025 919 2570038 920 5709268 921 6893795 922 3960133 923 3829226 924 8539298 925 64855 926 2302166 927 5154535 928 8128171 929 2380486 930 4370699 931 2847494 932 3798732 933 8148384 934 5978156 935 7126811 936 3289289 937 1678291 938 8241416 939 1540846 940 1096832 941 6475931 942 6187581 943 8769636 944 644796 945 4227791 946 2836380 947 4333230 948 115975 949 4561509 950 331739 951 4417804 952 3299186 953 8057232 954 6939325 955 7531445 956 1670040 957 7184382 958 4179221 959 6193733 960 5354372 961 1154908 962 4000647 963 2924389 964 11312947 965 939394 966 6487419 967 4491939 968 2551726 969 3083445 970 6773703 971 5272121 972 6126657 973 235514 974 3340187 975 9048738 976 809521 977 8244484 978 4837647 979 10191692 980 9887878 981 2894201 982 3465721 983 9813987 984 18460 985 3250046 986 7681808 987 7596847 988 8664430 989 2290023 990 2342484 991 6399136 992 11252760 993 5389597 994 1204010 995 6226164 996 6830608 997 1241848 998 9983230 999 9958538 1000 894124