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