Is the Kid in Green Zelda?

In the Legend of Zelda games, the unit of currency is the rupee. However, there also exist black "thief rupees": picking one up actually decreases the rupees you are holding.

Link, the hero, is currently in the top-left cell — cell $[0][0]$ — of an $N \times N$ cave filled entirely with thief rupees. He must travel to the cave's exit on the opposite side, the bottom-right cell $[N-1][N-1]$.

Every cell of the cave holds a thief rupee, and passing through a cell makes Link lose an amount of money equal to that cell's thief-rupee value. Both the starting cell and the destination cell count among the cells he passes through. Link may move one cell at a time to a cell that is horizontally or vertically adjacent.

What is the minimum total number of rupees Link is forced to lose while travelling from the start to the exit?

The input consists of several test cases.

The first line of each test case contains an integer $N$, the size of the cave. ($2 \le N \le 125$)

The next $N$ lines each contain $N$ integers separated by spaces, giving the thief-rupee value in each cell of the cave, row by row from top to bottom. If a cell's value is $k$, passing through it costs $k$ rupees. Every integer given is a single digit between $0$ and $9$ inclusive.

A line containing $N = 0$ signals the end of the input.

For each test case, print the answer on its own line. For the $t$-th test case (numbering starts at $1$), print it in the format Problem t: c, where $c$ is the minimum total number of rupees Link is forced to lose.