#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <algorithm>#include <queue>#define maxn 20+5using namespace std;int map[maxn][maxn],vis[maxn][maxn][maxn];int m,n,k,ans;int dx[]={0,0,1,-1};int dy[]={1,-1,0,0};struct Node{    int x,y;    int cnt;    int k;};int init(){    memset(map,0,sizeof(map));    memset(vis,0,sizeof(vis));    cin>>n>>m>>k;    for (int i=0;i<n;i++)        for (int j=0;j<m;j++)            cin>>map[i][j];}int bfs(){    queue<Node> q;    Node u;    u.x=0;u.y=0;u.cnt=0;u.k=k;    vis[0][0][k]=1;    q.push(u);    while (!q.empty()){        u=q.front();q.pop();        if (u.x==n-1&&u.y==m-1){            ans=u.cnt;            return 0;        }        Node v;        if (u.k>=0)//如果到该点没有命了， 那么就不需要在该点扩展了         for (int i=0;i<4;i++){            v.x=u.x+dx[i];            v.y=u.y+dy[i];            v.cnt=u.cnt+1;            if (map[v.x][v.y]) v.k=u.k-1;                    else v.k=k;//碰到0就恢复满命             if (v.x>=0&&v.x<n&&v.y>=0&&v.y<m&&!vis[v.x][v.y][v.k]){                if (v.k>=0) {q.push(v);vis[v.x][v.y][v.k]=1;}            }        }    }    if (q.empty()) ans=-1;}int main(){    int T;    cin>>T;    while (T--){        init();        bfs();        cout<<ans<<endl;    }}