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