#include<iostream>
#include<stdio.h>
using namespace std;
#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 500//最大顶点个数
typedef unsigned int VertexType; //
typedef unsigned int VRType; //
typedef struct{
VertexType arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵
int vexnum,arcnum; //图的当前顶点数和弧数
}MGraph;
struct {
VertexType adjvex; //储存衣服在U中的顶点
VRType lowcost; //权值
}closedge[MAX_VERTEX_NUM];
int minimum(MGraph &G)
{
int k;
for(k=0;k<G.vexnum;k++)
if(closedge[k].lowcost!=0)break;
for(int i=k;i<G.vexnum;i++)
{
if(closedge[k].lowcost>closedge[i].lowcost&&closedge[i].lowcost!=0)
k=i;
}
return k;
}
void MiniSpanTree_PRIM(MGraph &G,unsigned int save[])
{
int k=0,l=0; //定位k值
int j;
for(j=0;j<G.vexnum;++j) //辅助数组初始化
if(j!=k)
{
closedge[j].adjvex=k;
closedge[j].lowcost=G.arcs[k][j];
}
closedge[k].lowcost=0; //初始，U={u}
/*
for(j=0;j<G.vexnum;++j)
cout<<closedge[j].adjvex<<" "<<closedge[j].lowcost<<endl;
*/
for(int i=1;i<G.vexnum;++i) //选择其余G.vexnum-1个顶点
{
k= minimum(G); //求出T的下一个结点：第K个结点
//cout<<closedge[k].lowcost<<endl;//输出生成树的边
save[l]=closedge[k].lowcost;
l++;
closedge[k].lowcost=0; //第k项点并入U集
/*
for(j=0;j<G.vexnum;++j)
cout<<closedge[j].adjvex<<" "<<closedge[j].lowcost<<endl;
*/
for(j=0;j<G.vexnum;++j)
{
if(G.arcs[k][j]<closedge[j].lowcost) //新顶点并入U后重新选择小边
{
closedge[j].adjvex=k;
closedge[j].lowcost=G.arcs[k][j];
}
}
}
}
void exchange(unsigned int &a,unsigned int &b)
{
unsigned int temp;
temp=a;
a=b;
b=temp;
}
int Sort(unsigned int k[],int vex)
{
unsigned int flag;
flag =k[0];
for(int i=1;i<vex-1;i++)
if(flag<k[i])
exchange(flag,k[i]);
return flag;
}
void CreatMGraph(MGraph &G,int vex)
{
int i,j;
for(i=0;i<vex;i++)
for(j=0;j<vex;j++)
cin>>G.arcs[i][j];
G.vexnum=vex;
G.arcnum=vex;
}
int main()
{
int i;
cin>>i;
getchar();
for(int j=0;j<i;j++)
{
int vex;
int answer;
unsigned int save[MAX_VERTEX_NUM]={0};
cin>>vex;
MGraph G;
CreatMGraph(G,vex);
MiniSpanTree_PRIM(G,save);
answer=Sort(save,vex);
cout<<answer<<endl;
}
//getchar();
//getchar();
return 0;
}
