////  main.cpp//  hdu_1429////  Created by Luke on 16/10/8.//  Copyright © 2016年 Luke. All rights reserved.//#include <iostream>#include <string>#include <cstring>#include <queue>using namespace std;int n,m,t;int ex,ey;char Map[25][25];int bit[10];struct Node{    int y,x;    int key;    int step;};bool vis[25][25][1025];int dir[4][2]={1,0,-1,0,0,1,0,-1};bool ok(Node &te){    if(te.step>=t)        return false;    if(te.y<0||te.y>=n||te.x<0||te.x>=m)        return false;    if(vis[te.y][te.x][te.key])        return false;    if(Map[te.y][te.x]==‘*‘)        return false;    if(Map[te.y][te.x]>=‘A‘&&Map[te.y][te.x]<=‘J‘)    {        int fix=bit[Map[te.y][te.x]-‘A‘];        if(!(fix&te.key))            return false;    }    if(Map[te.y][te.x]>=‘a‘&&Map[te.y][te.x]<=‘j‘)        te.key|=bit[Map[te.y][te.x]-‘a‘];    vis[te.y][te.x][te.key]=1;    return true;}int bfs(int sy,int sx){    queue<Node> q;    q.push((Node){sy,sx,0,0});    memset(vis,0,sizeof(vis));    Node now,nx;    while(!q.empty())    {        now=q.front(),q.pop();        if(now.y==ey&&now.x==ex)            return now.step;        for(int i=0;i<4;i++)        {            nx=now;            nx.y+=dir[i][0],nx.x+=dir[i][1];            nx.step++;            if(ok(nx))                q.push(nx);        }    }    return -1;}int main(int argc, const char * argv[]) {    cin.sync_with_stdio(false);    bit[0]=1;    for(int i=1;i<10;i++)        bit[i]=bit[i-1]<<1;    while(cin>>n>>m>>t)    {        int sx,sy;        bool fix[10];        memset(fix,0,sizeof(fix));        for(int i=0;i<n;i++)            for(int j=0;j<m;j++)            {                cin>>Map[i][j];                if(Map[i][j]>=‘A‘&&Map[i][j]<=‘J‘)                    fix[Map[i][j]-‘A‘]=1;                if(Map[i][j]==‘^‘)                    ex=j,ey=i;                if(Map[i][j]==‘@‘)                    sx=j,sy=i;            }        for(int i=0;i<n;i++)            for(int j=0;j<m;j++)                if(Map[i][j]>=‘a‘&&Map[i][j]<=‘j‘)                    if(!fix[Map[i][j]-‘a‘])                        Map[i][j]=‘.‘;        cout<<bfs(sy,sx)<<endl;    }    return 0;}