[SWEA] 최소비용

T = int(input())
for TC in range(T):
    N = int(input())
    MAP = [list(map(int, input().split())) for _ in range(N)]
    check = [[10000] * N for _ in range(N)]
    check[0][0] = 0
    q = []
    q.append((0, 0))
    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]

    while len(q) != 0:
        now_dr, now_dc = q.pop(0)
        for i in range(4):
            next_dr = now_dr + dr[i]
            next_dc = now_dc + dc[i]
            if 0 > next_dr or next_dr >= N or 0 > next_dc or next_dc >= N:
                continue
            temp = 1
            if MAP[next_dr][next_dc] > MAP[now_dr][now_dc]:
                temp = MAP[next_dr][next_dc] - MAP[now_dr][now_dc] + 1
            if check[next_dr][next_dc] > check[now_dr][now_dc] + temp:
                check[next_dr][next_dc] = check[now_dr][now_dc] + temp
                q.append((next_dr, next_dc))

    print('#{} {}'.format(TC+1, check[N-1][N-1]))