1 #include <bits/stdc++.h>
2 #define _for(i,a,b) for(int i = (a);i < b;i ++)
3 #define _rep(i,a,b) for(int i = (a);i > b;i --)
4 #define INF 0x3f3f3f3f
5 #define MOD 1000000007
6 #define maxn 10
7 typedef long long ll;
8 using namespace std;
9
10 inline ll read()
11 {
12 ll ans = 0;
13 char ch = getchar(), last = ' ';
14 while(!isdigit(ch)) last = ch, ch = getchar();
15 while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
16 if(last == '-') ans = -ans;
17 return ans;
18 }
19 inline void write(ll x)
20 {
21 if(x < 0) x = -x, putchar('-');
22 if(x >= 10) write(x / 10);
23 putchar(x % 10 + '0');
24 }
25 int T;
26 int mp[maxn][maxn];
27 int bx,by;
28 const int dx[]={1,1,-1,-1,2,2,-2,-2};
29 const int dy[]={2,-2,2,-2,1,-1,1,-1};
30 const int target[maxn][maxn] =
31 {
32 {0,0,0,0,0,0},
33 {0,2,2,2,2,2},
34 {0,1,2,2,2,2},
35 {0,1,1,0,2,2},
36 {0,1,1,1,1,2},
37 {0,1,1,1,1,1}
38 };
39
40 int g()
41 {
42 int rnt = 0;
43 _for(i,1,6)
44 _for(j,1,6)
45 {
46 if(!mp[i][j]) continue;
47 if(target[i][j] != mp[i][j])
48 rnt ++;
49 }
50 return rnt;
51 }
52 bool valid(int x,int y)
53 { return x>=1&&x<6&&y>=1&&y<6;}
54 bool dfs(int maxstep,int step)
55 {
56 int gg = g();
57 if(!gg)
58 return true;
59 if(step+gg>maxstep)
60 return false;
61 _for(i,0,8)
62 {
63 int nx = bx+dx[i];
64 int ny = by+dy[i];
65 if(valid(nx,ny))
66 {
67 int tx = bx,ty = by;
68 swap(mp[bx][by],mp[nx][ny]);
69 bx = nx,by = ny;
70 if(dfs(maxstep,step+1)) return true;
71 bx = tx,by = ty;
72 swap(mp[nx][ny],mp[bx][by]);
73 }
74 }
75 return false;
76 }
77 int main()
78 {
79 T = read();
80 while(T--)
81 {
82 char tmp;
83 _for(i,1,6)
84 _for(j,1,6)
85 {
86 scanf(" %c",&tmp);
87 if(tmp=='*')
88 mp[i][j] = 0,bx = i,by = j;
89 else
90 mp[i][j] = tmp-'0'+1;
91 }
92 int flag = 0;
93
94 _for(maxstep,0,16)
95 {
96 if(dfs(maxstep,0))
97 { flag = 1,printf("%d\n",maxstep);break;}
98 }
99 if(!flag)
100 printf("%d\n",-1);
101 }
102 return 0;
103 }
知识兔