IDA*

#include<bits/stdc++.h>
using namespace std;
char ch;
int a[10][10];
int d1[]={1,1,2,2,-1,-1,-2,-2};
int d2[]={2,-2,1,-1,2,-2,1,-1};
int s[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 f()
{
	int cnt=0;
	for(int i(1);i<=5;++i)
		for(int j(1);j<=5;++j)
		if(a[i][j]!=s[i][j])
		cnt++;
	return cnt-1;
}
bool dfs(int x,int y,int step,int maxstep)
{
	if(step==maxstep&&f()==-1)
	return 1;
	bool ans=0;
	for(int i(0);i<=7;++i)
	{
		int nowx=x+d1[i];
		int nowy=y+d2[i];
		if(nowx<1||nowx>5||nowy<1||nowy>5)
		continue;
		swap(a[x][y],a[nowx][nowy]);
		if(step+f()<=maxstep)
			ans=ans|dfs(nowx,nowy,step+1,maxstep);
		swap(a[x][y],a[nowx][nowy]);
		if(ans)
		return 1;
	}
	return 0;
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int x,y;
		for(int i(1);i<=5;++i)
			for(int j(1);j<=5;++j)
				{
					cin>>ch;
					if(ch=='*')
					x=i,y=j,a[i][j]=2;
					else
					a[i][j]=ch-'0';
				}
		if(f()>15)
		printf("-1\n");
		else
		{
			bool op=0;
//			printf("%d\n",f());
			for(int i(f());i<=15;++i)
				if(dfs(x,y,0,i)!=0)
				{
					op=1;
					printf("%d\n",i);
					break;
				}
			if(!op)
			printf("-1\n");
		}
	}
}