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