1000 999 996 820 765 568 953 412 16 225 215 677 603 774 311 708 74 25 210 116 671 762 638 694 253 588 582 803 257 949 502 421 372 55 327 984 465 263 503 187 662 750 389 263 853 94 827 327 112 199 341 74 96 743 147 422 194 728 226 510 369 917 908 675 975 765 167 889 540 580 732 220 208 487 648 46 579 602 175 93 934 660 434 308 323 558 942 779 470 35 666 581 44 892 288 755 745 448 339 3 271 993 307 360 7 264 624 394 416 475 326 468 940 983 350 108 633 955 103 900 189 98 22 347 763 527 426 115 958 367 475 238 816 491 303 191 471 874 206 974 543 392 597 647 835 240 715 681 609 707 13 174 307 102 283 787 202 245 680 295 754 444 946 388 689 175 880 571 425 646 333 488 58 856 107 607 697 480 225 290 29 791 404 590 719 811 438 701 390 106 454 756 960 40 794 76 351 968 383 739 320 151 181 420 711 29 793 217 976 726 724 621 903 195 772 783 899 606 362 262 572 80 432 132 27 749 630 299 599 997 27 546 370 446 121 428 824 995 623 500 440 159 950 961 932 905 702 506 716 216 403 492 325 951 280 134 132 580 398 854 775 309 321 87 355 285 696 600 105 622 39 139 966 197 756 566 85 407 737 17 107 944 285 698 439 441 560 751 623 919 981 284 859 898 273 78 971 832 876 782 419 574 309 358 489 124 525 963 98 770 795 577 763 570 389 740 720 205 53 300 420 530 234 328 517 322 463 480 593 184 179 77 906 602 701 554 287 805 636 990 768 953 91 659 123 498 671 130 702 788 517 555 661 543 970 435 868 741 131 90 780 802 467 842 16 298 884 717 279 282 767 738 413 138 948 433 638 115 982 537 264 930 822 778 418 738 662 447 211 363 534 256 362 3 231 524 233 567 900 652 157 572 393 546 665 863 118 766 885 574 217 482 340 866 918 535 981 811 799 618 954 622 916 570 181 928 920 918 278 463 625 686 36 663 538 155 860 246 276 794 466 569 864 559 145 456 688 796 131 937 63 828 64 789 219 564 235 597 7 430 139 921 839 349 483 99 670 186 211 875 401 769 394 324 992 329 37 656 37 567 129 269 698 712 753 469 343 569 653 24 792 845 328 866 632 1 640 933 84 342 501 43 360 707 747 384 461 565 241 373 203 399 835 421 288 261 774 857 913 265 515 571 109 126 525 379 804 666 456 770 315 38 125 455 169 168 492 189 704 512 706 764 731 823 72 819 351 337 962 633 895 654 268 122 62 857 82 331 246 234 75 142 382 964 395 60 943 988 856 909 409 384 126 747 673 252 979 393 336 4 231 414 62 596 215 296 163 985 248 998 317 825 867 705 914 668 677 410 995 987 110 409 157 286 251 136 336 624 306 679 921 590 201 252 135 520 573 462 267 67 840 540 964 361 867 721 722 51 855 424 179 779 490 502 68 170 333 361 404 302 286 370 848 576 524 691 881 687 424 183 775 108 846 586 298 5 171 826 542 450 316 61 237 827 674 31 941 497 204 973 18 522 558 245 757 66 250 60 670 621 896 538 722 185 2 704 965 316 924 192 533 511 766 952 214 898 759 300 332 651 554 52 690 700 2 52 551 658 99 536 541 454 927 287 45 669 723 544 862 13 639 36 678 849 478 117 140 947 913 916 892 120 514 826 736 101 936 952 386 222 8 959 695 865 458 897 682 496 429 562 50 92 387 555 513 464 889 372 556 293 983 379 790 443 182 338 460 423 128 146 682 841 552 949 748 526 871 80 512 437 821 940 366 119 948 999 996 936 798 329 843 349 113 902 34 414 786 292 106 531 905 150 20 26 377 972 664 319 610 748 317 83 19 705 869 17 66 448 14 258 938 718 190 611 275 304 599 877 710 544 453 838 410 313 899 364 452 737 717 378 522 219 144 176 472 397 446 155 658 468 401 816 550 209 667 880 48 547 172 617 32 536 79 34 607 190 440 526 367 910 6 356 594 938 726 76 149 476 626 78 519 751 528 803 165 637 962 479 781 963 585 634 249 822 334 729 436 241 344 388 791 752 445 873 861 719 469 477 442 641 447 486 485 255 860 635 855 467 926 143 251 374 772 339 164 239 742 694 495 203 746 854 846 97 556 643 1 903 865 652 828 729 42 529 542 501 882 743 946 395 168 325 755 862 53 832 230 128 552 869 118 289 879 411 563 431 237 873 612 380 383 735 674 35 81 72 127 182 343 653 491 614 777 723 801 242 363 101 283 100 851 912 399 18 731 459 465 529 874 49 620 516 71 870 476 486 167 228 193 408 4 321 23 715 601 111 613 198 582 598 724 972 248 971 173 941 830 632 505 506 275 180 781 464 153 487 710 232 592 195 178 515 802 178 909 431 967 378 947 688 895 193 20 868 68 38 86 815 494 259 812 400 991 49 425 15 71 353 539 878 926 618 258 676 577 812 650 904 322 455 657 496 65 819 716 472 450 88 348 477 39 714 25 274 308 994 376 5 508 797 741 445 595 843 851 499 95 117 284 242 140 699 584 586 642 6 266 891 998 88 249 957 672 588 551 943 814 690 736 224 532 70 22 210 850 553 685 735 904 174 979 70 342 294 346 796 135 646 985 51 925 883 69 490 415 299 776 693 276 977 110 55 79 550 353 220 626 810 462 527 910 314 999 799 859 589 908 10 673 270 615 557 989 207 593 416 692 931 232 647 879 150 829 233 412 511 194 675 821 114 397 229 893 19 518 10 87 760 340 655 498 500 243 458 644 534 620 279 130 629 239 373 451 643 861 700 272 713 665 57 824 375 417 230 365 734 267 163 28 40 297 262 884 352 277 560 600 457 335 575 744 616 807 845 768 837 125 31 413 154 687 785 907 11 683 790 122 280 434 265 758 548 759 151 929 784 23 165 631 906 141 187 345 514 489 173 335 326 911 223 982 192 392 800 347 521 73 484 713 896 63 354 102 411 188 253 304 858 978 218 585 291 408 162 294 133 841 637 380 651 829 64 509 769 156 438 771 201 199 377 451 166 137 805 32 15 750 54 986 82 589 191 218 583 314 521 92 368 223 583 883 374 911 530 358 160 973 619 711 433 507 656 939 313 576 660 915 247 152 924 54 831 680 754 12 400 86 808 202 686 147 901 65 639 718 878 398 703 310 481 243 281 474 541 654 562 312 277 200 746 84 871 45 664 959 310 56 116 801 957 684 933 852 914 575 227 752 986 720 601 156 479 922 930 980 648 449 348 302 813 391 120 405 236 272 494 872 838 73 149 9 989 402 311 270 67 228 198 579 528 406 50 273 159 987 699 625 504 563 893 853 842 180 176 143 439 48 727 837 136 461 221 833 709 257 430 762 994 641 350 858 685 813 513 423 649 474 966 956 613 806 581 744 419 960 767 532 547 629 929 357 137 728 833 390 485 595 603 912 504 365 619 616 359 250 58 644 330 293 661 967 578 591 172 520 289 119 359 260 371 28 41 59 41 254 523 745 184 427 133 97 798 831 247 312 645 605 89 592 303 870 683 852 877 266 205 505 268 160 148 8 417 214 978 356 807 405 549 422 153 427 753 739 836 934 385 627 470 612 376 291 478 725 493 305 44 849 950 516 888 75 642 990 499 809 709 804 295 368 402 305 124 166 864 672 969 338 1000 21 89 890 481 460 296 573 758 604 43 788 787 605 282 568 453 617 177 676 452 928 773 466 236 206 991 141 785 834 977 689 442 795 974 301 170 886 598 90 318 942 847 278 604 539 221 703 196 631 885 594 789 381 887 818 444 429 561 596 945 640 337 730 352 636 497 894 902 366 628 482 834 984 961 564 627 77 882 47 297 645 290 315 292 11 850 127 668 733 649 319 951 188 341 809 100 749 81 121 997 919 935 435 364 712 96 881 657 261 958 531 907 488 386 970 533 391 887 786 406 678 186 630 606 396 112 185 387 334 457 757 553 357 396 780 146 30 969 820 557 301 91 808 459 697 587 493 162 30 955 104 105 306 213 591 695 138 169 615 509 721 771 216 473 204 33 344 566 403 917 9 876 988 154 415 733 848 213 890 212 734 614 920 331 836 992 114 134 650 783 385 259 778 839 915 197 818 932 901 776 761 945 436 382 207 164 129 152 324 260 611 345 773 894 61 371 208 103 693 111 939 183 158 426 797 935 240 1000 740 14 922 59 732 937 584 69 844 968 518 764 508 814 510 320 507 196 158 432 537 346 94 256 944 330 965 578 238 847 57 254 565 608 792 437 484 931 760 274 224 872 810 696 244 610 784 993 545 369 235 332 318 891 354 21 171 742 669 483 47 863 634 923 548 209 244 227 144 888 255 12 109 95 559 975 897 806 271 840 730 503 519 471 663 825 323 24 113 104 923 976 708 46 33 177 925 692 93 535 800 830 628 817 26 473 145 561 375 684 229 980 428 142 681 441 609 823 549 545 523 691 793 761 226 123 587 42 85 875 212 381 355 418 956 635 449 443 815 161 200 679 667 817 608 407 714 269 148 844 927 777 659 161 56 222 727 495 886 281 954 782 655 706