dfs+A*优化。
A*是人工智能算法，属于启发式搜索的一部分。第一次知道这个名词是在写虫食算的时候闵神说这个用A*搞跑的比谁都快..但是当时搜了很多资料想搞清楚这个东西，但是当时还是太拿衣服，所以拖到了联赛前补一补。
其实A*算法应该是算用于剪枝吧（我什么不懂说错了求不喷QAQ），优化每次扩展搜索树的顺序已达到最理想的效果。在寻路方面有个视频可以很好的反映出A*的优越性：
A*在这里的关键就是如何设置估价函数，因为末状态已知，所以设有多少个点和答案不同为估价函数。
//BZOJ 1085
//by Cydiater
//2016.10.11
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <ctime>
#include <cmath>
#include <cstdlib>
#include <iomanip>
#include <cstdio>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
const int MAXN=1e6+5;
const int oo=0x3f3f3f3f;
const int N=5;
const int dx[8]={1,1,-1,-1,2,2,-2,-2};
const int dy[8]={2,-2,2,-2,1,-1,1,-1};
inline int read(){
char ch=getchar();int x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int aim[6][6]={
{0,0,0,0,0,0},
{0,1,1,1,1,1},
{0,0,1,1,1,1},
{0,0,0,2,1,1},
{0,0,0,0,0,1},
{0,0,0,0,0,0}
};
int a[6][6],b[6][6],T,stx,sty;
bool OK=0;
namespace solution{
void print(){
up(i,1,5){
up(j,1,5)printf("%d ",a[i][j]);
printf("\n");
}
puts("");
}
void init(){
up(i,1,N){
scanf("\n");
up(j,1,N){
char ch;scanf("%c",&ch);
if(ch=='1')a[i][j]=1;
if(ch=='0')a[i][j]=0;
if(ch=='*'){
a[i][j]=2;
stx=i;sty=j;
}
}
}
memcpy(b,a,sizeof(a));
}
bool check(int now,int lim){
int cnt=0;
up(i,1,5)up(j,1,5)if(a[i][j]!=aim[i][j])cnt++;
if(cnt+now>lim)return 0;
return 1;
}
bool judge(){
up(i,1,5)up(j,1,5)if(aim[i][j]!=a[i][j])return 0;
return 1;
}
void dfs(int x,int y,int dep,int depth){
//if(depth==7)print();
if(dep==depth)if(judge()){
OK=1;return;
}
if(OK)return;
up(i,0,15){
int tx=x+dx[i],ty=y+dy[i];
if(tx>5||tx<1||ty>5||ty<1)continue;
swap(a[x][y],a[tx][ty]);
if(check(dep,depth))dfs(tx,ty,dep+1,depth);
swap(a[x][y],a[tx][ty]);
}
}
void slove(){
OK=0;
up(dep,1,15){
memcpy(a,b,sizeof(b));
dfs(stx,sty,0,dep);
if(OK){
cout<<dep<<endl;
break;
}
}
if(!OK)puts("-1");
}
}
int main(){
//freopen("input.in","r",stdin);
//freopen("out.out","w",stdout);
using namespace solution;
T=read();
while(T--){
init();
slove();
}
return 0;
}