program tju1037;
const
  maxn=100;
var
  len:array[1..maxn,1..maxn]of longint;
  dist:array[1..maxn]of longint;
  s:set of 1..maxn;
  m,t,n,i,j,k,l:word;
  min,ans:longint;
begin
  read(m);
  for t:=1 to m do begin
    read(n);
    for i:=1 to n do
      for j:=1 to n do
        read(len[i,j]);
    dist[1]:=0;for i:=2 to n do dist[i]:=maxlongint;
    j:=1;s:=[1];ans:=0;
    for k:=2 to n do begin
      min:=maxlongint;
      for i:=2 to n do
        if not (i in s) then begin
          if len[j,i]<dist[i] then dist[i]:=len[j,i];
          if dist[i]<min then begin
            min:=dist[i];l:=i;
          end;
        end;
      inc(ans,dist[l]);s:=s+[l];j:=l;
    end;
    writeln(ans);
  end;
end.