IDA*:

#include<iostream>
using namespace std;
const int MAXN = 7;
int m[MAXN][MAXN];
const int goal[MAXN][MAXN]={
	{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}
};
const int dx[]={0,1,1,-1,-1,2,2,-2,-2};
const int dy[]={0,2,-2,2,-2,1,-1,1,-1};
int maxdep;
bool flag;
int check()
{
	int cnt = 0;
	for(int i=1;i<=5;i++)
		for(int j=1;j<=5;j++)
			if(m[i][j]!=goal[i][j])
				cnt++;
	return cnt;
}
void dfs(int dep,int x,int y)
{
	if(dep == maxdep)
	{
		if(!check())flag = true;
		return;
	}
	for(int i=1;i<=8;i++)
	{
		int nx = x + dx[i];
		int ny = y + dy[i];
		if(nx < 1 || nx > 5 || ny < 1 || ny > 5)continue;
		int h = check();
		if(dep + h <= maxdep)
		{
			swap(m[x][y],m[nx][ny]);
			dfs(dep+1,nx,ny);
			swap(m[x][y],m[nx][ny]);
		}
	
		
	}
}
void solve()
{
	int x,y;
	flag = false;
	for(int i=1;i<=5;i++)
		for(int j=1;j<=5;j++)
		{
			char c;
			cin >> c;
			if(c == '*')
			{				
				m[i][j] = 2;
				x = i,y = j;
			}
			else
				m[i][j] = (c - '0');
				
		}
	for(maxdep=1;maxdep<=15;maxdep++)
	{
		dfs(0,x,y);
		if(flag)
		{
			cout << maxdep << endl;
			return ;
		}
	}
	cout << -1 << endl;
	
	
	
}
int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		solve();
	}
	return 0;
}