#include <iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<vector> #include<string> #include<map> #include<queue> using namespace std; #define maxn 100005 int h[15]; struct node { int x,dis; }t,f; char st[10][10][10]; char ed[10][10][10]; char tst[10][10]; char tzf[10][10]; vector<int> fin[15]; int edge[10][4]; struct *** { int to,turn; ***(int a,int b){to=a;turn=b;} ***(){} }v[20]; int top; bool use[15]; bool FINAL[1111111]; void cal(int now) { memcpy(tst,st[now],sizeof(st[now])); for(int d=0;d<4;d++) { if(memcmp(tst,ed[now],sizeof(tst))==0) {fin[now].push_back(d);} for(int i=0;i<8;i++) { for(int j=0;j<8;j++) { tzf[j][8-i-1]=tst[i][j]; } } memcpy(tst,tzf,sizeof(tzf)); } } bool vis[1111111]; int Turn[9]; bool isok(int x,int y) { return x>=0&&x<3&&y>=0&&y<3; } int dx[]={0,-1,0,1}; int dy[]={-1,0,1,0}; int op(int a,int b) { if(a-b>=0) return a-b; return 3-(b-a-1); } bool can(int a,int b,int d) { if(d==0&&edge[a][op(0,Turn[a])]&&edge[b][op(2,Turn[b])]) return true; if(d==1&&edge[a][op(1,Turn[a])]&&edge[b][op(3,Turn[b])]) return true; if(d==2&&edge[a][op(2,Turn[a])]&&edge[b][op(0,Turn[b])]) return true; if(d==3&&edge[a][op(3,Turn[a])]&&edge[b][op(1,Turn[b])]) return true; return false; } void dfs(int x,int y,int flag) { v[top++]=***(x*3+y,flag); for(int d=0;d<4;d++) { int nx=x+dx[d]; int ny=y+dy[d]; if(isok(nx,ny)&&use[nx*3+ny]==0&&can(x*3+y,nx*3+ny,d)) { use[nx*3+ny]=true; dfs(nx,ny,-flag); } } } void bfs() { memset(Turn,0,sizeof(Turn)); memset(vis,0,sizeof(vis)); vis[0]=true; queue<node> q; f.dis=0;f.x=0; q.push(f); while(!q.empty()) { f=q.front();q.pop(); for(int i=0;i<9;i++) Turn[i]=(f.x/h[9-i-1])%4; for(int d=0;d<9;d++) { t=f; t.dis++; top=0; memset(use,0,sizeof(use)); use[d]=1; dfs(d/3,d%3,1); int tmp=t.x; for(int i=0;i<top;i++) { int g=(tmp/h[9-v[i].to-1])%4; t.x-=g*h[9-v[i].to-1]; g+=v[i].turn; if(g==4) g=0; else if(g==-1) g=3; t.x+=g*h[9-v[i].to-1]; } if(FINAL[t.x]) {printf("%dn",t.dis);return;} if(vis[t.x]==false) { vis[t.x]=true; q.push(t); } } } puts("-1"); } int tot; void dfs2(int now,int s) { if(now==9) { FINAL[s]=true; tot++; return; } for(int i=0;i<fin[now].size();i++) { dfs2(now+1,s+fin[now][i]*h[9-now-1]); } } int main() { h[0]=1; for(int i=1;i<=10;i++) { h[i]=h[i-1]*4; } int cas; scanf("%d",&cas); while(cas--) { memset(FINAL,0,sizeof(FINAL)); for(int i=0;i<10;i++) fin[i].clear(); for(int t=0;t<=6;t+=3) { for(int i=0;i<8;i++) { for(int k=t;k<t+3;k++) {scanf("%s",st[k][i]); } } } for(int t=0;t<=6;t+=3) { for(int i=0;i<8;i++) { for(int k=t;k<t+3;k++) {scanf("%s",ed[k][i]); } } } for(int i=0;i<9;i++) { for(int j=0;j<4;j++) { scanf("%d",&edge[i][j]); } } for(int k=0;k<9;k++) cal(k); tot=0; dfs2(0,0); if(tot==0) puts("-1"); else if(FINAL[0]) puts("0"); else bfs(); } return 0; }
