핼러윈 다음 날 아침

문제

당신은 놀이공원에서 오바케야시키(obakeyashiki), 즉 손님들이 좁고 어두운 복도를 걸어 지나가는 귀신의 집의 운영자로 일하고 있다. 이 집은 활기찬 귀신들을 자랑하는데, 사실 이 귀신들은 운영자가 원격으로 조종하는 로봇으로, 복도 여기저기에 숨어 있다. 어느 날 아침, 당신은 귀신들이 있어야 할 위치에 있지 않다는 것을 발견했다. 아, 어제는 핼러윈이었다. 믿거나 말거나, 초자연적인 영혼들이 밤사이에 그들을 복도 이곳저곳으로 옮겨 놓은 것이다. 당신은 손님들이 오기 전에 그들을 올바른 위치로 옮겨 놓아야 한다. 당신의 매니저는 귀신들을 원상 복구하는 데 얼마나 걸리는지 몹시 알고 싶어 한다.

이 문제에서는 집의 층 지도가 주어졌을 때 모든 귀신을 있어야 할 위치로 옮기는 데 필요한 최소 스텝 수를 구하는 프로그램을 작성해야 한다.

하나의 층은 정사각형 칸들의 행렬로 이루어진다. 각 칸은 귀신이 들어갈 수 없는 벽 칸이거나 들어갈 수 있는 복도 칸이다.

각 스텝마다 당신은 임의의 수의 귀신을 동시에 움직일 수 있다. 각 귀신은 현재 칸에 그대로 있거나, 다음 조건을 만족하는 경우 자신의 4-이웃(즉 바로 왼쪽, 오른쪽, 위, 아래) 복도 칸 중 하나로 움직일 수 있다:

스텝이 끝났을 때 한 위치를 두 마리 이상의 귀신이 차지하지 않는다.
그 스텝에서 어떤 두 귀신도 서로 위치를 맞바꾸지 않는다.

예를 들어, 다음의 (부분) 지도와 같이 귀신들이 놓여 있다고 하자. 여기서 샤프 기호('#')는 벽 칸을, 'a', 'b', 'c'는 귀신을 나타낸다.

####
 ab#
#c##
####

다음 네 개의 지도는 한 스텝 뒤에 가능한 귀신들의 위치 전부를 보여 준다.

####   ####   ####   ####
 ab#   a b#   acb#   ab #
#c##   #c##   # ##   #c##
####   ####   ####   ####

입력

입력은 최대 10개의 데이터셋으로 이루어지며, 각 데이터셋은 집의 층 지도를 나타낸다. 데이터셋의 형식은 다음과 같다.

w h n
c11 c12 ... c1w
c21 c22 ... c2w
...
ch1 ch2 ... chw

첫째 줄의 $w$, $h$, $n$은 공백으로 구분된 정수이다. $w$와 $h$는 각각 집의 층 너비와 높이이다. $n$은 귀신의 수이다. 이들은 다음 제약을 만족한다.

$4 \le w \le 16$, $4 \le h \le 16$, $1 \le n \le 3$

이어지는 $h$개의 줄, 각 $w$개의 문자는 층 지도이다. 각 $c_{ij}$는 다음 중 하나이다:

벽 칸을 나타내는 '#',
어떤 귀신의 초기 위치인 복도 칸을 나타내는 소문자,
대응하는 소문자 귀신이 있어야 할 위치인 복도 칸을 나타내는 대문자,
위의 어느 것도 아닌 복도 칸을 나타내는 공백.

각 지도에서 a부터 시작하는 처음 $n$개의 문자와 A부터 시작하는 처음 $n$개의 문자는 각각 정확히 한 번씩 나타난다. 지도의 가장 바깥쪽 칸은 벽이다. 즉 첫째 줄과 마지막 줄의 모든 문자는 샤프이며, 각 줄의 첫 번째와 마지막 문자도 샤프이다. 지도의 모든 복도 칸은 연결되어 있다. 즉 어떤 복도 칸에서 출발해 4-이웃의 복도 칸들을 따라가면 다른 임의의 복도 칸에 도달할 수 있다. 마찬가지로 모든 벽 칸도 연결되어 있다. 지도의 임의의 2 x 2 영역에는 적어도 하나의 샤프가 있다. 모든 지도에는 모든 귀신을 있어야 할 위치로 되돌리는 귀신 이동의 수열이 존재한다고 가정해도 된다.

마지막 데이터셋 다음에는 공백으로 구분된 세 개의 0으로 이루어진 줄이 온다.

출력

입력의 각 데이터셋에 대해, 귀신들을 있어야 할 위치로 되돌리는 데 필요한 최소 스텝 수를 담은 한 줄을 출력해야 한다. 출력 줄에는 공백과 같은 추가 문자가 들어 있으면 안 된다.