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