#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
//学习博友翻译
int da[100][100];//我写小了有溢出 一直wa
int tim[10000];
int hs[10000];
struct nod{
int nut;
int x;
int y;
};
bool cmp(nod a, nod b)
{
return a.nut>b.nut;
}
int main()
{
int T;
cin>>T;
for(int o=0;o<T;o++)
{
memset(da,0,sizeof(da));
memset(tim,0,sizeof(tim));
memset(hs,0,sizeof(hs));
int n,m,lim;
cin>>n>>m>>lim;
vector<nod> ve;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>da[i][j];
if(da[i][j]!=0)
{
nod t;
t.nut=da[i][j];
t.x=j;
t.y=i;
ve.push_back(t);
}
}
}
sort(ve.begin(),ve.end(),cmp);//以上ac
/*
int sum=0;
lim-=ve[0].y;
for(int i=0;i<ve.size();++i)
{
if(lim>=ve[i].y+1)
{
sum+=ve[i].nut;
lim-=abs(ve[i].x-ve[i+1].x)+abs(ve[i].y-ve[i+1].y)+1;
}
else
break;
}
printf("%d\n",sum);*/
/*
if(ve.size()==0)
{
cout<<0<<endl;
continue;
}*/
int sum=0;//不算出去花的时间
int tx=ve[0].x;
int ty=0;
int pn=0;//摘到的花生
for(int i=0;i<ve.size();i++)
{
//cout<<i<<" "<<ve[i].nut<<" "<<ve[i].x<<" "<<ve[i].y<<endl;
int ax=ve[i].x;
int ay=ve[i].y;
sum=sum+abs(tx-ax)+abs(ty-ay)+1;
pn=pn+ve[i].nut;
hs[i]=pn;
tx=ax;
ty=ay;
tim[i]=sum+ay;
//cout<<sum<<" "<<time[i]<<endl<<endl;
}
/*
for(int i=0;i<ve.size();i++)
{
cout<<ve[i].nut<<" "<<ve[i].x<<" "<<ve[i].y<<" ";
}
cout<<endl;
for(int i=0;i<ve.size();i++)
{
cout<<tim[i]<<" ";
}
cout<<endl;
for(int i=0;i<ve.size();i++)
{
cout<<hs[i]<<" ";
}
cout<<endl;*/
int jg=0;//一下ac
for(int i=0;i<ve.size();i++)
{
if(tim[i]>lim)
{
break;
}else
{
jg=hs[i];
}
}
cout<<jg<<endl;
}
return 0;
}
