스탬피드!

$n \times n$ 크기의 게임판이 있다. 일부 칸에는 장애물이 있지만, 맨 왼쪽 열과 맨 오른쪽 열에는 장애물이 없다. 맨 왼쪽 열에는 내 말 $n$개가 한 행에 하나씩 놓여 있다. 목표는 말을 모두 맨 오른쪽 열로 최대한 빨리 옮기는 것이다.

한 턴에 각 말을 위, 아래, 왼쪽, 오른쪽 중 한 방향으로 한 칸 움직이거나 그 자리에 그대로 둘 수 있다. 장애물이 있는 칸으로는 움직일 수 없고, 같은 턴에 두 말이 같은 칸으로 움직일 수도 없다. 모든 말이 동시에 움직이므로, 어떤 칸에 있던 말이 같은 턴에 그 칸을 떠난다면 다른 말이 그 칸으로 들어갈 수 있다.

$n$과 장애물 배치가 주어질 때, 말을 모두 판의 맨 오른쪽 열로 옮기는 데 필요한 최소 턴 수를 구하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 게임판의 크기를 나타내는 양의 정수 $n$이 주어진다 ($n \le 25$). 이어지는 $n$개의 줄에는 각각 문자 $n$개가 주어진다. $i$번째 줄의 $j$번째 문자가 X이면 $(i, j)$ 칸에 장애물이 있고, .이면 장애물이 없다. 행 번호와 열 번호는 0부터 센다.

0번 열과 $n-1$번 열에는 장애물이 절대 없고, 두 열을 잇는 장애물 없는 경로가 항상 하나 이상 있다.

0 하나만 있는 줄이 입력의 끝을 뜻한다.

각 테스트 케이스마다 Case i: t 형식으로 한 줄씩 출력한다. i는 1부터 시작하는 테스트 케이스 번호이고, t는 말을 모두 맨 왼쪽 열에서 맨 오른쪽 열로 옮기는 데 필요한 최소 턴 수이다.