#include <iostream>

#include <stdio.h>

#include <string.h>

#include <memory.h>

#include <algorithm>

using namespace std;

#define N 10005

#define inf 100010

int a[N][N],ans;

bool vis[N];

int dis[N],n;

bool Prim()

{

    ///初始化每条路没走过

    memset(vis,,sizeof(vis));

    ///初始化到每一点的权

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

    {

        dis[i]=inf;

    }

    ans=;

    ///从第一个点搜起。到达自己的权为0

    dis[]=;

    ///搜索每个节点，加入到集合中来

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

    {

        int tmp=inf,k=;

        ///搜索每个点，找i到达下一点的最小权

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

        {

            if(!vis[j]&&dis[j]<tmp)

            {

                tmp=dis[j];

                k=j;

            }

        }

        if(tmp==inf)        ///搜索不成功

        {

            return false;

        }

        vis[k]=true;        ///标记走过

        ans=max(ans,dis[k]);

        ///更新到每个节点的最小权

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

        {

            if(!vis[j]&&dis[j]>a[k][j])

            {

                dis[j]=a[k][j];

            }

        }

    }

}

int main()

{

    int Case;

    scanf("%d",&Case);

    while(Case--)

    {

        scanf("%d",&n);

        ans=;

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

        {

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

            {

                scanf("%d",&a[i][j]);

            }

        }

        Prim();

        cout<<ans<<endl;

    }

    return ;

}