1000
72 586 42 845 680 24 613 775 278 703 629 36 31 835 465 288 368 32 751 662 688 675 90 541 11 492 606 33 505 182 379 133 270 282 720 368 163 57 131 270 270 217 942 457 501 18 187 583 328 385 20 877 776 85 668 436 586 280 186 83 25 104 600 869 795 350 534 813 987 78 572 399 135 89 792 369 418 191 957 82 500 9 517 913 136 862 895 505 207 157 668 475 836 123 103 885 935 348 228 978 86 167 587 874 697 733 356 132 732 386 404 921 667 600 649 114 696 880 739 501 345 826 276 731 32 215 457 670 811 341 265 753 613 523 766 416 148 70 137 963 149 987 35 245 516 821 777 753 369 434 879 951 607 889 257 835 159 478 102 558 909 361 974 258 936 236 805 360 744 988 896 77 51 266 992 812 569 378 820 29 977 635 796 695 435 520 348 929 440 822 885 432 246 480 866 540 408 512 809 819 573 111 880 314 40 846 59 393 641 405 723 302 330 252 217 349 100 328 380 87 618 585 63 481 974 970 782 39 827 144 290 447 92 102 898 210 699 472 965 65 148 79 686 397 986 637 439 146 938 193 369 308 815 685 299 211 310 374 817 659 907 44 399 215 819 290 782 766 524 8 309 222 641 544 468 529 651 797 702 789 653 499 429 57 206 931 130 133 300 205 92 232 647 547 697 168 107 811 619 606 763 438 565 567 434 679 550 610 11 558 653 367 13 597 390 653 111 714 731 607 594 479 751 751 958 271 615 364 141 769 522 816 112 865 378 117 742 406 971 249 740 166 44 743 386 345 412 184 602 84 991 306 670 948 961 904 970 790 530 938 472 772 394 414 483 979 574 895 542 75 796 213 957 686 804 789 204 333 144 595 895 671 366 909 74 867 682 305 794 961 689 106 947 396 396 575 236 890 313 541 480 79 577 966 998 838 269 761 35 890 490 292 262 764 23 944 484 230 596 268 990 64 981 92 784 488 479 171 715 527 699 935 733 10 193 133 111 694 414 924 207 848 913 381 119 235 234 483 110 763 708 728 566 730 934 969 494 865 84 771 944 474 475 342 77 963 12 264 832 678 88 853 952 774 902 126 866 76 680 143 527 699 285 854 746 945 19 817 725 79 210 334 931 131 25 497 889 308 427 610 609 869 314 669 799 510 200 950 120 167 217 852 143 238 613 741 738 347 580 794 188 954 115 517 133 89 142 752 839 379 622 112 874 932 757 570 642 326 808 973 407 739 341 80 966 620 468 645 198 393 834 374 661 50 844 670 988 757 490 236 736 481 268 340 739 651 257 302 675 535 53 11 313 145 650 381 300 516 723 982 462 963 941 340 287 894 935 307 386 896 676 388 453 726 366 861 68 930 757 153 456 417 216 809 28 89 459 82 585 872 970 401 618 985 933 485 274 288 484 868 893 919 413 192 925 658 635 99 406 561 609 721 379 523 672 502 802 163 414 591 789 902 592 709 203 578 249 215 199 998 74 487 831 365 588 713 223 92 588 711 511 919 343 920 899 607 519 458 489 79 644 93 784 255 230 106 967 680 969 948 164 296 850 230 966 353 730 790 717 814 761 512 360 269 124 205 839 691 642 438 3 900 76 851 970 618 315 25 112 345 582 180 178 192 212 321 516 122 6 343 606 878 249 782 914 763 995 345 321 304 723 128 167 811 118 442 348 649 536 57 284 518 448 950 777 965 815 678 448 569 761 69 226 309 100 658 43 601 402 651 832 406 930 683 788 117 516 448 284 506 140 954 653 263 638 842 866 558 875 383 874 174 443 742 673 635 460 275 605 175 969 747 460 533 222 644 588 239 723 71 212 86 96 933 529 227 792 520 179 28 97 747 194 305 211 685 946 887 422 161 439 692 193 569 821 652 352 21 806 724 302 751 626 789 932 369 210 716 264 193 286 791 513 939 952 146 793 759 344 66 181 541 64 18 978 366 667 469 792 213 130 235 219 542 624 215 967 566 743 384 508 612 353 375 338 358 676 72 631 678 528 677 879 334 986 599 867 393 582 726 109 85 928 19 82 278 668 4 473 525 552 240 924 609 846 203 885 332 646 276 803 393 459 958 988 316 388 772 812 755 446 904 823 659 552 981 676 567 520 531 820 637 348 180 249 24 364 509 489 581 518 70 493 704 465 886 237 799 438 993 407 867 43 915 15 658 571 377 657 631 539 142 861 526 757 451 931 314 802 491 207 58 4 422 598 724 938 476 378 184 520 69 649 153 918 478 557 959 231 583 320 472 685 451 247 208 154 191 289 943