#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
#include<map>
using namespace std;
const int MAXN=510;
typedef pair<int,int> PII;
typedef pair<int,PII> PIII;
//map<PII,int> mpp;
bool st[MAXN][MAXN];
int q,n,m;
long long mp[MAXN][MAXN];
int vis [MAXN][MAXN];
long long dist[MAXN][MAXN];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
long long mint=0x3f3f3f3f;
int disjkstra()
{
priority_queue<PIII,vector<PIII>, greater<PIII> > heap ;// 每次弹出最小的点,所以用小根堆
dist[1][1]=1e18,dist[n][m]=1e18;
for(int i=2;i<=n;i++)
{
if(mp[i][1]!=1e18)
{
PIII kk;
kk.first=mp[i][1],kk.second.first=i,kk.second.second=1;
heap.push(kk);
dist[i][1]=mp[i][1];
}
}
for(int i=1;i<m;i++)
{
if(mp[n][i]!=1e18)
{
PIII kk;
kk.first=mp[n][i],kk.second.first=n,kk.second.second=i;
heap.push(kk);
dist[n][i]=mp[n][i];
}
}
// 将左边和下边的符合条件的点放进堆里
while(!heap.empty())
{
PIII top=heap.top();
heap.pop();
long long distance = top.first;
PII var=top.second; int varx=var.first,vary=var.second;
if(varx==1||vary==m) //当碰到上面的和右边的点时,说明这个围墙已经搭建好,判断这时distance是否是最小
{
mint=min(mint,distance);
continue;//由于围墙已经搭建好了,所以对周围的点做松弛操作没有必要
}
if(st[varx][vary]) continue; //如果该点的最短距离已经被确认了,则无需再做松弛操作
else st[varx][vary]=true;
for(int i=0;i<4;i++) // 给四周的点做松弛操作
{
int xx=varx+dx[i],yy=vary+dy[i];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!st[xx][yy]) // 相比于前面的大佬稍微优化了一下,因为如果改点已经确定,则该点无需再入堆
{
if(distance+mp[xx][yy]<dist[xx][yy])//只有当改点减小了才会对周围的点做松弛操作,所以不符合条件的点不必要放入
{
dist[xx][yy] =distance+mp[xx][yy];
PIII kk;
kk.first=dist[xx][yy],kk.second.first=xx,kk.second.second=yy;
heap.push(kk);// 将符合条件的点放入堆中
}
}
}
}
if(mint==1e18) return -1;
else return mint;
}
void sc()
{
//memset(st,0,sizeof st);
mint=1e18;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>mp[i][j];
if(mp[i][j]==-1) mp[i][j]=0;
else if(mp[i][j]==0) mp[i][j]=1e18;
st[i][j]=false;
dist[i][j]=1e18;
}
cout<<disjkstra()<<endl;
}
int main()
{
cin>>q>>n>>m;
while(q--) sc();
}