Billiards Sorting

Rotation is a pocket billiards game played with 15 balls numbered 1 to 15. At the start of a game the balls sit in a triangular rack in this order. The order is simplified from the real rules of Rotation to keep the problem short.

        [ 1]
      [ 2][ 3]
    [ 4][ 5][ 6]
  [ 7][ 8][ 9][10]
[11][12][13][14][15]

You build automatic billiards machines. Your first machine stacks the balls into the triangle, but it cannot put them in the right order.

So you are building a second machine that repairs the order by swapping balls. To keep it cheap, the machine swaps ball 1 only with a ball that touches it from the row above or the row below. Two balls in the same row are never swapped, even when they sit side by side. In the rack below the machine can perform exactly four swaps: (1,2), (1,3), (1,8), (1,9).

        [ 5]
      [ 2][ 3]
    [ 4][ 1][ 6]
  [ 7][ 8][ 9][10]
[11][12][13][14][15]

The ball in row $r$, position $c$ from the left, touches positions $c-1$ and $c$ of row $r-1$, and positions $c$ and $c+1$ of row $r+1$, whenever those positions lie inside the triangle.

A rack of $N$ rows is in the right order when reading the rows from top to bottom, each row from left to right, gives $1, 2, \dots, N(N+1)/2$. Write a program that computes the minimum number of swaps.

The input holds several test cases.

The first line of a test case has one integer $N$ ($1 \le N \le 5$), the number of rows. The next $N$ lines describe the rack that the first machine stacked: line $i$ has exactly $i$ integers, the numbers of the balls in row $i$ from left to right. The numbers on those $N$ lines form a permutation of $1$ through $N(N+1)/2$.

The last line has a single 0. Print nothing for it.

For each test case, print one line Case x: y, where $x$ is the test case number starting from 1 and $y$ is the minimum number of swaps.

Every rack in the input can be put in the right order, and no rack needs more than 45 swaps.