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