妖怪的闺房是一个 $n*m$ 的矩阵，而且某些地方安装了带锁的门。钥匙藏在闺房另外的某些地方。

刚開始 WP 被关在 $(s_x,s_y)$ 的位置，离开闺房的门在 $(e_x,e_y)$ 的位置。WP 每分钟仅仅能从一个坐标走到相邻四个坐标中的当中一个。

妖怪每 $t$ 分钟回闺房视察一次。若发现 CZ 不在原位置便把他再拎回去。经过若干次的尝试，CZ 已画出整个闺房的地图。如今请你帮他计算是否能再次成功逃亡。

仅仅要在妖怪下次视察之前走到出口就算离开闺房。假设妖怪回来的时候刚好走到出口或还未到出口都算逃亡失败。

每组測试数据的第一行有三个整数 $n,m,t\ (2\leq n,m\leq 20,\ t>0)$。

接下来的 $n$ 行 $m$ 列为闺房的地图，当中包含:

. 代表路
* 代表墙
@ 代表CZ的起始位置
^ 代表闺房的出口
A-J 代表带锁的门,相应的钥匙分别为 a-j
a-j 代表钥匙，相应的门分别为 A-J

每组測试数据之间有一个空行。

针对每组測试数据，假设能够成功逃亡。请输出最少须要多少分钟才干离开。假设不能则输出-1。