#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <functional>
#include <algorithm>
#include <queue>
#include <memory.h>
  
using namespace std;
  
int v;
struct Vertex
{
    int cost;
};
  
Vertex G[130][130];
int d[130][130];
const int INF = numeric_limits<int>::max();
struct P
{
    int y, x, cost;
    bool operator<(const P& p) const
    {
        return cost < p.cost;
    }
    P(int _y, int _x, int _cost) 
    {
        y = _y;
        x = _x;
        cost = _cost;
    }
    bool operator>(const P& p) const
    {
        return cost > p.cost;
  
    }
    P(){}
};
void dijkstra(int sy, int sx)
{
//  typedef pair<int, int> P; // cost, to
    priority_queue<P, vector<P>, greater<P>> que;
      
    for(int i=1; i<=v; i++)
    {
        for(int j=1; j<=v; j++)
            d[i][j] = INF; 
    }
    d[sy][sx] = G[sy][sx].cost;
    que.push(P(sy, sx, G[sy][sx].cost));
  
    while(!que.empty())
    {
        auto p = que.top();
        que.pop();
  
  
        int Vy = p.y;
        int Vx = p.x;
 
  
        int dx[] = {1, -1, 0, 0};
        int dy[] = {0, 0, 1, -1};
        for(int i=0; i<=3; i++) // 좌표 index
        {
            int newY = Vy + dy[i];
            int newX = Vx + dx[i];
  
            Vertex v = G[newY][newX];
            if(d[newY][newX] > d[Vy][Vx] + v.cost)
            {
                d[newY][newX] = d[Vy][Vx] + v.cost;
                P newP;
                newP.y = newY;
                newP.x = newX;
                newP.cost = d[newY][newX];
                que.push(newP);
            }
        }
    }
}
  
int main()
{
    int cnt = 1;
    while(true)
    {
        memset(d, 0, sizeof(int) * 130 * 130);
  
        cin >> v;
//      cout << v << endl;
//      v = n;
        if(v == 0)
            break;
  
        for(int i=1; i<=v; i++)
        {
            for(int j=1; j<=v; j++)
            {
                int t;
                cin >> t;
                G[i][j].cost = t; // i, j
            }
        } 
  
        dijkstra(1, 1); 
        printf("Problem %d: %d\n", cnt, d[v][v]);
        cnt++;
////        cout << v << endl;
//      for(int i=1; i<=v; i++)
//      {
//          for(int j=1; j<=v; j++)
//          {
//              printf("%d ", d[i][j]);
//          }
//          printf("\n");
//      } 
    }
  
    return 0;
}