/*
* @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 , L , R , sz;
char c[WH][WH];
ii list[WH * WH];
int dp[WH * WH][N][N] , q[WH * WH];
vector <int> g[WH * WH];
int dx[4] = {0 , -1 , 0 , 1};
int dy[4] = {-1 , 0 , 1 , 0};
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;
// opt[i][l][l] = l;
}
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;
L = 1 , R = 0;
q[++R] = id(i , j);
while(R - L + 1 > 0)
{
int u = q[L++];
for(int &v : g[u])
if(minz(dp[v][c[i][j] - '0'][c[i][j] - '0'] , dp[u][c[i][j] - '0'][c[i][j] - '0'] + 1))
q[++R] = v;
}
}
}
}
FOR(r , 1 , n)
{
FORD(l , r - 1 , 1)
{
FOR(i , 1 , h)
{
FOR(j , 1 , w)
{
FOR(mid , l , r - 1)
minz(dp[id(i , j)][l][r] , dp[id(i , j)][l][mid] + dp[id(i , j)][mid + 1][r]);
// {
// opt[id(i , j)][l][r] = mid;
// }
}
}
sz = 0;
FOR(i , 1 , h)
{
FOR(j , 1 , w)
{
if(dp[id(i , j)][l][r] < oo)
{
list[++sz] = ii(dp[id(i , j)][l][r] , id(i , j));
}
}
}
sort(list + 1 , list + 1 + sz);
FOR(i , 1 , sz)
{
if(list[i].fi > dp[list[i].se][l][r])
continue;
L = 1 , R = 0;
q[++R] = list[i].se;
while(R - L + 1 > 0)
{
int u = q[L++];
for(int &v : g[u])
if(minz(dp[v][l][r] , dp[u][l][r] + 1))
q[++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();
}
/*
*/
