#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;

struct Adj{
    int first;
    int last;
    int len;
};
int parent[1000];
Adj adj[125000];

bool cmp(Adj a,Adj b){
        if(a.len>b.len)
            return false;
        return true;
}

int root(int chd){
        if(parent[chd]==chd)
            return chd;
        else
            return root(parent[chd]);
}

int main(){
    int ma;
    int t;
    scanf("%d",&t);
    while(t--){
            int num(0);
            int n;
            scanf("%d",&n);
            for(int i=0;i<n;i++)
                    parent[i] = i;

            for(int i=0;i<n;i++){
                    for(int j=0;j<n;j++){
                            int tmp;
                            scanf("%d",&tmp);
                            if(i<j){
                                adj[num].first = i;
                                adj[num].last = j;
                                adj[num].len = tmp;
                                num++;
                            }
                    }
            }

            sort(adj,adj+num,cmp);

            int total(0);
            ma = 0;
            for(int i=0;i<num;i++){
                    if(total==n-1)
                        break;
                    int a = adj[i].first;
                    int b = adj[i].last;
                    int c = root(a);
                    int d = root(b);
                    if(c==d)
                        continue;
                    else{
                        if(ma<adj[i].len)
                                ma = adj[i].len;
                        total++;
                        parent[c] = d;
                        //cout<<a<<" "<<b<<" "<<adj[i].len<<endl;
                    }
            }
            printf("%d\n",ma);
    }
}