#include<iostream>

#include<string>

#include<vector>

#include<algorithm>

using namespace std;

//*********************************************************************

//Krushal 幷查集和最小生成树

//：：返回最小生成树最大权值

#define maxn 250005

int u[maxn];//第i条边的两个端点和权值

int v[maxn];

int w[maxn];

int r[maxn];//排序后第i小的边的序号保存在r[i]中（见下面间接排序函数cmp)

int p[maxn];//幷查集节点i对应的根节点

int m,n;//n个节点，m个边

//------------------------

int cmp(const int i,const int j){return w[i]<w[j];}//间接排序

int Find(int x){return p[x]==x ? x:p[x]=Find(p[x]);}//幷查集寻根

int Krushal(){

    int ans=-;//最小生成树最大权值

    for(int i=;i<n;i++)p[i]=i;//初始化幷查集

    for(int i=;i<m;i++)r[i]=i;//初始化边序号

    sort(r,r+m,cmp);//给边排序

    for(int i=;i<m;i++){//由小到大枚举每条边，两个端点在不同树中则合并

        int e=r[i];int x=Find(u[e]);int y=Find(v[e]);

        if(x!=y){if(ans<w[e])ans=w[e];p[x]=y;}

    }

    return ans;

}

void read(){//将m条边读入

    int a;m=;

    for(int i=;i<n;i++){

        for(int j=;j<n;j++){

            cin>>a;

            u[m]=i;v[m]=j;w[m]=a;

            m++;

        }

    }

}

//***************************************************************************

int main(){

    int T;cin>>T;

    while(T--){

        cin>>n;

        read();

        cout<<Krushal()<<'\n';

    }return ;

}