#include<iostream>
using namespace std;
int arr[10][10];
int visited[10][10];
int min_cost;
int n;
bool isSafe(int x,int y){
if(x>=0 && y>=0 && x<n && y<n && arr[x][y]!=0 ){return true;}
else{return false;}
}
bool AllVisited(){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(visited[i][j]!=1){return false;}
}
}
return true;
}
void dfs(int x,int y,int cost){
if(x==n-1 && y==n-1){
if(cost<min_cost){min_cost=cost;}
std::cout<<"one loop got completed ------- giving cost :"<<cost<<" min cost :"<<min_cost<<std::endl;
bool k = AllVisited();
if(k==true){std::cout<<"found the elemeents !! yay "<<std::endl; return;}
//if(k==false){return;}
}
if(isSafe(x,y)==true){
if(arr[x+1][y]!=0 && visited[x+1][y]==0){visited[x+1][y]=1; cost=cost+arr[x+1][y]; std::cout<<"sending xy:"<<x+1<<" "<<y<<" cost :"<<cost<<std::endl; dfs(x+1,y,cost); cost=cost-(arr[x+1][y]); visited[x+1][y]=0; std::cout<<"backtracking xy:"<<x+1<<y<<" cost :"<<cost<<std::endl;}
if(arr[x][y+1]!=0 && visited[x][y+1]==0){visited[x][y+1]=1; cost=cost+arr[x][y+1]; std::cout<<"sending xy:"<<x<<" "<<y+1<<" cost :"<<cost<<std::endl; dfs(x,y+1,cost); cost=cost-(arr[x][y+1]); visited[x][y+1]=0; std::cout<<"backtracking xy:"<<x<<y+1<<" cost :"<<cost<<std::endl;}
if(arr[x-1][y]!=0 && visited[x-1][y]==0){visited[x-1][y]=1; cost=cost+arr[x-1][y]; std::cout<<"sending xy:"<<x-1<<" "<<y<<" cost :"<<cost<<std::endl; dfs(x-1,y,cost); cost=cost-(arr[x-1][y]); visited[x-1][y]=0; std::cout<<"backtracking xy:"<<x-1<<y<<" cost :"<<cost<<std::endl;}
if(arr[x][y-1]!=0 && visited[x][y-1]==0){visited[x][y-1]=1; cost=cost+arr[x][y-1]; std::cout<<"sending xy:"<<x<<" "<<y-1<<" cost :"<<cost<<std::endl; dfs(x,y-1,cost); cost=cost-(arr[x][y-1]); visited[x][y-1]=0; std::cout<<"backtracking xy:"<<x<<y-1<<" cost :"<<cost<<std::endl;}
}
return ;
}
int main(){
int t;
std::cin>>t;
for(int tc=0;tc<t;tc++){
std::cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
std::cin>>arr[i][j];
visited[i][j]=0;
}
}
min_cost=999;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(arr[i][j]!=0 && visited[i][j]==0){
visited[i][j]=1;
dfs(0,0,);
}
}
}
std::cout<<"min_cost"<<min_cost<<std::endl;
}
return 0;}
using namespace std;
int arr[10][10];
int visited[10][10];
int min_cost;
int n;
bool isSafe(int x,int y){
if(x>=0 && y>=0 && x<n && y<n && arr[x][y]!=0 ){return true;}
else{return false;}
}
bool AllVisited(){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(visited[i][j]!=1){return false;}
}
}
return true;
}
void dfs(int x,int y,int cost){
if(x==n-1 && y==n-1){
if(cost<min_cost){min_cost=cost;}
std::cout<<"one loop got completed ------- giving cost :"<<cost<<" min cost :"<<min_cost<<std::endl;
bool k = AllVisited();
if(k==true){std::cout<<"found the elemeents !! yay "<<std::endl; return;}
//if(k==false){return;}
}
if(isSafe(x,y)==true){
if(arr[x+1][y]!=0 && visited[x+1][y]==0){visited[x+1][y]=1; cost=cost+arr[x+1][y]; std::cout<<"sending xy:"<<x+1<<" "<<y<<" cost :"<<cost<<std::endl; dfs(x+1,y,cost); cost=cost-(arr[x+1][y]); visited[x+1][y]=0; std::cout<<"backtracking xy:"<<x+1<<y<<" cost :"<<cost<<std::endl;}
if(arr[x][y+1]!=0 && visited[x][y+1]==0){visited[x][y+1]=1; cost=cost+arr[x][y+1]; std::cout<<"sending xy:"<<x<<" "<<y+1<<" cost :"<<cost<<std::endl; dfs(x,y+1,cost); cost=cost-(arr[x][y+1]); visited[x][y+1]=0; std::cout<<"backtracking xy:"<<x<<y+1<<" cost :"<<cost<<std::endl;}
if(arr[x-1][y]!=0 && visited[x-1][y]==0){visited[x-1][y]=1; cost=cost+arr[x-1][y]; std::cout<<"sending xy:"<<x-1<<" "<<y<<" cost :"<<cost<<std::endl; dfs(x-1,y,cost); cost=cost-(arr[x-1][y]); visited[x-1][y]=0; std::cout<<"backtracking xy:"<<x-1<<y<<" cost :"<<cost<<std::endl;}
if(arr[x][y-1]!=0 && visited[x][y-1]==0){visited[x][y-1]=1; cost=cost+arr[x][y-1]; std::cout<<"sending xy:"<<x<<" "<<y-1<<" cost :"<<cost<<std::endl; dfs(x,y-1,cost); cost=cost-(arr[x][y-1]); visited[x][y-1]=0; std::cout<<"backtracking xy:"<<x<<y-1<<" cost :"<<cost<<std::endl;}
}
return ;
}
int main(){
int t;
std::cin>>t;
for(int tc=0;tc<t;tc++){
std::cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
std::cin>>arr[i][j];
visited[i][j]=0;
}
}
min_cost=999;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(arr[i][j]!=0 && visited[i][j]==0){
visited[i][j]=1;
dfs(0,0,);
}
}
}
std::cout<<"min_cost"<<min_cost<<std::endl;
}
return 0;}