#include <bits/stdc++.h>
using namespace std;
int findMinCost(int **grid,int row,int col,int** dp,int r=0, int c=0)
{
if(r >=row || c >=col)
return INT_MAX;
if(r == row-1 && c == col-1)
return 1;
if(dp[r][c] != -1)
return dp[r][c];
int right = findMinCost(grid,row,col,dp,r,c+1);
int down = findMinCost(grid,row,col,dp,r+1,c);
if(right != INT_MAX)
right -= grid[r][c+1];
if(down !=INT_MAX)
down -= grid[r+1][c];
if(right<1)
right = 1;
if(down<1)
down = 1;
int mincost= min(right,down);
// cout<<r<<" "<<c<<" "<<mincost<<endl;
dp[r][c]=mincost;
return dp[r][c];
}
int find(int **grid,int r,int c)
{
int **dp= new int*[r];
for(int i=0;i<r;i++)
dp[i]= new int[c];
for(int i=0;i<r;i++)
for(int j=0;j<c;j++)
dp[i][j]=-1;
int ans=findMinCost(grid,r,c,dp);
for(int i=0;i<r;i++)
delete [] dp[i];
delete [] dp;
return ans;
}
int main()
{
int t;
cin>>t;
while(t--)
{
int r,c;
cin>>r>>c;
int **grid= new int* [r];
for(int i=0;i<r;i++)
grid[i]= new int[c];
for(int i=0;i<r;i++)
for(int j=0;j<c;j++)
cin>> grid[i][j];
cout<<find(grid,r,c)<<endl;
for(int i=0;i<r;i++)
delete [] grid[i];
delete [] grid;
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgZmluZE1pbkNvc3QoaW50ICoqZ3JpZCxpbnQgcm93LGludCBjb2wsaW50KiogZHAsaW50IHI9MCwgaW50IGM9MCkKewogICAgIAogICAgCiAgICAgaWYociA+PXJvdyB8fCBjID49Y29sKQogICAgICAgICByZXR1cm4gSU5UX01BWDsKICAgIAogICAgIGlmKHIgPT0gcm93LTEgJiYgYyA9PSBjb2wtMSkKICAgICAgICByZXR1cm4gMTsKICAgCiAgICAgaWYoZHBbcl1bY10gIT0gLTEpCiAgICAgICAgcmV0dXJuIGRwW3JdW2NdOwogICAgCiAgICAKICAgICBpbnQgcmlnaHQgPSAgZmluZE1pbkNvc3QoZ3JpZCxyb3csY29sLGRwLHIsYysxKTsKICAgICBpbnQgZG93biAgPSAgZmluZE1pbkNvc3QoZ3JpZCxyb3csY29sLGRwLHIrMSxjKTsKIAogICAgCiAgICAgaWYocmlnaHQgIT0gSU5UX01BWCkKICAgICAgICAgcmlnaHQgLT0gZ3JpZFtyXVtjKzFdOwogICAgCiAgICAgIGlmKGRvd24gIT1JTlRfTUFYKQogICAgICAgICAgZG93biAtPSBncmlkW3IrMV1bY107CiAgICAKICAgIGlmKHJpZ2h0PDEpCiAgICAgICAgcmlnaHQgPSAxOyAgICAKICAgIGlmKGRvd248MSkKICAgICAgICBkb3duID0gMTsKICAgIAogICAgIGludCBtaW5jb3N0PSBtaW4ocmlnaHQsZG93bik7CiAgICAgLy8gIGNvdXQ8PHI8PCIgIjw8Yzw8IiAiPDxtaW5jb3N0PDxlbmRsOwogICAgCiAgICAgIAogICAgICAgICAgZHBbcl1bY109bWluY29zdDsKICAgICAKICAgICAgICByZXR1cm4gZHBbcl1bY107CiAgICAKfQppbnQgZmluZChpbnQgKipncmlkLGludCByLGludCBjKQp7CiAgICBpbnQgKipkcD0gbmV3IGludCpbcl07CiAgICAgICAgCiAgICAgIGZvcihpbnQgaT0wO2k8cjtpKyspCiAgICAgICAgICAgIGRwW2ldPSBuZXcgaW50W2NdOwogICAgCiAgICAgICBmb3IoaW50IGk9MDtpPHI7aSsrKQogICAgICAgICAgZm9yKGludCBqPTA7ajxjO2orKykKICAgICAgICAgICAgIGRwW2ldW2pdPS0xOwogICAgCiAgICBpbnQgYW5zPWZpbmRNaW5Db3N0KGdyaWQscixjLGRwKTsKIAogICAgZm9yKGludCBpPTA7aTxyO2krKykKICAgICAgICAgICBkZWxldGUgW10gZHBbaV07CiAgICAgICAgZGVsZXRlIFtdIGRwOwogICAgICAgIAogICByZXR1cm4gYW5zOwp9CgppbnQgbWFpbigpCnsKICAgIAogICAgaW50IHQ7CiAgICBjaW4+PnQ7CiAgICB3aGlsZSh0LS0pCiAgICB7CiAgICAgICBpbnQgcixjOwogICAgICAgIGNpbj4+cj4+YzsKICAgICAgICBpbnQgKipncmlkPSBuZXcgaW50KiBbcl07CiAgICAgICAgCiAgICAgICAgZm9yKGludCBpPTA7aTxyO2krKykKICAgICAgICAgICAgZ3JpZFtpXT0gbmV3IGludFtjXTsKICAgICAgICAKICAgICAgZm9yKGludCBpPTA7aTxyO2krKykKICAgICAgICAgIGZvcihpbnQgaj0wO2o8YztqKyspCiAgICAgICAgICAgICBjaW4+PiBncmlkW2ldW2pdOyAgICAgICAgICAgICAgICAKICAgICAgICAKICAgICAgICBjb3V0PDxmaW5kKGdyaWQscixjKTw8ZW5kbDsKICAgICAgICAKICAgICAgICBmb3IoaW50IGk9MDtpPHI7aSsrKQogICAgICAgICAgIGRlbGV0ZSBbXSBncmlkW2ldOwogICAgICAgIGRlbGV0ZSBbXSBncmlkOwogICAgICAgIAogICAgfQogICAgcmV0dXJuIDA7Cn0K