SWAcademy 1249

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class Solution {
	static int N;
	static int[][] map;
	static int[][] cost;
	static int[] dy = { -1, 1, 0, 0 }, dx = { 0, 0, -1, 1 };
	static PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> a.d - b.d);

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			N = Integer.parseInt(br.readLine());
			map = new int[N][N];
			cost = new int[N][N];
			for (int i = 0; i < N; i++) {
				String str = br.readLine();
				for (int j = 0; j < N; j++) {
					map[i][j] = str.charAt(j) - '0';
					cost[i][j] = Integer.MAX_VALUE;
				}
			}
			dik();
			System.out.println("#" + t + " " + cost[N - 1][N - 1]);
		}
	}

	private static void dik() {
		cost[0][0] = map[0][0];
		pq.offer(new Node(0,0,map[0][0]));
		while(!pq.isEmpty()) {
			Node e = pq.poll();
			for (int i = 0; i < 4; i++) {
				int ny = e.y + dy[i];
				int nx = e.x + dx[i];
				if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
				if(cost[ny][nx] > cost[e.y][e.x] + map[ny][nx]) {
					cost[ny][nx] = cost[e.y][e.x] + map[ny][nx];
					pq.offer(new Node(ny, nx, cost[ny][nx]));
				}
			}
		}
	}

	static class Node {
		int y, x, d;
		Node(int y, int x, int d) {
			this.y = y;
			this.x = x;
			this.d = d;
		}
	}
}