[SCOI2005]骑士精神

题目描述

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

输入输出格式

输入格式


第一行有一个正整数 $T$($T \le 10$),表示一共有 $T$ 组数据。 接下来有 $T$ 个 $5 \times 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)