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