1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int k[30][30], vis[30][30][30], pre[1500];
int turn[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int m, n;

struct POINT
{
    int x, y, z;
}que[1500];

int cnt, heart;
bool flag;

void cntpls( int a ){
    int t = pre[a];
    if( t != 0 )
        cntpls(t);
    cnt++;
}

void Print( int n )
{
    cntpls(n);
    printf("%dn",cnt);
}

bool go( int x, int y, int p )
{
    if( x >= 0 && x < m && y >= 0 && y < n )
        return true;
    return false;
}

void BFS()
{
    cnt = 0;
    flag = false;
    memset(vis, 0, sizeof(vis));
    int head = 0, tile = 1, a, b, xx, yy, zz;
    que[0].x = 0, que[0].y = 0, que[0].z = 0;
    pre[0] = -1;
    while( head < tile ){
        a = que[head].x;
        b = que[head].y;
        if( a == m-1 && b == n-1 ){
            Print(head);
            flag = true;
            return;
        }
        for( int i = 0; i < 4; i++ ){
            xx = a + turn[i][0];
            yy = b + turn[i][1];
            zz = que[head].z;
            if( k[xx][yy] )
                zz++;
            else
                zz = 0;
            if( zz <= heart && !vis[xx][yy][zz] && go(xx, yy, zz) ){
                vis[xx][yy][zz] = 1;
                que[tile].x = xx;
                que[tile].y = yy;
                que[tile].z = zz;
                pre[tile] = head;
                tile++;
            }
        }
        head++;
    }
    return;
}



int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&m,&n,&heart);
        for( int i = 0; i < m; i++ )
            for( int j = 0; j < n; j++ )
                scanf("%d",&k[i][j]);
        if( m == 1 && n == 1 ){
            printf("0n");
            continue;
        }
        else
            BFS();
        if(!flag)
            printf("-1n");
    }
    return 0;
}