#include using namespace std; using ll =long long; void solve(){ ll H,W,M; cin>>H>>W>>M; vector B(H); ll SY,SX,GY,GX; for(int i=0;i>B[i]; for(int j=0;j>> DP(H,vector>(W,vector(10,1e18))); DP[SY][SX][0]=0; queue> Q; Q.push({SY,SX,0}); vector nd={0,1,0,-1,0}; while(!Q.empty()){ auto [y,x,k]=Q.front(); Q.pop(); for(int d=0;d<4;d++){ ll ny=y+nd[d]; ll nx=x+nd[d+1]; ll nk=k; if(ny<0||nx<0||ny>=H||nx>=W)continue; if(B[ny][nx]=='#')continue; if('a'<=B[ny][nx]&&B[ny][nx]<='z'){ if(B[ny][nx]-'a'+1!=k)continue; } if('1'<=B[ny][nx]&&B[ny][nx]<='9'){ nk=B[ny][nx]-'0'; } if(DP[ny][nx][nk]>DP[y][x][k]+1){ DP[ny][nx][nk]=DP[y][x][k]+1; Q.push({ny,nx,nk}); } } } ll an=1e18; for(int i=0;i<10;i++)an=min(an,DP[GY][GX][i]); cout<<(an<1e17?an:-1)<>T; while(T--)solve(); }