1000
86 569 759 320 432 191 84 346 955 663 668 789 373 172 357 198 383 766 957 544 768 387 481 556 607 227 321 63 323 634 70 375 874 888 534 650 366 335 563 595 348 232 640 215 238 77 189 472 252 985 148 368 947 759 268 906 213 310 369 769 543 262 862 284 664 158 741 740 373 143 435 695 725 836 366 739 13 17 769 848 340 591 826 543 615 84 986 740 701 425 212 877 836 588 369 654 965 61 817 10 518 710 593 874 50 625 636 579 752 695 349 791 650 612 827 327 540 139 877 893 368 458 805 979 181 733 54 957 318 507 463 38 972 536 650 500 272 833 582 441 498 414 8 40 791 879 104 741 723 675 421 806 288 9 487 150 525 49 152 415 262 642 149 101 309 586 700 70 431 49 462 315 111 934 952 108 575 283 378 64 723 594 559 791 129 849 99 220 100 324 597 689 288 536 406 99 534 690 722 722 363 940 626 978 179 99 957 995 696 193 23 374 907 161 399 302 650 894 635 783 528 282 196 499 615 776 859 384 894 593 817 100 128 292 997 174 180 530 692 910 974 555 910 827 950 774 71 367 173 788 419 636 143 356 151 264 414 228 711 445 809 572 893 486 286 547 702 689 435 392 280 417 984 849 867 678 258 734 633 327 338 427 291 292 277 141 646 879 717 979 47 258 636 12 968 992 496 150 357 640 565 194 826 626 525 513 860 703 299 690 665 97 850 894 355 621 734 962 335 470 915 16 367 646 405 398 729 886 397 484 150 92 104 377 61 167 389 330 193 440 682 225 362 897 809 628 898 303 904 283 472 635 919 554 108 442 812 106 412 746 233 782 487 518 336 566 439 57 859 765 405 210 671 289 463 617 263 98 781 259 594 881 538 162 585 564 88 59 180 907 480 332 192 732 760 300 803 251 439 128 546 75 992 11 296 301 764 735 987 784 204 267 763 755 233 432 323 199 618 772 977 336 388 218 116 324 332 870 879 242 52 408 992 872 677 346 213 560 214 499 987 411 516 374 522 667 552 959 494 187 683 363 336 739 636 969 80 466 575 676 387 187 337 274 317 4 614 995 150 181 945 649 130 851 832 348 464 315 756 888 499 380 553 595 623 791 820 721 700 656 729 502 458 200 305 788 571 940 708 504 26 570 834 819 9 872 915 59 985 568 609 580 797 354 633 977 706 771 381 20 10 213 522 200 979 667 666 542 686 314 554 254 230 430 929 633 373 319 439 579 32 966 612 353 189 376 319 733 305 581 338 891 439 532 310 628 886 732 897 478 428 527 892 483 900 66 574 964 336 795 274 788 574 728 817 121 250 875 738 62 276 330 320 155 473 50 859 530 266 619 467 105 247 866 774 703 144 566 964 201 477 852 586 927 646 868 118 611 984 601 574 807 198 793 457 200 704 975 169 527 340 341 853 177 373 447 20 82 901 603 376 145 64 654 530 373 985 885 737 190 925 717 506 956 534 772 763 715 264 442 880 599 823 914 394 958 242 932 654 565 627 790 47 932 152 391 633 753 866 372 549 927 412 267 657 158 359 878 411 766 965 304 674 903 74 553 815 390 218 256 52 126 136 134 659 508 903 702 76 889 708 620 584 530 746 423 491 333 861 807 640 256 398 262 82 719 432 69 295 470 749 535 992 76 719 661 753 679 520 738 401 770 132 263 146 850 576 841 347 866 17 4 59 797 229 840 522 685 2 274 861 792 173 238 368 494 330 800 455 457 732 609 717 210 449 713 351 736 691 21 488 875 10 288 464 537 737 554 983 660 565 867 558 236 644 468 780 627 327 514 123 624 740 603 883 911 928 855 800 796 37 200 281 867 931 249 819 540 565 931 891 616 827 602 826 177 708 833 209 15 243 397 307 357 892 6 330 548 775 180 748 974 951 62 269 975 800 522 844 789 664 603 786 130 242 53 240 621 431 613 265 579 51 24 874 660 122 512 163 587 438 173 82 56 397 454 196 99 544 9 299 617 344 559 176 900 452 559 324 273 611 598 496 907 559 697 611 296 248 656 849 940 163 655 624 832 88 875 964 695 299 848 657 250 853 801 685 861 657 391 976 763 177 587 375 526 908 892 614 329 145 416 897 616 851 978 500 167 444 806 240 763 807 349 802 564 887 493 932 632 167 402 397 392 299 894 962 878 270 390 207 255 299 523 335 845 115 182 905 986 233 722 971 211 856 756 757 158 49 600 133 898 46 328 114 563 827 515 147 496 507 573 781 752 943 889 49 756 740 940 286 179 204 169 16 567 367 725 327 77