/*
* @Author: MaxPhast
* @File: test.cpp
* @Date: 2026-04-06 13:02:54
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#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)1e18
#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 = 5e2;
const int N = 10;
int n , w , h;
int dp[WH][WH][N][N][4][2];
char c[WH][WH];
int dx[4] = {0 , -1 , 0 , 1};
int dy[4] = {-1 , 0 , 1 , 0};
struct State
{
int cost , i , j , l , r , dir , t;
State()
{
cost = i = j = l = r = dir = t = 0;
}
State(int _cost , int _i , int _j , int _l , int _r , int _dir , int _t)
{
cost = _cost;
i = _i;
j = _j;
l = _l;
r = _r;
dir = _dir;
t = _t;
}
bool operator < (const State &other) const
{
return cost > other.cost;
}
};
priority_queue <State> pq;
bool ins(int x , int y)
{
return x >= 0 && x < h && y >= 0 && y < w;
}
void solve()
{
cin >> n >> w >> h;
FOR(i , 0 , h - 1)
FOR(j , 0 , w - 1)
cin >> c[i][j];
FOR(i , 0 , h - 1)
{
FOR(j , 0 , w - 1)
{
FOR(l , 0 , n - 1)
{
FOR(r , 0 , n - 1)
{
FOR(dir , 0 , 3)
{
FOR(t , 0 , 1)
{
dp[i][j][l][r][dir][t] = oo;
}
}
}
}
}
}
FOR(i , 0 , h - 1)
{
FOR(j , 0 , w - 1)
{
if(c[i][j] >= '1' && c[i][j] <= char(n + '0'))
{
FOR(dir , 0 , 3)
{
dp[i][j][c[i][j] - '1'][c[i][j] - '1'][dir][0] = 0;
pq.push(State(0 , i , j , c[i][j] - '1' , c[i][j] - '1' , dir , 0));
}
}
}
}
while(!pq.empty())
{
State cur = pq.top();
pq.pop();
if(cur.cost > dp[cur.i][cur.j][cur.l][cur.r][cur.dir][cur.t])
continue;
if(cur.t)
{
int newdir = (cur.dir + (c[cur.i][cur.j] == 'A' ? -1 : (c[cur.i][cur.j] == 'C' ? 1 : 0)) + 4) % 4;
int newx = cur.i + dx[newdir];
int newy = cur.j + dy[newdir];
if(ins(newx , newy) && c[newx][newy] != 'x')
{
if(minz(dp[newx][newy][cur.l][cur.r][newdir][cur.t] , dp[cur.i][cur.j][cur.l][cur.r][cur.dir][cur.t]))
pq.push(State(dp[newx][newy][cur.l][cur.r][newdir][cur.t] , newx , newy , cur.l , cur.r , newdir , cur.t));
}
else
{
FOR(dir , 0 , 3)
if(minz(dp[cur.i][cur.j][cur.l][cur.r][dir][0] , dp[cur.i][cur.j][cur.l][cur.r][cur.dir][cur.t]))
pq.push(State(dp[cur.i][cur.j][cur.l][cur.r][dir][0] , cur.i , cur.j , cur.l , cur.r , dir , 0));
}
}
else
{
int newdir = (cur.dir + (c[cur.i][cur.j] == 'A' ? 1 : (c[cur.i][cur.j] == 'C' ? -1 : 0)) + 4) % 4;
int newx = cur.i + dx[newdir];
int newy = cur.j + dy[newdir];
if(ins(newx , newy) && c[newx][newy] != 'x')
{
if(minz(dp[newx][newy][cur.l][cur.r][newdir][1] , dp[cur.i][cur.j][cur.l][cur.r][cur.dir][cur.t] + 1))
pq.push(State(dp[newx][newy][cur.l][cur.r][newdir][1] , newx , newy , cur.l , cur.r , newdir , 1));
}
FOR(newl , 0 , cur.l - 1)
{
int opt = oo;
FOR(dir , 0 , 3)
minz(opt , dp[cur.i][cur.j][newl][cur.l - 1][dir][0]);
FOR(dir , 0 , 3)
{
if(minz(dp[cur.i][cur.j][newl][cur.r][dir][0] , opt + dp[cur.i][cur.j][cur.l][cur.r][cur.dir][cur.t]))
pq.push(State(dp[cur.i][cur.j][newl][cur.r][dir][0] , cur.i , cur.j , newl , cur.r , dir , 0));
}
}
FOR(newr , cur.r + 1 , n - 1)
{
int opt = oo;
FOR(dir , 0 , 3)
minz(opt , dp[cur.i][cur.j][cur.r + 1][newr][dir][0]);
FOR(dir , 0 , 3)
{
if(minz(dp[cur.i][cur.j][cur.l][newr][dir][0] , dp[cur.i][cur.j][cur.l][cur.r][cur.dir][cur.t] + opt))
pq.push(State(dp[cur.i][cur.j][cur.l][newr][dir][0] , cur.i , cur.j , cur.l , newr , dir , 0));
}
}
}
}
int ans = oo;
FOR(i , 0 , h - 1)
{
FOR(j , 0 , w - 1)
{
FOR(dir , 0 , 3)
{
FOR(t , 0 , 1)
{
minz(ans , dp[i][j][0][n - 1][dir][t]);
}
}
}
}
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();
}
/*
*/
