녹색 옷 입은 애가 젤다지?

젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 '도둑루피'라고 불리는 검은색 루피도 있는데, 이것을 얻으면 오히려 가지고 있던 루피가 줄어든다.

주인공 링크는 지금 도둑루피로만 가득 찬 $N \times N$ 크기 동굴의 가장 왼쪽 위 칸, 즉 $[0][0]$ 칸에 있다. 링크는 이 동굴의 반대편 출구인 가장 오른쪽 아래 칸 $[N-1][N-1]$까지 이동해야 한다.

동굴의 각 칸에는 도둑루피가 하나씩 놓여 있으며, 어떤 칸을 지나가면 그 칸에 적힌 도둑루피의 크기만큼 소지금을 잃는다. 이때 출발 칸과 도착 칸도 지나가는 칸에 포함된다. 링크는 한 번에 상하좌우로 인접한 칸으로 한 칸씩만 이동할 수 있다.

링크가 출발 칸에서 도착 칸까지 이동하면서 잃을 수밖에 없는 루피의 최소 합은 얼마인가?

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫째 줄에는 동굴의 크기를 나타내는 정수 $N$이 주어진다. ($2 \le N \le 125$)

이어지는 $N$개의 줄에는 각 줄마다 $N$개의 정수가 공백으로 구분되어 주어지며, 동굴의 각 칸에 놓인 도둑루피의 크기를 위쪽 줄부터 차례대로 나타낸다. 어떤 칸의 값이 $k$이면 그 칸을 지날 때 $k$루피를 잃는다는 뜻이다. 주어지는 모든 정수는 $0$ 이상 $9$ 이하의 한 자리 수다.

$N = 0$인 줄이 주어지면 전체 입력이 끝난다.

각 테스트 케이스마다 한 줄에 답을 출력한다. $t$번째 테스트 케이스(번호는 $1$부터 시작한다)에 대해서는 Problem t: c 형식으로 출력하며, 여기서 $c$는 링크가 잃을 수밖에 없는 루피의 최소 합이다.