#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int a[60][60],sumt[2510]={0},sum[2510]={0};
struct Peanut{
    int x,y,s;
};
struct sortf{
    bool operator()(const Peanut &a,const Peanut &b){
        return a.s>b.s;
    }
};

Peanut f[2510];
int main()
{
    int w;
    cin >> w;
    while(w--){
        memset(a,0,sizeof(a));
        int m,n,k,ii=0;
        cin >> m >> n >> k;
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                cin >> a[i][j];
                if(a[i][j]>0) {
                    ii++;
                    f[ii].s=a[i][j];
                    f[ii].x=i;
                    f[ii].y=j;
                }
            }
        }
        sort(f+1,f+1+ii,sortf());
        
        int x=0,y=f[1].y;
        int t=0;
        for(int i=1;i<=ii;i++){
            t=t+abs(x-f[i].x)+abs(y-f[i].y)+1;
            sumt[i]=t+f[i].x;
            sum[i]=sum[i-1]+f[i].s;
            x=f[i].x;y=f[i].y;
            if(k<sumt[i]){
                cout << sum[i-1];
                break;
            }
            if(i==ii&&k>=sumt[ii]) cout << sum[i];
        }
        cout << endl;
    }
    return 0;
}