#include <stdio.h>
#include <math.h>
struct node
{
	int data,row,line;
};

int main()
{
	int nums,m,n,k;
	scanf("%d",&nums);
	for(int z=0;z!=nums;z++){
		scanf("%d%d%d",&m,&n,&k);
		node** a=new node*[m];
		for(int i=0;i!=m;i++){
			a[i]=new node[n];
		}
		for(int i=0;i!=m;i++)
			for(int j=0;j!=n;j++){
				scanf("%d",&a[i][j].data);
				a[i][j].row=i+1;
				a[i][j].line=j+1;
			}
		node t;
		for(int p=0;p!=m;p++){                                 //将结点从大到小排序
			for(int q=0;q!=n;q++){
				for(int i=p;i!=m;i++){
					int j;
					for((i==p?j=q:j=0);j!=n;j++){
						if(a[p][q].data<a[i][j].data){
							t=a[p][q];
							a[p][q]=a[i][j];
							a[i][j]=t;
						}  
					}
				}
			}
		}

		int sum=0,time=0,currow=a[0][0].row,curline=a[0][0].line;
		if(2*a[0][0].row+1<=k) 
		{
			time+=a[0][0].row+1;
			sum+=a[0][0].data;
		}
		for(int i=0;i!=m;i++){
			int j;
			for((i==0?j=1:j=0);j!=n;j++){
				int cha=abs(a[i][j].row-currow)+abs(a[i][j].line-curline)+1;
				if(cha+a[i][j].row+time<=k){
					time+=cha;
					sum+=a[i][j].data;
					currow=a[i][j].row;
					curline=a[i][j].line;
					if(i==m-1&&j==n-1) 
						printf("%d\n",sum);
				}
				else 
				{
					printf("%d\n",sum);
					i=m-1;
					j=n-1;
				}
			}
		}
	}
	

	return 0; 
}