C++ :

/*
date : 2019-07-27 12:37:13
problem ID : 
problem WEB :
*/
#include <iostream>
#include <string.h>
#include <cstdio>
#include <algorithm>
using namespace std;
#define LL long long
int ans = -1 , nowa , nowb , d;
int p[8] = {-2 , -2 , -1 , -1 , 1 , 1 , 2 , 2};
int q[8] = {-1 , 1 , -2 , 2 , -2 , 2 , -1 , 1};
int a[6][6] , goal[6][6]={{0,0,0,0,0,0},
				        {0,1,1,1,1,1},
				        {0,0,1,1,1,1},
				        {0,0,0,-1,1,1},
				        {0,0,0,0,0,1},
				        {0,0,0,0,0,0}};
void putin()
{
	char x;
	for (int i = 1 ; i < 6 ; i++)
		for (int j = 1 ; j < 6 ; j++)
		{
			cin >> x;
			if (x == '*')
			{
				a[i][j] = -1;
				nowa = i;
				nowb = j;
			}
			else
				a[i][j] = x - '0';
		}
}

int flag()
{
	int ans = 0;
	for (int i = 1 ; i < 6 ; i++)
		for (int j = 1 ; j < 6 ; j++)
			if (a[i][j] != goal[i][j])
				ans++;
	return ans;
}

bool dfs(int x , int y , int step)
{
	if (step > d)
		return false;
	int z = flag();
	if (z == 0)
	{
		ans = step;
		return true;
	}
	if (z + step > d + 1)
		return false;
	int xx = x , yy = y;
	for (int i = 0 ; i < 8 ; i++)
	{
		xx = x + p[i];
		yy = y + q[i];
		if (xx > 0 && xx < 6 && yy > 0 && yy < 6)
		{
			swap(a[x][y] , a[xx][yy]);
			if (dfs(xx , yy , step + 1))
				return 1;
			swap(a[x][y] , a[xx][yy]);
		}
	}
	return 0;
}

int main()
{
	int n;
	cin >> n;
	for (int i = 1 ; i <= n ; i++)
	{
		bool fl = 0;
		putin();
		ans = -1;
		int sum = flag();
		for (d = sum ; d <= 15 ; d++)
		{
			if (dfs(nowa , nowb , 0))
			{
				cout << ans << endl;
				fl = 1;
				break;
			}
		}
		if (!fl)
			cout << -1 << endl;
	}
	return 0;
}

#include<cstdio>
#include<iostream> 
#include<cstring>
#define INF 536870912
using namespace std;
char map[6][6];
char check[6][6]={
	'0','0','0','0','0','0',
	'0','1','1','1','1','1',
	'0','0','1','1','1','1',
	'0','0','0','*','1','1',
	'0','0','0','0','0','1',
	'0','0','0','0','0','0',
};
int xm[9]={0,-2,-2,-1,-1,1,1,2,2};
int ym[9]={0,-1,1,-2,2,-2,2,-1,1};
int ans;
inline void swap(char &p1,char &p2){
	char mid=p1; p1=p2; p2=mid;
}
inline int dif(){
	int ret=0;
	for(int i=1;i<=5;i++){
		for(int j=1;j<=5;j++){
			if(map[i][j]!=check[i][j]) ret++;
		}
	}
	return ret;
}
inline void dfs(int x,int y,int d,int f){
	int l=dif();
	if(d+l>16) return ;
	if(d>=ans) return ;
	if(l==0){
		ans=d; return ;
	}
	for(int i=1;i<=8;i++){
		if((x+xm[i]<1)||(x+xm[i]>5)) continue;
		if((y+ym[i]<1)||(y+ym[i]>5)) continue;
		if(f+i!=9){
			swap(map[y+ym[i]][x+xm[i]],map[y][x]);
			dfs(x+xm[i],y+ym[i],d+1,i);
			swap(map[y+ym[i]][x+xm[i]],map[y][x]);
		}
	}
}
inline void init(){
	int x,y;
	for(int i=1;i<=5;i++) cin>>map[i]+1;
	for(int i=1;i<=5;i++){
		for(int j=1;j<=5;j++){
			if(map[i][j]=='*') { x=j; y=i; }
		}
	}
	ans=25;
	dfs(x,y,0,0);
	printf("%d\n",ans==25?-1:ans);
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--)init();
	return 0;
}

/*********************************
备注：
*********************************/
#include<map>
#include<list>
#include<stack>
#include<queue>
#include<cmath>
#include<queue>
#include<stack>
#include<deque>
#include<math.h>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iomanip>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
#define in int
#define ch char
#define lo long
#define fl float
#define sh short
#define ld long double
#define lli long long int
#define db double
#define str string
#define ll long long
const int N =1e6+10;
const int INF =0x3f3f3f3f;
int read()
{
    int f=1,x=0;
    char ss=getchar();
    while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
    while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
    return f*x;
}

int n;
int ans[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 nxtx[]={1,1,2,2,-2,-2,-1,-1};
int nxty[]={2,-2,1,-1,1,-1,2,-2};
int a[10][10],k;
int judge;

int check()
{
    for(int i=1;i<=5;++i)
    for(int j=1;j<=5;++j)
    if(ans[i][j]!=a[i][j])return 0;
    return 1;
}

int test(int step)
{
    int cnt=0;
    for(int i=1;i<=5;++i)
    for(int j=1;j<=5;++j)
    if(ans[i][j]!=a[i][j]){ if(++cnt+step>k) return 0;}
    return 1;
}

void A_star(int step,int x,int y,int pre)
{
    if(step==k){ if(check())judge=1; return;}
    if(judge) return;
    for(int i=0;i<8;++i)
    {
        int nx=x+nxtx[i],ny=y+nxty[i];
        if(nx<1||nx>5||ny<1||ny>5||i+pre==7) continue;
        swap(a[x][y],a[nx][ny]);
        if(test(step)&&!judge) A_star(step+1,nx,ny,i);
        swap(a[x][y],a[nx][ny]);
    }
}

int main()
{
    n=read();
    while(n--)
    {
        int x,y; judge=0;
        for(int i=1;i<=5;++i)
        {
            char ss[7]; scanf("%s",&ss);
            for(int j=0;j<5;++j)
            if(ss[j]=='*') a[i][j+1]=2,x=i,y=j+1;
            else a[i][j+1]=ss[j]-'0';
        }
        for(k=1;k<=15;++k)
        {
            A_star(0,x,y,-1);
            if(judge) { printf("%d\n",k); break;}
        }
        if(!judge)cout<<"-1"<<endl;
    }
    return 0;
}