Untitled

package phoneList;

import java.io.FileInputStream;
import java.util.Scanner;

class Point{
	int x, y, z;
	
	public Point() {
		// TODO Auto-generated constructor stub
	}
	
	public Point(int x, int y, int z){
		this.x = x;
		this.y = y;
		this.z = z;
	}
}

class myQ{
	int front, rear;
	Point[] a = new Point[10000000];
	
	public myQ() {
		front = rear = -1;// TODO Auto-generated constructor stub
	}
	
	void init(){
		front = rear = -1;
	}
	
	void enQueue(Point x){
		a[++rear] = x;
	}
	
	Point deQueue(){
		return a[++front];
	}
	
	boolean isEmpty(){
		return front == rear;
	}
}

public class Solution {
	public static int[] rs = {-1,0,1,0,0,0};
	public static int[] cs = {0,-1,0,1,0,0};
	public static int[] hs = {0,0,0,0,1,-1};
	
	public static int N, T, ans, count;
	public static int[][][] a, visited;
	public static Point start, p;
	public static myQ queue = new myQ();

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		System.setIn(new FileInputStream("src\\phoneList\\input.txt"));

		Scanner sc = new Scanner(System.in);
		T = sc.nextInt();
		for (int tc = 1; tc <= T; tc++) {
			N = sc.nextInt();
			
			a = new int[N][N][N];
//			visited = new int[N][N][N];
			
			for (int k = 0; k < N; k++) {
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						a[i][j][k] = sc.nextInt();
						if(a[i][j][k] == 2){
							start = new Point(i,j,k);
						}
					}
				}
			}
			
			ans = 1000000;
			BFS(start);
			

			System.out.print("#" + tc + " ");
			System.out.println(ans);

		}
	}
	
	public static void BFS(Point start) {
		queue.init();
		visited = new int[N][N][N];
		queue.enQueue(start);
		visited[start.x][start.y][start.z] = 1;
		
		
		int cr, cc, ch;
		while(!queue.isEmpty()){
			p = queue.deQueue();
			if(p.x == 0 || p.y == 0 || p.y == N-1 || p.z == 0 || p.z == N-1){
				if(ans > visited[p.x][p.y][p.z] - 1){
					ans = visited[p.x][p.y][p.z] - 1;	
//					System.out.println(ans + "*");
//					for (int i = 0; i < N; i++) {
//						for (int j = 0; j < N; j++) {
//							for (int k = 0; k < N; k++) {
//								System.out.print(visited[i][j][k] + " ");
//							}
//							System.out.println();
//						}
//						System.out.println();
//					}
				}
				continue;
			}
			
			for (int i = 0; i < 6; i++) {
				cr = p.x + rs[i];
				cc = p.y + cs[i];
				ch = p.z + hs[i];
				
				if(cr>=0&&cr<N&&cc>=0&&cc<N&&ch>=0&&ch<N && (visited[cr][cc][ch] == 0 || visited[p.x][p.y][p.z] + a[cr][cc][ch] < visited[cr][cc][ch])){
					visited[cr][cc][ch] = visited[p.x][p.y][p.z] + a[cr][cc][ch];
					
					queue.enQueue(new Point(cr,cc,ch));
				}
			}
		}
	}
}