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