#include<bits/stdc++.h>
using namespace std;
// iNautix
// #Placement
// 0 path, 1 diamond, -1 block
// possible movements right, down
// reverse up, left
int maxD(vector< vector <int> > a);
bool valid(vector< vector<int> > a, int x, int y);
bool btFWD(vector < vector<int> > a, int x, int y);
int solveFWD(vector< vector<int> > &a, int r,int c,int x,int y, int di);
bool btREV(vector < vector<int> > a, int x, int y);
int solveREV(vector< vector<int> > &a, int r,int c,int x,int y, int di);
int main(){
int t;
cin>>t;
while(t--){
int r,c;
cin>>r>>c;
vector< vector<int> > a(r);
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
int x;
cin>>x;
a[i].push_back(x);
}
}
cout<<maxD(a)<<endl;
}
return 0;
}
int maxD(vector< vector <int> > a){
int r=a.size();
int c=a[0].size();
int fwd=solveFWD(a,r,c,0,0,0);
int ans=solveREV(a,r,c,r-1,c-1,fwd);
return ans;
}
bool valid(vector< vector<int> > a, int x, int y){
int r=a.size();
int c=a[0].size();
if(x<0 || y<0 || x>=r || y>=c){
return false;
}
if(a[x][y]==-1){
return false;
}
return true;
}
bool btFWD(vector < vector<int> > a, int x, int y){
int r=a.size();
int c=a[0].size();
if(x==r-1 && y==c-1){
return true;
}
if(valid(a,x,y)==true){
if(btFWD(a,x,y+1)==true){
return true;
}
if(btFWD(a,x+1,y)==true){
return true;
}
return false;
}
return false;
}
int solveFWD(vector< vector<int> > &a, int r,int c,int x,int y, int di){
if(x==r-1 && y==c-1){
di+=a[x][y];
a[x][y]=0;
return di;
}
if(btFWD(a,x,y)==true){
di+=a[x][y];
a[x][y]=0;
vector< vector<int> > aCPY=a;
int right=solveFWD(a,r,c,x,y+1,di);
int down=solveFWD(aCPY,r,c,x+1,y,di);
if(right<down){
a=aCPY; // IMP step
return down; // make a copy of array to backtrack
}else{
return right;
}
}else{
return -1; // No Path
}
}
bool btREV(vector < vector<int> > a, int x, int y){
if(x==0 && y==0){
return true;
}
if(valid(a,x,y)==true){
if(btREV(a,x,y-1)==true){
return true;
}
if(btREV(a,x-1,y)==true){
return true;
}
return false;
}
return false;
}
int solveREV(vector< vector<int> > &a, int r,int c,int x,int y, int di){
if(x==0 && y==0){
di+=a[x][y];
a[x][y]=0;
return di;
}
if(btREV(a,x,y)==true){
di+=a[x][y];
a[x][y]=0;
vector< vector<int> > aCPY=a;
int left=solveREV(a,r,c,x,y-1,di);
int up=solveREV(aCPY,r,c,x-1,y,di);
if(left<up){
a=aCPY;
return up;
}else{
return left;
}
}else{
return -1; // No Path
}
}