// Arup Guha
// 3/13/2018, finished 3/14/2018
// Solution to 2018 UCF HS Contest Problem: Heavy Lifting
// Runs in 4.6 seconds on my desktop.

import java.util.*;

public class heavy {

	// Directions of movement.
	final public static int[] DX = {-1,-1,-1,0,0,1,1,1};
	final public static int[] DY = {-1,0,1,-1,1,-1,0,1};
	final public static int N = 8;
	final public static int MAXH = 100;
	final public static int BITS = 6;
	final public static int MAXPLATFORM = 10;

	// lowMap[i][j] is a list of each path (its mask) at index i of cost j.
	public static ArrayList[][] lowMap;

	// highMap[i][j] is a list of each path (its mask) at index i of cost j.
	public static ArrayList[][] highMap;

	// Grid info.
	public static int[][] grid;
	public static int height;

	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);
		int nC = stdin.nextInt();

		// Process each case.
		for (int loop=1; loop<=nC; loop++) {

			// Here is where we have to get. Mid is for readability.
			height = stdin.nextInt();

			// Get the grid.
			grid = new int[N][N];
			for (int i=0; i<N; i++)
				for (int j=0; j<N; j++)
					grid[i][j] = stdin.nextInt();

			// Get these set up.
			lowMap = new ArrayList[N*N][MAXH*(MAXPLATFORM/2+2)];
			highMap = new ArrayList[N*N][MAXH*(MAXPLATFORM/2+2)];
			for (int i=0; i<lowMap.length; i++) {
				for (int j=0; j<lowMap[i].length; j++) {
					lowMap[i][j]  = new ArrayList<Long>();
					highMap[i][j] = new ArrayList<Long>();
				}
			}

			// Try each starting spot.
			for (int i=0; i<N; i++) {
				for (int j=0; j<N; j++) {

					// Start from both top and bottom moving in the appropriate direction.
					go(0L, i, j, 0, 0, 1, height/2);
					go(0L, i, j, height, 0, -1, height/2);
				}
			}

			// Solve it.
			System.out.println("Crypt #"+loop+": "+solve());
		}
	}

	public static int solve() {

		// Can't be worse than this.
		int res = N*N*MAXH;

		// i is our meet in the middle spot.
		for (int i=0; i<N*N; i++) {

			// Give these names.
			ArrayList[] myLowMap = lowMap[i];
			ArrayList[] myHighMap = highMap[i];

			// Find each solution in myLowMap.
			for (int j=0; j<myLowMap.length; j++) {

				// Won't find a better solution.
				if (j > res) break;

				// Try each low mask here.
				for (Long x : (ArrayList<Long>)myLowMap[j]) {

					// Now go through matching list.
					for (int k=0; k<myHighMap.length; k++) {

						// Won't find a better solution.
						if (j+k > res) break;

						// Try each high mask here.
						for (Long y: (ArrayList<Long>)myHighMap[k]) {

							// Nothing intersects, so this is valid. Cost is just sum based
							// on how we stored data for the masks.
							if ((x & y) == 0) res = Math.min(res, j+k);
						}
					}
				}
			}
		} // end i

		// Ta da!
		return res;
	}

	public static long convert(long mask, int slots) {

		long res = 0L;

		// Peel off each item.
		for (int i=0; i<slots; i++) {
			int spot = (int)(mask & ((1L<<BITS)-1));
			res |= (1L<<spot);
			mask >>= BITS;
		}
		return res;
	}

	// Passing in a lot of redundant stuff to make this easier to code...
	public static void go(long used, int x, int y, int curH, int cost, int delta, int targetH) {

		// Can't build off this.
		if (grid[x][y] < curH) return;

		// location in one dimension.
		int spot = N*x + y;

		// Got where we want to be.
		if (curH == targetH) {

			// Put in appropriate map - only add middle block cost to lower path not upper path.
			if (delta == 1) ((ArrayList<Long>)lowMap[N*x+y][cost+grid[x][y]-curH]).add(used);
			else 			((ArrayList<Long>)highMap[N*x+y][cost]).add(used);

			return;
		}

		// Go in each direction.
		for (int dir=0; dir<DX.length; dir++) {

			int nX = x + DX[dir];
			int nY = y + DY[dir];

			int nSpot = N*nX + nY;

			// Off the board.
			if (!inbounds(nX, nY)) continue;

			// Been here before.
			if ((used & (1L<<nSpot)) != 0) continue;

			// Recurse to this spot.
			go( used | (1L<<spot), nX, nY, curH+delta, cost+grid[x][y]-curH, delta, targetH);
		}
	}

	public static boolean inbounds(int x, int y) {
		return x >= 0 && x < N && y >= 0 && y < N;
	}
}