1 #include<stdio.h>
 2 #include<string.h>
 3 #include<math.h>
 4 #include<iostream>
 5 #include<algorithm>
 6 #include<queue>
 7 #include<vector>
 8 #include<set>
 9 #include<stack>
10 #include<string>
11 #include<sstream>
12 #include<map>
13 #include<cctype>
14 #include<limits.h>
15 using namespace std;
16 int n,m,a[55][55],visited[55][55],b[2][2]={-1,0,0,-1},result,flag,mark;
17 struct node
18 {
19     int x,y,step;
20     friend bool operator<(node s1,node s2)
21     {
22         return s1.step<s2.step;
23     }
24 };
25 priority_queue<node>Q;
26 void BFS(int y,int x)
27 {
28     node q={x,y,a[y][x]};
29     visited[y][x]=1;
30     Q.push(q);
31     while(!Q.empty())
32     {
33         node e=Q.top();
34         Q.pop();
35         for(int i=0;i<2;i++)
36         {
37             q.x=e.x+b[i][0],q.y=e.y+b[i][1];
38             if(q.x>=0&&q.x<m&&q.y>=0&&q.y<n&&!visited[q.y][q.x])
39             {
40                 visited[q.y][q.x]=1;
41                 q.step=e.step+a[q.y][q.x];
42                 Q.push(q);
43                 if(q.x==0&&q.y==0)
44                 {
45                     result+=q.step;
46                     flag=1;
47                     break;
48                 }
49             }
50         }
51         if(flag)
52         {
53             while(!Q.empty())
54                 Q.pop();
55         }
56     }
57 }
58 void DFS(int y,int x,int step)
59 {
60     if(step==result||mark)
61     {
62         a[y][x]=1;
63         return;
64         mark=1;
65     }
66     DFS(y-1,x,step+a[y-1][x]);
67     if(step==result||mark)
68     {
69         a[y][x]=1;
70         return;
71         mark=1;
72     }
73     DFS(y,x-1,step+a[y][x-1]);
74     if(step==result||mark)
75     {
76         a[y][x]=1;
77         return;
78         mark=1;
79     }
80 }
81 int main()
82 {
83     int t;
84     scanf("%d",&t);
85     while(t--)
86     {
87         scanf("%d%d",&n,&m);
88         for(int i=0;i<n;i++)
89             for(int j=0;j<m;j++)
90             scanf("%d",&a[i][j]);
91         memset(visited,0,sizeof(visited));
92         mark=result=flag=0;
93         BFS(n-1,m-1);
94         DFS(n-1,m-1,0);
95         printf("%d
",result);
96     }
97     return 0;
98 }