#include<iostream> 
#include<math.h>
using namespace std;
int main()
{int i,j,k,m,l,w,t,e,f,p, s,d[100000],g;
cin>>g;
for(;g>0;g--)
{cin>>l>>w>>t;
int *a=new int [l*w];int *b=new int[l];int *c=new int [w];
for(i=0;i<l*w;i++)
{a[i]=0;}
for(i=0;i<l;i++)
{b[i]=0;}
for(i=0;i<w;i++)
{c[i]=0;}
for(i=0;i<l*w;i++)
{cin>>a[i];}
for(i=0,k=0;i<l*w;i++)
{if(a[i]>0){d[k]=a[i];b[k]=i/w+1;c[k]=i%w+1;k++;}
}
for(j=1;j<k;j++)
for(i=0;i<k-j;i++)
{if(d[i]<d[i+1])
{p=d[i];d[i]=d[i+1];d[i+1]=p;
e=b[i];b[i]=b[i+1];b[i+1]=e;
f=c[i];c[i]=c[i+1];c[i+1]=f;}
}
for(s=2+b[0]+c[0],i=1,m=d[0];i<k;i++)
{s=s+abs(b[i]-b[i-1])+abs(c[i]-c[i-1]);
if(s<=t)m=m+d[i];
}
cout<<m<<endl;
delete[]a;
delete[]b;
delete[]c;
}
return 0;
}