const maxg=15;
       maxu=pred(longint(1) shl maxg);
var ti,tn,i,n,g,goal:longint;
     bad:array[0..maxu] of boolean;
     mask:array[0..15] of longint;
procedure search1(sc:longint);
var i:longint;
begin
   if bad[sc] then exit;
   bad[sc]:=true;
   for i:=0 to pred(g) do
     if sc and mask[i]<>0 then search1(sc xor mask[i]);
end;
function value(d:longint):longint;
var i,res,ever2:longint;
begin
   ever2:=0;
   res:=0;
   for i:=0 to pred(g) do
     if (d and mask[i])<>0 then begin
       inc(res);
       if (goal and mask[i])=0 then begin
         inc(res);
         inc(ever2);
       end;
     end;
   if ever2>0 then dec(res);
   if ever2>1 then dec(res);
   value:=res;
end;
procedure search;
var best,i:longint;
begin
   best:=500;
   for i:=0 to pred(mask[g]) do
     if not bad[i] then
       if value(i)<best then best:=value(i);
   writeln(best);
end;
function readit:longint;
var c:char;
     i,res:longint;
begin
   res:=0;
   for i:=1 to g do begin
     read(c);
     res:=(res shl 1)+(ord(c)-48);
   end;
   readln;
   readit:=res;
end;
begin
   for i:=0 to 15 do mask[i]:=longint(1) shl i;
   readln(tn);
   for ti:=1 to tn do begin
     readln(n,g);
     goal:=readit;
     fillchar(bad,sizeof(bad),0);
     dec(n);
     for i:=1 to n do search1(pred(mask[g]) xor (readit xor goal));
     search;
   end;
end.