===INPUT===
2
100 10
364 673 491 804 471 840 449 469 325 884 678 94 736 988 635 502 730 505 960 143 915 663 676 213 72 487 59 594 880 35 497 924 272 41 325 618 849 467 682 219 472 974 482 279 615 26 892 938 835 593 784 534 310 228 144 111 901 234 185 173 356 274 794 366 512 732 925 931 893 619 331 204 521 997 117 469 617 534 392 531 284 217 601 218 701 33 281 969 92 159 882 857 358 93 803 505 644 258 945 965 
100 10
818 911 583 528 817 418 686 848 991 872 16 209 629 449 850 765 257 142 785 354 525 598 654 180 864 754 68 813 444 253 681 794 671 624 644 760 150 285 166 607 975 906 596 757 334 712 684 214 906 125 373 299 904 79 716 528 681 954 549 691 136 468 302 497 334 846 514 859 529 533 709 554 946 235 827 190 383 88 590 221 177 52 792 226 542 713 389 596 753 429 68 233 160 6 688 3 982 633 450 481
===OUTPUT===
96
101
===END===