#include <iostream>#include <string.h>#include <stdio.h>#include <algorithm>using namespace std;int n,m;int dir[4][2]={0,1,1,0,0,-1,-1,0};char str[1010];int bo[22][22];int vis[22][22];int check(int x,int y){ if(x<0||y<0||x>=n||y>=m||vis[x][y]) return 0; return 1;}int sum=0,limit;int ans[1010];void dfs(int x,int y,int d,int num,int po){ vis[x][y]=1; int xx=x+dir[d][0],yy=y+dir[d][1]; limit--; if(po==4) { ans[sum++]=num*2+bo[x][y]; po=0; if(limit<=0) return; if(check(xx,yy)) { dfs(xx,yy,d,0,0); } else { d=(d+1)%4; xx=x+dir[d][0],yy=y+dir[d][1]; dfs(xx,yy,d,0,0); } } else { if(check(xx,yy)) { dfs(xx,yy,d,num*2+bo[x][y],po+1); } else { d=(d+1)%4; xx=x+dir[d][0],yy=y+dir[d][1]; dfs(xx,yy,d,num*2+bo[x][y],po+1); } }}int main(){ int ncase,time=0; scanf("%d",&ncase); while(ncase--) { scanf("%d%d",&n,&m); printf("%d ",++time); scanf("%s",str); sum=0; int len=n*m,i,j; limit=len/5*5; for(i=0;i<n;i++) { for(j=0;j<m;j++) bo[i][j]=str[i*m+j]-'0'; } memset(vis,0,sizeof(vis)); dfs(0,0,0,0,0); while(ans[sum-1]==0)sum--; for(i=0;i<sum;i++) { if(ans[i]==0) printf(" "); else printf("%c",ans[i]-1+'A'); } printf("n"); } return 0;}
