#include<bits/stdc++.h>
using namespace std;
int a[51][51];
int dist[51][51];
int n;
bool check(int x,int y){
    return x>=0 && x < n && y>=0 && y < n;
}
void dijkstra(){
    priority_queue<pair<int,pair<int ,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>>pq;
    pq.push({a[0][0],{0,0}});
    dist[0][0]=a[0][0];
    while(!pq.empty()){
       auto temp = pq.top();
       pq.pop();
       int u = temp.second.first;
       int v = temp.second.second;
       if(check(u+1,v) && dist[u][v]+a[u+1][v]<dist[u+1][v])dist[u+1][v]=dist[u][v]+a[u+1][v],pq.push({dist[u+1][v],{u+1,v}});
       if(check(u,v+1) && dist[u][v]+a[u][v+1]<dist[u][v+1])dist[u][v+1]=dist[u][v]+a[u][v+1],pq.push({dist[u][v+1],{u,v+1}});
       if(check(u-1,v) && dist[u][v]+a[u-1][v]<dist[u-1][v])dist[u-1][v]=dist[u][v]+a[u-1][v],pq.push({dist[u-1][v],{u-1,v}});
       if(check(u,v-1) && dist[u][v]+a[u][v-1]<dist[u][v-1])dist[u][v-1]=dist[u][v]+a[u][v-1],pq.push({dist[u][v-1],{u,v-1}});

    }


}
int main(){
    int t;
    cin>>t;
    while(t--){
       // int n;
        cin>>n;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++)
                cin>>a[i][j];
        }
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
              dist[i][j]=INT_MAX;
        dijkstra();
        cout<<dist[n-1][n-1]<<endl;      
    }
    
}