题目描述（Description）

你在一家游乐园里担任“鬼屋”（日语称作 obakeyashiki）的工作人员，负责操作里面的“鬼魂”机器人。这些“鬼魂”藏身于黑暗狭窄的走廊中，由你远程操控。

某天早上，你发现所有的鬼魂都不在应在的位置上。啊，昨天是万圣节！不管你信不信，可能真有灵异现象把鬼魂们在夜里移了位。现在你必须赶快把它们移回正确的位置，在游客到来之前完成准备。你的经理急切地想知道需要多少步才能复位全部鬼魂。

本题要求你编写一个程序，在满足约束条件下，计算将所有鬼魂移动到目标位置所需的最少步数。

地图说明（Map）

地图由一个矩阵组成，每个单元格可以是以下几种：

• 墙壁格（不可进入）：用 # 表示
• 走廊格（可进入）：用空格 ' ' 表示
• 鬼魂当前所在位置：用小写字母 'a', 'b', 'c' 表示
• 鬼魂目标位置：用对应的大写字母 'A', 'B', 'C' 表示

例如，以下是一个部分地图的例子：

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

其中 a、b 和 c 是鬼魂，# 是墙壁。

移动规则（Move Rules）

• 每一步中，你可以同时移动任意数量的鬼魂。

• 每个鬼魂可以选择原地不动或移动到上下左右四个方向中的某一个走廊格中。

• 限制条件如下：

  1. 每个格子中最多只能有一个鬼魂。
  2. 不能有两个鬼魂交换位置（即不能 a->b，b->a 这样换位置）。

输入格式（Input）

输入最多包含 $10$ 组测试数据。

每组数据第一行为三个整数 $w, h, n$（用空格分隔）：

• $w$：地图的宽度，满足 $4 \leq w \leq 16$
• $h$：地图的高度，满足 $4 \leq h \leq 16$
• $n$：鬼魂的数量，满足 $1 \leq n \leq 3$

接下来是 $h$ 行，每行 $w$ 个字符，表示地图内容。

• 每个字符是：#, 小写字母（起始位置），大写字母（目标位置），或空格。

• 每个测试数据的地图：

  • 起始位置（a, b, c）与目标位置（A, B, C）一一对应且各出现一次。
  • 地图边界全部是墙壁（#）。
  • 所有走廊格连通（任意两个走廊格之间存在路径）。
  • 所有墙壁格也连通。
  • 地图中任意 $2 \times 2$ 区域至少有一个 #。
  • 每组测试数据都存在解，即一定能通过若干步将所有鬼魂移动到目标位置。

输入以一行 0 0 0 结束。

输出格式（Output）

每组测试数据输出一行，表示最少所需步数（即让所有鬼魂回到目标位置的最小移动次数）。

输出中不应包含多余字符（例如空格或换行）。

样例输入

5 5 2
#####
#A#B#
# # #
#b#a#
#####
16 4 3
################
##          ####
# ABCcba      ##
################
16 16 3
################
###  ##  ##  ## #
##  # c# #  #####
b# #  # # #  #  #
# ## a# # #  ### 
## #### ## # ## 
# #  #  # ##### 
# ## ## #### #B#
#    ## C#  # ###
# # ####### #  #
###### A## #  # 
# ## ################
0 0 0

样例输出

7
36
77

数据来源

Japan 2007（日本 2007 年程序竞赛）