De men phieu luu ky

#define DEBUG freopen("input.txt", "r", stdin)

#ifdef DEBUG
#include <time.h>
#endif

#include <iostream>
#include <stdio.h>
using namespace std;

#define f(i, a, b, d) for (int i = a; i < b; i += d)
#define fr(i, a, b, d) for (int i = a; i <= b; i += d)
#define rf(i, a, b, d) for (int i = a; i >= b; i -= d)

template <typename T = int, int N = 999999>
class Queue {
private:
	T arr[N];
	int front, tail;

public:
	Queue() {
		clear();
	}

	void clear() {
		front = tail = -1;
	}

	bool isEmpty() {
		return front == -1;
	}

	bool isFull() {
		return (tail + 1) % N == front;
	}

	void push(T x) {
		if (isFull()) {
			cerr << "[ERROR] Queue is full" << endl;
			return;
		}
		if (front == -1) {
			front = 0;
		}
		tail = (tail + 1) % N;
		arr[tail] = x;
	}

	T pop() {
		// todo: check if empty
		T x = arr[front];
		if (front == tail) {
			clear();
		} else {
			front = (front + 1) % N;
		}
		return x;
	}

	T peek() {
		return arr[front];
	}
};

#define mapP(a, point) a[point.x][point.z][point.y]
struct Point {
	int x, y, z;

	void assign(int x, int z, int y) {
		this->x = x;
		this->y = y;
		this->z = z;
	}
};

const Point dir[] = {
	{ 0, 0, 1 },
	{ 0, 0, -1 },
	{ 0, 1, 0 },
	{ 0, -1, 0 },
	{ 1, 0, 0 },
	{ -1, 0, 0 }
};
const int nDir = sizeof(dir) / sizeof(*dir);

const int oo = 2 * 999999999;
const int N = 32;
int tnum, ans;
int n;
int a[N][N][N];
int step[N][N][N];
Point start;

void input() {
	cin >> n;
	f(x, 0, n, 1) {
		f(z, 0, n, 1) {
			f(y, 0, n, 1) {
				cin >> a[x][z][y];
				if (a[x][z][y] == 2) {
					start.assign(x, z, y);
				}
			}
		}
	}

	// add walls
	f(x, 0, n, 1) {
		f(y, 0, n, 1) {
			a[x][n][y] = 7;
		}
	}
}

bool inBound(Point p) {
	// z == n is the wall
	return p.x >= 0 && p.x < n && p.y >= 0 && p.y < n && p.z >= 0 && p.z <= n;
}

void bfs() {
	static Queue<Point> q;
	Point cur, next;
	f(x, 0, n, 1) {
		f(z, 0, n, 1) {
			f(y, 0, n, 1) {
				step[x][z][y] = oo;
			}
		}
	}

	q.clear();
	q.push(start);
	mapP(step, start) = 0;
	while (!q.isEmpty()) {
		cur = q.pop();
		f(i, 0, nDir, 1) {
			next = cur;
			next.x += dir[i].x;
			next.z += dir[i].z;
			next.y += dir[i].y;

			if (!inBound(next)) {
				ans = min(ans, mapP(step, cur));
				continue;
			}

			if (mapP(a, next) < 2 
				&& mapP(step, next) > (mapP(step, cur) + mapP(a, next))
			) {
				mapP(step, next) = mapP(step, cur) + mapP(a, next);
				q.push(next);
			}
		}
	}
}

void solve() {
	input();
	ans = oo;
	bfs();
	printf("#%d %d\n", tnum, ans);
}

int main() {

#ifdef DEBUG
	fprintf(stderr, "Running on Debug mode\n");
	clock_t start = clock();
	DEBUG;
#endif

	int t;
	cin >> t;
	for (tnum = 1; tnum <= t; tnum++) {
		solve();
	}

#ifdef DEBUG
	double duration = double(clock() - start) / CLOCKS_PER_SEC;
	fprintf(stderr, "Finished in %.6lf seconds\n", duration);
#endif

	return 0;
}