#include<bits/stdc++.h>
using namespace std;
const long long M=1e7+1,MOD=1000000007;
typedef long long ll;
#define double long double
#define debug(x) cout<<x<<endl
int a[800][800];
void clr(int n){
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)a[i][j]=1e5;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
       int n;
       cin>>n;
      vector<int>st;
       for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int b;
            cin>>b;
            st.push_back(b);
       }
   }
   sort(st.begin(),st.end());
       int l=-2e4,r=2e4;
       int res=-1e5;
       while(l<=r){
        int mid=l+(r-l)/2;
        int ok=1;
        multiset<int>st1;
        for(auto it:st)st1.insert(it);
        clr(n);
        for(int i=1;i<=n&&ok;i++){
            for(int j=1;j<=n&&ok;j++){
                if(i==1 && j==1){
                    auto it=st1.begin();
                    a[i][j]=*it;
                    st1.erase(st1.find(a[i][j]));
                }
                else{
                    int x=min(a[i-1][j],a[i][j-1]);
                    int lagba=mid-x;
                    auto it=st1.lower_bound(lagba);
                    if(it==st1.end()){
                        ok=0;
                        break;
                    }
                    a[i][j]=*it;
                    st1.erase(st1.find(a[i][j]));
                }
                
            }
        }
        int ok1=1;
        clr(n);
        st1.clear();
        for(auto it:st)st1.insert(it);
         for(int i=1;i<=n&&ok1;i++){
            for(int j=1;j<=n&&ok1;j++){
                if(i==1 && j==1){
                    auto it=st1.rbegin();
                    a[i][j]=*it;
                    st1.erase(st1.find(a[i][j]));
                }
                else{
                    int x=min(a[i-1][j],a[i][j-1]);
                    int lagba=mid-x;
                    auto it=st1.lower_bound(lagba);
                    if(it==st1.end()){
                        ok1=0;
                        break;
                    }
                    a[i][j]=*it;
                    st1.erase(st1.find(a[i][j]));
                }
                
            }
        }
        if(ok || ok1){
            res=mid;
            l=mid+1;
        }
        else r=mid-1;

       }
       cout<<res<<"\n";
    }


    return 0;
 
}