Migrated from Lutece 2649 国际象棋

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给出一个 $5\times 5$ 的棋盘，上面共有 $12$ 个白色骑士，$12$ 个黑色骑士和一个空格。你需要按国际象棋的规则（骑士可以移动到纵坐标相差 $1$ 且横坐标相差 $2$，或者纵坐标相差 $2$ 且横坐标相差 $1$ 的位置。）移动骑士。请你输出讲所有骑士安放到以下位置的最小步数。

用 $0$ 表示白色骑士，$1$ 表示黑色骑士，$*$ 表示空格，那么你需要将棋盘摆放为

11111
01111
00*11
00001
00000

Input

第一行一个数 $t$，表示数据组数。 接下来 $5t$ 行，每 $5$ 行表示一个棋盘。

Output

$t$ 行，每行一个整数，表示最小步数。如果这个最小步数大于 $15$，输出 $-1$。

Samples

2
1*111
01111
00111
00001
00000
01011
110*1
01110
01010
00100

1
-1

Constraints

$1 \le t \le 10$

Resources

2021 UESTC ICPC Training for String and Search Algorithm