/*
* @Author: MaxPhast
* @File: test.cpp
* @Date: 2026-04-06 22:34:25
*/
#include <bits/stdc++.h>
using namespace std;
#define ii pair <int , int>
#define iii pair <int , ii>
#define iiii pair <ii , ii>
#define FOR(i , l , r) for(int i = (l) , _r = (r) ; i <= _r ; ++ i)
#define FORD(i , r , l) for(int i = (r) , _l = (l) ; i >= _l ; -- i)
#define ALL(vec) vec.begin() , vec.end()
#define UNI(vec) sort(ALL(vec)) , vec.erase(unique(ALL(vec)) , vec.end())
#define pb push_back
#define MASK(i) (1ll << i)
#define BIT(mask , i) ((mask >> i) & 1ll)
#define ON(mask , i) (mask | MASK(i))
#define OFF(mask , i) (mask & (~MASK(i)))
#define TURN(mask , i) (mask ^ MASK(i))
#define BP(mask) __builtin_popcountll(mask)
#define sqr(x) (1ll * (x) * (x))
#define fi first
#define se second
#define oo (int)1e9
#define time() cerr << " \n " << "Time elapsed : " << 1000.0 * clock() / CLOCKS_PER_SEC << "ms."
#define IO(TASK) if(fopen(#TASK".INP" , "r")){freopen(#TASK".INP" , "r" , stdin); freopen(#TASK".OUT" , "w" , stdout);}
template <class X , class Y>
bool maxz(X &a , const Y b)
{
if(a < b)
{
a = b;
return true;
}
return false;
}
template <class X , class Y>
bool minz(X &a , const Y b)
{
if(a > b)
{
a = b;
return true;
}
return false;
}
namespace MaxPhast
{
const int WH = 505;
const int N = 15;
int n , w , h;
char c[WH][WH];
int dp[WH * WH][N][N];
vector <int> g[WH * WH];
int dx[4] = {0 , -1 , 0 , 1};
int dy[4] = {-1 , 0 , 1 , 0};
priority_queue <ii , vector <ii> , greater <ii>> pq;
bool ins(int x , int y)
{
return x >= 1 && x <= h && y >= 1 && y <= w;
}
int id(int x , int y)
{
return (x - 1) * w + y;
}
int next(int dir , int i , int j)
{
return (dir + (c[i][j] == 'A' ? -1 : (c[i][j] == 'C' ? 1 : 0)) + 4) % 4;
}
void solve()
{
cin >> n >> w >> h;
FOR(i , 1 , h)
{
FOR(j , 1 , w)
{
cin >> c[i][j];
}
}
FOR(i , 1 , h)
{
FOR(j , 1 , w)
{
FOR(dir , 0 , 3)
{
int newx = i , newy = j , newdir = next(dir , i , j);
while(ins(newx + dx[newdir] , newy + dy[newdir]) && c[newx + dx[newdir]][newy + dy[newdir]] != 'x')
{
newx += dx[newdir];
newy += dy[newdir];
newdir = next(newdir , newx , newy);
}
g[id(i , j)].pb(id(newx , newy));
}
}
}
FOR(i , 1 , w * h)
FOR(l , 1 , n)
FOR(r , 1 , n)
dp[i][l][r] = oo;
FOR(i , 1 , h)
{
FOR(j , 1 , w)
{
if(c[i][j] >= '1' && c[i][j] <= char(n + '0'))
{
dp[id(i , j)][c[i][j] - '0'][c[i][j] - '0'] = 0;
pq.push(ii(0 , id(i , j)));
while(!pq.empty())
{
ii cur = pq.top();
pq.pop();
if(cur.fi > dp[cur.se][c[i][j] - '0'][c[i][j] - '0'])
continue;
for(int &v : g[cur.se])
if(minz(dp[v][c[i][j] - '0'][c[i][j] - '0'] , dp[cur.se][c[i][j] - '0'][c[i][j] - '0'] + 1))
pq.push(ii(dp[v][c[i][j] - '0'][c[i][j] - '0'] , v));
}
}
}
}
FOR(r , 1 , n)
{
FORD(l , r - 1 , 1)
{
FOR(mid , l , r - 1)
{
FOR(i , 1 , h)
{
FOR(j , 1 , w)
{
minz(dp[id(i , j)][l][r] , dp[id(i , j)][l][mid] + dp[id(i , j)][mid + 1][r]);
}
}
}
FOR(i , 1 , h)
{
FOR(j , 1 , w)
{
if(dp[id(i , j)][l][r] < oo)
pq.push(ii(dp[id(i , j)][l][r] , id(i , j)));
}
}
while(!pq.empty())
{
ii cur = pq.top();
pq.pop();
if(cur.fi > dp[cur.se][l][r])
continue;
for(int &v : g[cur.se])
if(minz(dp[v][l][r] , dp[cur.se][l][r] + 1))
pq.push(ii(dp[v][l][r] , v));
}
}
}
int ans = oo;
FOR(i , 1 , h)
FOR(j , 1 , w)
minz(ans , dp[id(i , j)][1][n]);
if(ans < oo)
cout << ans;
else
cout << -1;
}
}
signed main()
{
ios_base :: sync_with_stdio(false) ; cin.tie(nullptr) ; cout.tie(nullptr) ;
IO(test);
MaxPhast :: solve();
time();
}
/*
*/
