#include <iostream> using namespace std; int n; bool f[501]; int w[501][501]; int lowcost[501]; int prim(){ int i,j; int max=-1; memset(f,0,sizeof(f)); memset(lowcost,0,sizeof(lowcost)); for(i=1;i<=n;i++){ lowcost[i]=w[1][i]; } f[1]=1; for(i=1;i<n;i++){ int v; int min=100*100*127; for(j=1;j<=n;j++){ if(!f[j]&&lowcost[j]<min){ min=lowcost[j]; v=j; } } if(min>max)max=min; f[v]=1; for(j=1;j<=n;j++){ if(!f[j]&&w[v][j]<lowcost[j]) lowcost[j]=w[v][j]; } } return max; } int main(){ int t; cin>>t; while(t--){ cin>>n; int i,j; for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ cin>>w[i][j]; } } cout<<prim()<<endl; } return 0; }