#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;
}