#include <iostream>
#include <iomanip>

typedef int table15[15][15];

void findmax(table15 t,int& row, int& col, int& value, int h, int w);
void findmin(table15 t,int& row, int& col,int height,int width);

int main()
{int sets;

 cin>>sets;

 while(sets>0)
 {int TOTAL=0;
  int x, y, min,max;
  int height, width;
  table15 t;
 
 cin>>height;
 width=height;
 
 // LOAD TABLE
  for (x=0;x<height;x++)
   for (y=0;y<width;y++)
    { cin>>t[x][y];}
 
 //Loop til min is above threshold
  min=100;
  while(min<1000)
   {
    min=10000;                      //set min to huge number
 //   cout<<endl;
 
 //Print Table of Data
 //   for (int row=0;row<height;row++)     //loop through rows
 //    {
 //     for (int col=0;col<width;col++)   //loop through columns
 //      if (t[row][col]==1000)
 //       cout<<"---- ";
 //      else
 //       cout<<setw(4)<<t[row][col]<<' ';   //Print out items
 //     cout<<endl;
 //    }
 
 //Find the maximum value, row, and column
    findmax(t,x,y,max, height, width);
 if (max==0) break;
 
 //cout<<"Max ="<<x<<' '<<y<<"  **"<<max<<endl;
 //Find Min in the same row or column as the max
    findmin(t,x,y,height,width);
 min=t[x][y];
 //cout<<"Min ="<<x<<' '<<y<<"  **"<<min<<endl;
 TOTAL+=min;
 //   cout<<endl<<"*************"<<x<<' '<<y<<' '<<min<<"      "<<TOTAL<<endl;
 //"Clear" out this row
    for (int row=0;row<height;row++)
     t[row][y]=1000;
 //"Clear" out this column
    for (int col=0;col<width;col++)
     t[x][col]=1000;
 //"Clear" out this corresponding row
    for (int row=0;row<height;row++)
     t[y][row]=1000;
 //"Clear" out this corresponding column
    for (int col=0;col<width;col++)
     t[col][x]=1000;
   }
 cout<<"MaxMin=\t"<<TOTAL<<endl;
 sets--;
 }
  return 0;
}
void findmin(table15 t,int& row, int& col,int width,int height)
{int x,min=1000;
 int r,w;
 for(x=0;x<width;x++)
  if (t[row][x]<min)
   {w=x;r=row;min=t[r][w];}
 for(x=0;x<height;x++)
  if (t[x][col]<min)
   {r=x;w=col;min=t[r][w];}
 row=r;col=w;
 return;
}

void findmax(table15 t,int& row, int& col, int& value, int h, int w)
{int x,y;
 value=0;                //assume first cell is min
 for (x=0;x<h;x++)       //loop through rows
  for(y=0;y<w;y++)       //loop through columns
   if ((t[x][y]<1000)&&(value<=t[x][y]))   // if this is the new max
    {row=x;              //set row
     col=y;              //set column
     value=t[x][y];      //set value
    }
 return;
}