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