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