#include <fstream>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

ifstream fin("smax.in");
ofstream fout("smax.out");

int mat[501][501];
int dir[4][2]={{-1,0},{0,1},{0,-1},{1,0}};
int nr_lin, nr_col;

struct vc{
    int val, lin, col;
} v[250001];

queue <vc> q;

bool cmp(vc a, vc b)
{
    return a.val < b.val;
}

bool InBound(vc coord)
{
    return 0 <= coord.lin && coord.lin < nr_lin && 0 <= coord.col && coord.col < nr_col;
}

bool InSquare(vc coord1, vc coord2, vc coord, int d)
{
    int d1, d2;
    d1=abs(coord.lin-coord1.lin)+abs(coord.col-coord1.col);
    d2=abs(coord.lin-coord2.lin)+abs(coord.col-coord2.col);
    return d1 < d2 && d2 <= d;
}

void reinit(int n, int m)
{
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
            mat[i][j]=0;
    }
}

void QuickSort(int st, int dr)
{
	if(st<dr)
	{
		int m=(st+dr)/2;
		vc aux=v[st];
		v[st]=v[m];
		v[m]=aux;
		int i=st, j=dr, d=0;
		while(i<j)
		{
			if(v[i].val > v[j].val )
			{
				aux=v[i];
				v[i]=v[j];
				v[j]=aux;
				d=1-d;
			}
			i+=d;
			j-=1-d;
		}
		QuickSort(st, i-1);
		QuickSort(i+1, dr);
	}
}

int CautareMax(vc val, int dist)
{
    int maxi=-1;
    q.push(val);
    while(!q.empty())
    {
        vc curent=q.front(), vecin;
        q.pop();
        for(int i=0; i<4; i++)
        {
            vecin.lin=curent.lin+dir[i][0];
            vecin.col=curent.col+dir[i][1];
            vecin.val=mat[vecin.lin][vecin.col];
            if(InBound(vecin) && InSquare(curent, vecin, val, dist))
            {
                q.push(vecin);
                if(vecin.val>maxi)
                    maxi=vecin.val;
            }
        }
    }
    return maxi;
}

int main()
{
    int test, nr_teste, nr_elem, d_max, i, j, smax;
    fin>>nr_teste;
    for(test=1; test<=nr_teste; test++)
    {
        fin>>nr_lin>>nr_col>>d_max;
        nr_elem=nr_lin*nr_col;
        for(i=0; i<nr_lin; i++)
        {
            for(j=0; j<nr_col; j++)
            {
                int a;
                fin>>a;
                mat[i][j]=a;
                v[j+nr_col*i].val=a;
                v[j+nr_col*i].lin=i;
                v[j+nr_col*i].col=j;
            }
        }
        /// QuickSort(0, nr_elem-1);
        sort(v, v + nr_elem, cmp);
        smax=0;
        for(i=nr_elem-1; i>=0; i++)
        {
            int s;
            s=CautareMax(v[i], d_max)+v[i].val;
            if(s>smax)
               smax=s;
            if(v[i-1].val <= smax-v[i].val)
                break;
        }
        fout<<smax<<'\n';
    }
    return 0;
}