# Appreciation

/*
 * Problem :: <No> / <Name>
 *
 * Kind :: Dijkstra
 *
 * Insight
 * - 동굴의 제일 왼쪽 위 [0][0] 에서
 *   동굴의 제일 오른쪽 아래 [N-1][N-1] 까지
 *   잃는 금액을 최소로 하여 이동해야 한다
 *   + dp[i][j] = [0][0] -> [i][j] 까지 이동시 잃는 루피의 최솟값
 *     (위, 아래, 왼쪽, 오른쪽) 인접한 칸들을 확인해서
 *     그 칸들의 dp 를 Relaxation 시켜주자
 *     # 한 지점으로부터 다른 지점으로까지 최단 경로를 구하고
 *       가중치가 전부 0 이상이므로
 *       다익스트라 알고리즘을 활용할 수 있다
 *
 * Point
 * - 물론 BFS(revisit) 로 완전탐색을 하여
 *   [0][0] ~ [N-1][N-1] 의 모든 칸의 dp[i][j] 를 구할 수 있지만
 *   굳이 모든 칸의 정보를 알 필요는 없으므로
 *   문제의 의도대로라면 다익스트라를 쓰는 것이 좋을 듯 하다
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <cstring>
#include <queue>
#include <functional>

using namespace std;

#define endl '\n'

// Set up : Global Variables
struct Point { int y, x; };
int dy[4] = {+1, 0, 0, -1};
int dx[4] = {0, +1, -1, 0};
struct State { int c; Point p; };

// Set up : Functions Declaration
bool operator < (State u, State v);


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int tc = 0;
    while (true) {
        int N; cin >> N;
        if (N == 0) break;

        tc++; /* 테스트 케이스 번호 */
        int A[N][N];
        for (int i=0; i<N; i++)
            for (int j=0; j<N; j++)
                cin >> A[i][j];

        // Process
        /* 좌표 (y,x) 가 유효하면 true 를 반환, 그 외 false 를 반환하는 함수 */
        function<bool(int,int)> isValid = [N](int y, int x){
            return y >= 0 && y < N && x >= 0 && x < N;
        };

        /* (isDone[i][j] = ture) == (더이상 dp[i][j] 는 Relaxation 이 일어나지 않음)
         * (isDone[i][j] = false) == (dp[i][j] 에 Relaxation 이 일어날 수 있음) */
        bool isDone[N][N];
        memset(isDone, false, sizeof(isDone));
        /* dp[i][j] = [0][0] -> [i][j] 까지 이동시 잃는 루피의 최솟값 */
        int dp[N][N];
        memset(dp, -1, sizeof(dp));
        priority_queue<State> pq; /* 최소힙 */

        dp[0][0] = A[0][0];
        pq.push({A[0][0], {0, 0}});

        while (not(pq.empty())) {
            int cc = pq.top().c; /* 현재 비용 */
            auto [cy, cx] = pq.top().p; /* 현재 좌표 */
            pq.pop();

            /* dp[cy][cx] < cc 이면
             * dp[cy][cx] 가 적어도 한 번 이상 Relaxation 이 일어났다는 뜻이므로
             * Relaxation 되기 이전의 값인 cc 로 인접한 다른 칸들을 Relaxation 시킬 필요 없음
             * (알고리즘 상으로 Relaxation 시킬 수도 없음) => 연산을 줄이는 최적화 */
            if (dp[cy][cx] < cc) continue;

            /* dp[cy][cx] 계산 끝 => 더이상 Relaxation 이 일어나지 않음 */
            isDone[cy][cx] = true;
            if (cy == N-1 && cx == N-1) break; /* [N-1][N-1] 도착 */

            for (int i=0; i<4; i++) {
                int ny = cy + dy[i]; /* 인접한 칸의 y 좌표 */
                int nx = cx + dx[i]; /* 인접한 칸의 x 좌표 */
                /* 인접한 칸의 좌표가 유효하고 아직 Relaxation 될 수 있다면 */
                if (isValid(ny, nx) && not(isDone[ny][nx])) {
                    /* Relaxation 시도 */
                    if (dp[ny][nx] == -1 || dp[ny][nx] > dp[cy][cx] + A[ny][nx]) {
                        dp[ny][nx] = dp[cy][cx] + A[ny][nx]; /* Relaxation 성공 */
                        pq.push({dp[ny][nx], {ny, nx}}); /* 최소힙에 추가 */
                    }
                }
            }
        }

        // Control : Output
        printf("Problem %d: %d\n", tc, dp[N-1][N-1]);
    }
}

// Helper Functions
bool operator < (State u, State v)
/* State 구조체의 최소힙 정렬을 위한 연산자 오버로딩 */
{
    return u.c > v.c;
}