Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

char getc()

{

	register char c = getchar();

	while(c != '0' && c != '1' && c != '*')c = getchar();

	return c;

}

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 mx[8] = {-2,-1,1,2,-2,-1,1,2};

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

int h()

{

	int res = 0;

	for(int i = 1;i <= 5;++i)

		for(int j = 1;j <= 5;++j)

			if(map[i][j] != check[i][j])

				++res;

	return res;

}

int ans;

void dfs(int x,int y,int cur,int last)

{

	int rem = h();

	if(cur + rem > 16)return;

	if(cur >= ans)return;

	if(rem == 0)

	{

		ans = cur;

		return;

	}

	for(int i = 0;i < 8;++i)

	{

		if(i + last == 7)continue;

		if(1 <= x + mx[i] && x + mx[i] <= 5 && 1 <= y + my[i] && y + my[i] <= 5)

		{

			swap(map[x][y],map[x + mx[i]][y + my[i]]);

			dfs(x + mx[i],y + my[i],cur + 1,i);

			swap(map[x][y],map[x + mx[i]][y + my[i]]);

		}

	}

	return;

}

void work()

{

	for(int i = 1;i <= 5;++i)

		for(int j = 1;j <= 5;++j)

			map[i][j] = getc();

	int px,py;

	for(int i = 1;i <= 5;++i)

		for(int j = 1;j <= 5;++j)

			if(map[i][j] == '*')

				{px = i;py = j;}

	ans = 25;

	dfs(px,py,0,10);

	printf("%d\n",(ans == 25 ? -1 : ans));

	return;

}

int main()

{

	int testcases;

	scanf("%d",&testcases);

	while(testcases--)work();

	return 0;

}