같은 색 패널 연결하기

후쿠오카 박사는 특별한 패널을 발명했다. 각 패널은 한 변의 길이가 1인 정사각형이며, 노랑, 분홍, 빨강, 보라, 초록, 파랑의 여섯 가지 색 중 하나를 가진다. 이 패널에는 두 가지 성질이 있다.

첫째, 같은 색 패널 두 개 이상이 변을 맞대고 인접하면 맞닿은 변이 녹으면서 서로 융합된다. 융합된 패널들은 하나의 다각형 패널로 합쳐진다.

둘째, 전기 충격을 주면 패널의 색을 여섯 가지 색 중 하나로 바꿀 수 있으며, 그 색은 파형으로 조절한다. 이미 융합된 패널에 전기 충격을 주면 그 전체가 지정한 하나의 색으로 바뀐다.

박사는 융합된 패널이 단위 패널에 비해 색과 크기 면에서 얼마나 강한지 조사하기 위해, 패널들을 원하는 색의 다각형 패널로 융합하려고 한다.

그림 C-1: 패널과 그 초기 색

패널들은 복잡한 화학 공정을 통해 여러 개가 동시에 합성되어 바탕판 위에 직사각형 모양으로 배열된다(그림 C-1). 만들어진 패널의 색은 무작위이다. 그림 C-1에서 보라색(4번) 패널 두 개는 서로 인접해 있으므로 처음부터 이미 융합되어 있음에 유의하라.

박사는 한 패널에 전극을 설치하고, 목표 색에 맞는 적절한 순서로 전기 충격을 여러 번 주어 색을 바꿈으로써, 융합된 패널이 인접한 패널들을 단계적으로 흡수하도록 하여 목표 색의 더 큰 패널을 얻을 수 있다. 다만 패널은 여섯 번째 전기 충격을 받으면 부서진다. 즉, 한 패널(또는 융합된 패널)의 색은 최대 다섯 번까지만 바꿀 수 있다.

그림 C-1의 배치에서 왼쪽 위 모서리 패널에 전극을 붙였다고 하자. 먼저 그 패널의 색을 노랑에서 파랑으로 바꾸면 인접한 두 패널이 하나로 융합된다(그림 C-2).

그림 C-2: 왼쪽 위 모서리 패널의 색을 노랑(1번)에서 파랑(6번)으로 변경.

두 번째로 왼쪽 위 융합 패널의 색을 파랑에서 빨강으로 바꾸면, 단위 패널 세 개로 이루어진 빨간 융합 패널이 새로 만들어진다(그림 C-3). 이어서 그 융합 패널의 색을 빨강에서 보라로 바꾸면 다시 융합이 일어나 단위 패널 다섯 개짜리 패널이 된다(그림 C-4).

그림 C-3: 왼쪽 위 모서리 패널의 색을 파랑(6번)에서 빨강(3번)으로 변경.

그림 C-4: 왼쪽 위 모서리 패널의 색을 빨강(3번)에서 보라(4번)으로 변경.

또한 보라에서 분홍으로 바꾸어 그림 C-5의 분홍 융합 패널을 만들고, 다시 분홍에서 초록으로 바꾸면 그림 C-6의 초록 융합 패널을 얻는다. 이 초록 융합 패널은 단위 패널 열 개로 이루어진다.

그림 C-5: 왼쪽 위 모서리 패널의 색을 보라(4번)에서 분홍(2번)으로 변경.

그림 C-6: 왼쪽 위 모서리 패널의 색을 분홍(2번)에서 초록(5번)으로 변경.

박사는 다양한 크기와 색의 융합 패널의 강도를 확인하기 위해, 목표 색으로 가능한 한 많은 패널을 융합하고자 한다. 색을 다섯 번 바꾸어 목표 색을 가진 가장 큰 융합 패널을 얻는 변경 순서를 찾는 프로그램을 작성하라. 전극은 왼쪽 위 모서리 패널에 고정되어 있다.

입력은 여러 개의 데이터셋으로 이루어지며, 각 데이터셋의 형식은 다음과 같다.

h w c
p1,1 p1,2 ... p1,w
p2,1 p2,2 ... p2,w
...
ph,1 ph,2 ... ph,w

$h$와 $w$는 주어진 직사각형의 높이와 너비를 나타내는 8 이하의 양의 정수이다. $c$는 최종 융합 패널의 목표 색을 나타내는 6 이하의 양의 정수이다. $p_{i,j}$는 위치 $(i, j)$에 있는 패널의 초기 색을 나타내는 6 이하의 양의 정수이다.

입력의 끝은 공백 하나로 구분된 세 개의 0으로 이루어진 줄로 표시된다.

각 데이터셋에 대해, 왼쪽 위 모서리 패널의 색을 다섯 번 바꾼 뒤 왼쪽 위 모서리의 융합 패널이 목표 색을 가질 때 가능한 단위 패널 수의 최댓값을 출력한다. 그 밖의 문자는 출력하지 않는다.