hdu1253

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

int a[55][55][55];
int T;
int n;
int A, B, C;
int vis[55][55][55];
int dist[6][3] = {0, 0, 1, 0, 0, -1, 1, 0, 0, -1, 0, 0, 0, 1, 0, 0, -1, 0};

struct node
{
	int x, y, z, step;
	// bool operator <(const node &q)const{
	// 	return step > q.step;
	// }
};

// void bfs(){
// 	memset(vis, 0, sizeof(vis));
// 	priority_queue<node> q;
// 	q.push(node{1, 1, 1, 0});
// 	vis[1][1][1] = 0;
// 	while(q.size()){
// 		node u = q.top();
// 		q.pop();
// 		if(u.x == A && u.y == B && u.z == C){
// 			if(u.step <= T){
// 				printf("%d\n", u.step);
// 			}else{
// 				printf("-1\n");
// 			}
// 			return ;
// 		}
// 		for (int i = 0; i < 6; i++){
// 			int x = u.x + dist[i][0], y = u.y + dist[i][1], z = u.z + dist[i][2];
			
// 			if(x < 1 || x > A || y < 1 || y > B || z < 1 || z > C || a[x][y][z] == 1) continue;
// 			if(!vis[x][y][z] || vis[x][y][z] > u.step + 1){
// 				vis[x][y][z] = u.step + 1;
// 				q.push(node{x, y, z, vis[x][y][z]});
// 			}
// 		}
// 	}
// 	printf("-1\n");
// }

// void bfs(){
// 	memset(vis, 0, sizeof(vis));
// 	priority_queue<node> q;
// 	q.push(node{1, 1, 1, 0});
// 	vis[1][1][1] = 1;
// 	while(q.size()){
// 		node u = q.top();
// 		q.pop();
// 		if(u.step > T){
// 			printf("-1\n");
// 			return ;
// 		}
// 		if(u.x == A && u.y == B && u.z == C){
// 			if(u.step <= T){
// 				printf("%d\n", u.step);
// 			}else{
// 				printf("-1\n");
// 			}
// 			return ;
// 		}
// 		for (int i = 0; i < 6; i++){
// 			int x = u.x + dist[i][0], y = u.y + dist[i][1], z = u.z + dist[i][2];
			
// 			if(x < 1 || x > A || y < 1 || y > B || z < 1 || z > C || a[x][y][z] == 1) continue;
// 			if(!vis[x][y][z]){
// 				vis[x][y][z] = 1;
// 				q.push(node{x, y, z, u.step + 1});
// 			}
// 		}
// 	}
// 	printf("-1\n");
// }

void bfs(){
	memset(vis, 0, sizeof(vis));
	queue<node> q;
	q.push(node{1, 1, 1, 0});
	vis[1][1][1] = 1;
	while(q.size()){
		node u = q.front();
		q.pop();
		if(u.x == A && u.y == B && u.z == C){
			if(u.step <= T){
					printf("%d\n", u.step);
			}else{
				printf("-1\n");
			}
			return ;
		}
		for (int i = 0; i < 6; i++){
			int x = u.x + dist[i][0], y = u.y + dist[i][1], z = u.z + dist[i][2];
			if(x < 1 || x > A || y < 1 || y > B || z < 1 || z > C || a[x][y][z] == 1) continue;
			if(!vis[x][y][z]){
				vis[x][y][z] = 1;
				q.push(node{x, y, z, u.step + 1});
			}
		}
	}
	printf("-1\n");
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%d", &n);
	while(n--){
		scanf("%d %d %d %d", &A, &B, &C, &T);
		for (int i = 1; i <= A; i++){
			for (int j = 1; j <= B; j++){
				for (int k = 1; k <= C; k++){
					scanf("%d", &a[i][j][k]);
				}
			}
		}
		bfs();
	}

	return 0;
}
/**/

想打人，优先队列过不了也是服气。