#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<climits>
using namespace std;
typedef long long ll;
int main(){

	int t;cin>>t;
	while(t--){
	    priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, greater<pair<int,pair<int,int>>> > q;
	    int n;cin>>n;
	    vector<vector<int>> m(n, vector<int>(n)), leastdist(n, vector<int>(n,INT_MAX));
	    for(int i=0;i<n;++i)
	        for(int j=0;j<n;++j)
	            cin>>m[i][j];

	    q.push({m[0][0],{0,0}});
	    leastdist[0][0] = m[0][0];
	    int dx[] = {1,0,0,-1};
	    int dy[] = {0,1,-1,0};
	    while(!q.empty()){
	        pair<int,pair<int,int>> cur = q.top();
	        q.pop();
	        int x = cur.second.first, y = cur.second.second, val = cur.first;

	        if(cur.second.second==n-1 && cur.second.first==n-1){
	            cout<<cur.first<<endl;
	            break;
	        }
	        if(val!=leastdist[x][y]){
	            continue;
	        }
	        for(int i=0;i<4;++i){
	            int nx = x+dx[i], ny = y+dy[i];
	            if(nx<n && ny<n && nx>=0 && ny>=0 && m[nx][ny]+val<leastdist[nx][ny]){
	                q.push({m[nx][ny]+val,{nx,ny}});
	                leastdist[nx][ny] = m[nx][ny]+val;
	            }
	        }
	    }
	}
	return 0;
}