#include <iostream>
#include <math.h>
#include <stdlib.h>

struct Point{
	int x,y;
	int v;
};

const int _MAXN=55;

using namespace std;

int top;
Point pt[_MAXN*_MAXN];
int n,m,c;

int cmp(const void *a,const void *b){
	Point A=*((Point *)a);
	Point B=*((Point *)b);
	return B.v-A.v;
}

int work(){
	int ans=0;
	int t=2+(pt[0].x-1)*2+1;
	Point pPre=pt[0];
	if(t>c){
		return 0;
	}
	int pre=t-pt[0].x;
	ans+=pPre.v;
	for(int i=1;i<top;i++){
		Point p=pt[i];
		t=pre+abs(p.x-pPre.x)+abs(p.y-pPre.y)+p.x+1;
		if(t<=c){
			pPre=p;
			pre=t-p.x;
			ans+=p.v;
		}else{
			break;
		}
	}
	return ans;
}

int main(){
	int N;
	cin>>N;
	while(N--){
		top=0;
		cin>>n>>m>>c;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				int temp;
				cin>>temp;
				if(temp!=0){
					pt[top].x=i;
					pt[top].y=j;
					pt[top++].v=temp;
				}
			}
		}
		qsort(pt,top,sizeof(Point),cmp);
		cout<<work()<<endl;
	}
	return 0;
}