Stampede!

You have an $n \times n$ game board. Some squares contain obstacles, but the left-most and right-most columns never do. The left-most column holds your $n$ pieces, one per row. Your goal is to move every piece to the right-most column as quickly as possible.

In one turn you can move each piece one square north, south, east, or west, or leave that piece where it is. A piece cannot move onto a square that contains an obstacle, and two pieces cannot move onto the same square on the same turn. All pieces move at the same time, so a piece may move onto a square another piece currently occupies as long as that other piece leaves the square on the same turn.

Given $n$ and the obstacles, determine the fewest number of turns needed to get every piece to the right-most column of the board.

The input holds several test cases. Each test case starts with a positive integer $n$, the size of the game board, with $n \le 25$. The next $n$ lines contain $n$ characters each. If the $j$th character of the $i$th line is X, square $(i, j)$ contains an obstacle; a . means the square is free. Rows and columns are numbered from 0.

Column 0 and column $n-1$ never contain an obstacle, and there is always at least one obstacle-free path between those two columns.

A line holding a single 0 ends the input.

For each test case print one line in the form Case i: t, where i is the test case number starting at 1 and t is the fewest turns needed to move every piece from the left-most column to the right-most column.