#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
int map[52][52],temp[3000][3];
void swap(int num[][3],int i,int j)
{
	int t;
	t=num[i][0];num[i][0]=num[j][0];
	num[j][0]=t;
	t=num[i][1];num[i][1]=num[j][1];
	num[j][1]=t;
	t=num[i][2];num[i][2]=num[j][2];
	num[j][2]=t;	
}
void quicksort(int num[][3],int left,int right)
{
	int j,last;
	if(left>=right)
	return;
	swap(num,left,(left+right)/2);
	last=left;
	for(j=left+1;j<=right;j++)
	{
		if(num[j][0]>num[left][0])
		swap(num,++last,j);
	}
	swap(num,left,last);
	quicksort(num,left,last-1);
	quicksort(num,last+1,right);
}
int main()
{
	int i,j,k,t;
	scanf("%d",&k);
	while(k--)
	{
		int m,n,time;
		scanf("%d%d%d",&m,&n,&time);
		t=0;
		for(i=1;i<=m;i++)
		{
			for(j=1;j<=n;j++)
			{
				scanf("%d",&map[i][j]);	
				if(map[i][j]>0)
				{
					temp[t][0]=map[i][j];
					temp[t][1]=i;
					temp[t][2]=j;
					t++;	
				}
			}	
		}
		quicksort(temp,0,t);
		int a,b;
		int total[3000];
		long long max;
		total[0]=temp[0][1]+1;
		if(total[0]*2-1<=time)
		{
			a=temp[0][2];
			b=temp[0][1];
			max=temp[0][0];
		}
		else
		{
			printf("0\n");
			continue;	
		}
		for(i=1;i<t;i++)
		{	
			if(a>=temp[i][2])
				total[i]=total[i-1]+a-temp[i][2]+1;
			else
				total[i]=total[i-1]+temp[i][2]-a+1;
			if(b>=temp[i][1])
				total[i]=total[i]+b-temp[i][1];
			else
				total[i]=total[i]+temp[i][1]-b;
			a=temp[i][2];
			b=temp[i][1];
			max=temp[i][0]+max;
			if(total[i]>=time)
			break;
		}
		if(total[i]+temp[i][1]>time)	
		while(1)
		{
			max=max-temp[i][0];
			i--;
			if(total[i]+temp[i][1]<=time)
			break;
			
		}
		printf("%lld\n",max);
		//system("pause");
	}
}