당구공 정렬

로테이션은 1번부터 15번까지 번호를 붙인 공 15개로 하는 포켓 당구 경기다. 경기를 시작할 때 공은 아래 그림의 순서대로 삼각형 랙 안에 놓인다. 문제를 짧게 하려고 실제 로테이션 규칙의 공 순서를 바꿨다.

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

당신은 당구 기계를 만드는 기술자다. 첫 번째 기계는 공을 삼각형으로 쌓는 데까지는 성공했지만 순서를 맞추지는 못한다.

그래서 공을 교환해 순서를 바로잡는 두 번째 기계를 만들고 있다. 비용을 줄이려고 이 기계는 1번 공을 바로 윗줄이나 바로 아랫줄에서 맞닿은 공하고만 교환할 수 있다. 같은 줄에 나란히 놓인 두 공은 붙어 있어도 교환하지 못한다. 아래 배치에서 기계가 할 수 있는 교환은 (1,2), (1,3), (1,8), (1,9) 네 가지다.

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

위에서 $r$번째 줄의 왼쪽에서 $c$번째 자리에 있는 공은 $r-1$번째 줄의 $c-1$번째와 $c$번째 자리, $r+1$번째 줄의 $c$번째와 $c+1$번째 자리에 맞닿는다. 그 자리가 삼각형 안에 있을 때만 맞닿는다.

$N$줄짜리 랙은 줄을 위에서 아래로, 각 줄을 왼쪽에서 오른쪽으로 읽은 결과가 $1, 2, \dots, N(N+1)/2$일 때 순서가 맞다. 필요한 최소 교환 횟수를 구하는 프로그램을 작성하라.

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

각 테스트 케이스의 첫 줄에는 줄 수 $N$ ($1 \le N \le 5$)이 주어진다. 이어지는 $N$개 줄은 첫 번째 기계가 쌓은 배치를 나타낸다. $i$번째 줄에는 정수가 정확히 $i$개 있고, 위에서 $i$번째 줄에 왼쪽부터 놓인 공의 번호다. 이 $N$개 줄에 나온 수를 모으면 $1$부터 $N(N+1)/2$까지의 순열이다.

마지막 줄에는 0이 하나 주어진다. 이 줄에 대해서는 아무것도 출력하지 않는다.

각 테스트 케이스마다 Case x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 최소 교환 횟수다.

입력으로 주어지는 배치는 모두 순서를 바로잡을 수 있고, 45번보다 많이 교환해야 하는 배치는 없다.