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