本地对拍无误，但是一到洛谷上就出错。已加注释，请放心食用。另外蒟蒻第一次写IDA*，码风较丑，请大佬见谅qwq

代码虽然看着长，但是有很多都是快读/快输，请忽略该部分。如果让您感到不适请原谅QAQ

#include<bits/stdc++.h>
#define ll long long
#define INF 0x7f7f7f7f
#define lowbit(x) x & -x
#define re register

using namespace std;

inline int read()//快读
{
	bool k=0;
	int w=0;
	char c=getchar();
	while ((c<'0'||c>'9')&&c!='-')
		c=getchar();
	if (c=='-')
	{
		k=1;
		c=getchar();
 	}
	while (c>='0'&&c<='9')
	{
		w=(w<<3)+(w<<1)+c-'0';
		c=getchar();
	}
	return k?-w:w;
}

void print(int p)//快输
{
	if (p<0)
	{
		putchar('-');
		p=-p;
	}
	if (p>9)
		print(p/10);
	putchar(p%10+'0');
	return ;
}

void Print(int p,char c)//快输
{
	print(p);
	putchar(c);
	return ;
}

int n;//棋盘总数
int mp[6][6];//棋盘
int sx,sy;//初始位置
int ans;//答案
string s;
bool f;//记录

int nx[8]={-1,-1,1,1,2,2,-2,-2};
int ny[8]={2,-2,-2,2,1,-1,1,-1};

int g[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,1}};//目标状态

inline int bst()//查找不同个数
{
	int cnt=0;
	for (int i=1;i<=5;i++)
		for (int j=1;j<=5;j++)
			if (mp[i][j]!=g[i][j])
				cnt++;
	return ((cnt==0)?0:cnt-1);//如果大于0则减1
    //return cnt;
}

void dfs(int step,int x,int y,int maxn,int prex,int prey)
{
	if (step==maxn)//如果步数等于最大值
	{
		if (bst()==0)//如果已经符合条件
		{
			f=1;//记录
			ans=step;//更新答案
		}
		return ;//返回
	}
	if (step+bst()>maxn+1)//如果当前步数加理想步数还比最大值大2
		return ;//返回
	int xx;
	int yy;
	int t;
	for (int i=0;i<8;i++)
	{
		xx=x+nx[i];//计算下一步的位置
		yy=y+ny[i];
		if ((xx==prex&&yy==prey)||xx<1||xx>5||yy<1||yy>5)//如果走回了上一步或是超界
			continue;//重新计算
		t=mp[x][y];//交换两处的值
		mp[x][y]=mp[xx][yy];
		mp[xx][yy]=t;
		if (step+bst()<=maxn+1)//如果当前步数加理想步数比最大值小1
		{
			dfs(step+1,xx,yy,maxn,x,y);//进行深搜
			if (f)//如果已经找到
				return ;//返回
		}
		mp[xx][yy]=mp[x][y];//换回来
		mp[x][y]=t;
	}
	return ;
}

signed main()
{
	
	n=read();
	while (n--)
	{
		f=0;//初始化
		for (int i=1;i<=5;i++)
		{
			cin >>s;
			for (int j=0;j<5;j++)
			{
				mp[i][j+1]=((s[j]=='*')?(2):(s[j]-'0'));//初始化棋盘
				if (s[j]=='*')//记录空格位置
				{
					sx=i;
					sy=j+1;
				}
			}
		}
		for (int i=bst();i<=15;i++)//最小从理想步数开始，一直到15
		{
			dfs(0,sx,sy,i,sx,sy);
			if (f)//如果找到了答案
			{
				Print(ans,'\n');//输出答案
				break;//跳出循环
			}
		}
		if (!f)//如果没有找到
			puts("-1");//输出-1
	}
	return 0;
}