[SCOI2005]骑士精神

题目描述

![](https://cdn.luogu.com.cn/upload/pic/1389.png)

输入输出格式

输入格式


第一行有一个正整数T(T<=10),表示一共有N组数据。接下来有T个5×5的矩阵,0表示白色骑士,1表示黑色骑士,\*表示空位。两组数据之间没有空行。

输出格式


对于每组数据都输出一行。如果能在15步以内(包括15步)到达目标状态,则输出步数,否则输出-1。

输入输出样例

输入样例 #1

2
10110
01*11
10111
01001
00000
01011
110*1
01110
01010
00100

输出样例 #1

7
-1

说明

![](https://cdn.luogu.com.cn/upload/pic/1390.png)