0 0 1 2 2 5 3 7 4 17 5 15 6 37 7 7 8 18 9 43 10 101 11 63 12 34 13 24 14 197 15 115 16 257 17 36 18 18 19 183 20 401 21 32 22 102 23 60 24 577 25 315 26 677 27 80 28 162 29 423 30 70 31 52 32 46 33 116 34 102 35 615 36 1297 37 144 38 22 39 763 40 1601 41 31 42 358 43 44 44 162 45 1015 46 102 47 37 48 466 49 1203 50 102 51 1303 52 546 53 288 54 2917 55 108 56 3137 57 20 58 678 59 1743 60 290 61 1863 62 774 63 404 64 258 65 2115 66 4357 67 456 68 42 69 2383 70 42 71 2523 72 83 73 61 74 5477 75 128 76 162 77 600 78 1222 79 3123 80 210 81 212 82 274 83 73 84 7057 85 3615 86 582 87 764 88 1554 89 252 90 8101 91 144 92 1698 93 180 94 8837 95 4515 96 722 97 948 98 135 99 44 100 210 101 5103 102 2086 103 1068 104 402 105 188 106 678 107 236 108 2338 109 472 110 12101 111 164 112 211 113 1284 114 358 115 408 116 13457 117 44 118 562 119 172 120 14401 121 7323 122 247 123 113 124 15377 125 616 126 15877 127 1620 128 147 129 212 130 16901 131 8583 132 63 133 97 134 17957 135 716 136 402 137 1884 138 311 139 9663 140 1170 141 9943 142 151 143 416 144 322 145 10515 146 21317 147 2168 148 355 149 672 150 22501 151 892 152 4626 153 2348 154 678 155 336 156 24337 157 53 158 4998 159 12643 160 25601 161 1012 162 215 163 2664 164 2082 165 13615 166 1638 167 2796 168 1134 169 14283 170 28901 171 14623 172 163 173 121 174 167 175 15315 176 30977 177 261 178 6342 179 472 180 32401 181 16383 182 58 183 221 184 33857 185 268 186 1222 187 289 188 7074 189 392 190 2790 191 85 192 179 193 156 194 678 195 19015 196 978 197 3888 198 7846 199 19803 200 211 201 20203 202 8166 203 337 204 41617 205 21015 206 42437 207 864 208 531 209 21843 210 44101 211 312 212 195 213 369 214 1158 215 828 216 147 217 301 218 1906 219 23983 220 1698 221 24423 222 9862 223 4980 224 50177 225 1508 226 3942 227 5160 228 323 229 2032 230 52901 231 26683 232 2158 233 157 234 3238 235 576 236 55697 237 185 238 11334 239 15 240 57601 241 372 242 88 243 1188 244 2082 245 30015 246 902 247 6108 248 12306 249 1100 250 62501 251 128 252 995 253 217 254 582 255 117 256 65537 257 1328 258 13318 259 1992 260 67601 261 34063 262 13734 263 6924 264 69697 265 125 266 582 267 7136 268 35 269 472 270 72901 271 36723 272 14802 273 293 274 582 275 37815 276 4498 277 7680 278 88 279 38923 280 78401 281 3052 282 3186 283 8016 284 80657 285 2408 286 678 287 8244 288 371 289 41763 290 2310 291 3272 292 17058 293 125 294 183 295 876 296 2178 297 8828 298 17766 299 44703 300 90001 301 600 302 88 303 9188 304 7122 305 436 306 93637 307 49 308 18978 309 47743 310 5670 311 492 312 19474 313 205 314 98597 315 49615 316 1698 317 793 318 814 319 133 320 7890 321 51523 322 327 323 10440 324 1042 325 52815 326 106277 327 61 328 21522 329 54123 330 8390 331 1920 332 4414 333 873 334 678 335 56115 336 275 337 325 338 391 339 1592 340 115601 341 1152 342 311 343 201 344 6978 345 59515 346 9222 347 12048 348 515 349 60903 350 122501 351 500 352 24786 353 757 354 1222 355 1096 356 9762 357 2556 358 25638 359 4972 360 179 361 3852 362 26214 363 13184 364 3618 365 2328 366 1478 367 13476 368 5422 369 5252 370 8070 371 68823 372 2147 373 13920 374 1158 375 70315 376 3858 377 301 378 63 379 71823 380 930 381 584 382 467 383 14676 384 147457 385 5716 386 148997 387 905 388 30114 389 2640 390 1798 391 76443 392 499 393 3096 394 183 395 385 396 156817 397 15768 398 2455 399 79603 400 160001 401 133 402 32326 403 265 404 9618 405 82015 406 164837 407 3320 408 215 409 83643 410 1830 411 177 412 2019 413 505 414 1798 415 86115 416 2898 417 17396 418 275 419 2184 420 176401 421 433 422 35622 423 653 424 13842 425 90315 426 1222 427 18240 428 36642 429 5432 430 184901 431 612 432 1498 433 18756 434 14502 435 94615 436 190097 437 133 438 120 439 732 440 193601 441 97243 442 999 443 164 444 197137 445 99015 446 11718 447 102 448 435 449 100803 450 471 451 101703 452 1443 453 20528 454 3942 455 6108 456 1042 457 4184 458 41958 459 105343 460 451 461 106263 462 42694 463 134 464 215297 465 1556 466 217157 467 313 468 8766 469 1120 470 220901 471 110923 472 2643 473 1741 474 224677 475 3088 476 643 477 441 478 45702 479 1380 480 13570 481 4020 482 9298 483 617 484 3282 485 688 486 18182 487 685 488 47634 489 573 490 240101 491 960 492 48418 493 4868 494 1158 495 1316 496 246017 497 1477 498 455 499 233 500 142 501 3104 502 3895 503 25308 504 1042 505 4428 506 15078 507 157 508 51618 509 744 510 8998 511 1092 512 164 513 26324 514 15558 515 116 516 1042 517 26736 518 10738 519 134683 520 1170 521 135723 522 54502 523 1633 524 259 525 10616 526 1158 527 27780 528 4307 529 139923 530 1350 531 8312 532 11326 533 28416 534 9862 535 143115 536 287297 537 28844 538 152 539 5040 540 1026 541 11272 542 1479 543 5904 544 295937 545 148515 546 1478 547 29928 548 3555 549 4112 550 2790 551 11692 552 563 553 637 554 23622 555 896 556 309137 557 97 558 62278 559 156243 560 211 561 4292 562 535 563 1129 564 24482 565 289 566 1158 567 2493 568 123 569 161883 570 324901 571 163023 572 65442 573 32840 574 19398 575 165315 576 331777 577 217 578 727 579 167623 580 355 581 168783 582 819 583 877 584 341057 585 1388 586 9318 587 34464 588 69154 589 2040 590 26790 591 10292 592 2451 593 561 594 352837 595 177015 596 3618 597 1265 598 1975 599 253 600 2450 601 892 602 72486 603 2817 604 3858 605 1128 606 107 607 7376 608 4371 609 185443 610 1830 611 2632 612 611 613 769 614 1638 615 956 616 131 617 38076 618 15282 619 14752 620 1698 621 201 622 77382 623 1093 624 9538 625 11508 626 13542 627 39320 628 78882 629 15232 630 5510 631 199083 632 1247 633 2381 634 401957 635 5488 636 404497 637 40584 638 81414 639 204163 640 2898 641 205443 642 408 643 8276 644 414737 645 16016 646 417317 647 1069 648 755 649 210603 650 903 651 992 652 85026 653 42648 654 427717 655 613 656 2898 657 193 658 6679 659 313 660 291 661 218463 662 87654 663 509 664 1602 665 5436 666 8422 667 2641 668 1391 669 223783 670 1350 671 17332 672 2483 673 45300 674 454277 675 968 676 26898 677 45840 678 1127 679 7980 680 462401 681 17852 682 66 683 46656 684 132 685 234615 686 470597 687 549 688 2355 689 237363 690 476101 691 1432 692 95778 693 137 694 37062 695 241515 696 484417 697 158 698 97446 699 244303 700 490001 701 265 702 98566 703 757 704 495617 705 1556 706 12198 707 789 708 3491 709 6832 710 2311 711 252763 712 1971 713 1789 714 509797 715 255615 716 512657 717 617 718 1235 719 4932 720 39890 721 4324 722 903 723 4041 724 2082 725 1248 726 1478 727 3133 728 106002 729 6524 730 4998 731 1072 732 21438 733 4153 734 14598 735 15908 736 41682 737 1909 738 108934 739 273063 740 547601 741 1232 742 3831 743 249 744 32578 745 277515 746 139 747 1409 748 675 749 21592 750 562501 751 282003 752 6675 753 56708 754 5958 755 1368 756 1618 757 237 758 114918 759 22172 760 577601 761 17052 762 8951 763 58224 764 583697 765 5576 766 20262 767 757 768 23598 769 17412 770 14502 771 345 772 244 773 59760 774 3238 775 1792 776 186 777 60380 778 7143 779 303423 780 608401 781 304983 782 467 783 1701 784 614657 785 325 786 36358 787 505 788 292 789 2240 790 2502 791 312843 792 125458 793 12584 794 2982 795 689 796 5922 797 63528 798 216 799 319203 800 790 801 24692 802 855 803 3817 804 10658 805 1168 806 5862 807 528 808 3571 809 1660 810 1798 811 673 812 7779 813 585 814 50982 815 332115 816 665857 817 66756 818 159 819 335383 820 1123 821 337023 822 743 823 67740 824 1843 825 6476 826 682277 827 5281 828 137122 829 89 830 9510 831 1220 832 27694 833 69396 834 2342 835 4008 836 1698 837 354 838 140454 839 3340 840 54290 841 353643 842 141798 843 301 844 1698 845 9688 846 42118 847 71748 848 143826 849 5012 850 535 851 3832 852 3587 853 242 854 42918 855 365515 856 8322 857 441 858 5111 859 2832 860 739601 861 370663 862 148614 863 374 864 746497 865 6196 866 57702 867 75176 868 30142 869 377583 870 18502 871 493 872 152082 873 76220 874 2118 875 382815 876 59042 877 76920 878 2967 879 29732 880 45570 881 388083 882 71 883 77976 884 4242 885 391615 886 4518 887 2749 888 9299 889 397 890 792101 891 1712 892 12259 893 437 894 21638 895 4228 896 3138 897 4757 898 161286 899 4104 900 3602 901 405903 902 12535 903 1197 904 13458 905 141 906 820837 907 16460 908 164898 909 413143 910 828101 911 421 912 166354 913 83364 914 487 915 2492 916 28962 917 84096 918 2611 919 253 920 846401 921 424123 922 232 923 85200 924 323 925 427815 926 14118 927 85940 928 13267 929 431523 930 864901 931 122 932 6954 933 87056 934 21318 935 437115 936 876097 937 87804 938 1335 939 25952 940 30498 941 34072 942 177478 943 3564 944 5286 945 293 946 894917 947 89688 948 228 949 450303 950 902501 951 452203 952 4467 953 90828 954 70022 955 456015 956 1507 957 1429 958 1239 959 459843 960 921601 961 1540 962 185094 963 92744 964 3282 965 529 966 933157 967 7213 968 1055 969 16220 970 631 971 2592 972 188962 973 5593 974 32742 975 11636 976 13122 977 1861 978 191302 979 479223 980 73890 981 481183 982 2291 983 7453 984 18322 985 485115 986 972197 987 1665 988 195234 989 489063 990 57670 991 491043 992 2131 993 98 994 3942 995 6856 996 707 997 99408 998 6903 999 365 1000 10002