题目描述

在一个$\red{5\times 5}$的棋盘上有$\red{12}$个白色的骑士和$\red{12}$个黑色的骑士，且有一个空位。

在任何时候一个骑士都能按照骑士的走法（它可以走到和它横坐标相差为$\red 1$，纵坐标相差为$\red 2$或者横坐标相差为$\red 2$，纵坐标相差为$\red 1$的格子）移动到空位上。

给定一个初始的棋盘，怎样才能经过移动变成如下目标棋盘：为了体现出骑士精神，他们必须以最少的步数完成任务。

输入格式

第一行有一个正整数$\red{T(T<=10)}$，表示一共有$\red T$组数据。

接下来有$\red T$个$\red{5\times 5}$的矩阵，$\red 0$表示白色骑士，$\red 1$表示黑色骑士，$\red *$表示空位。

两组数据之间没有空行。

输出格式

每组数据输出占一行。

如果能在$\red {15}$步以内（包括$\red{15}$步）到达目标状态，则输出步数，否则输出$\red{-1}$。

样例

输入样例

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

输出样例

7
-1