Problem Description

On a $5 \times 5$ board there are $12$ white knights and $12$ black knights, plus one empty cell. At any time, a knight may move into the empty cell following the knight's move (it can move to a cell where the x-coordinate differs by $1$ and the y-coordinate differs by $2$, or the x-coordinate differs by $2$ and the y-coordinate differs by $1$).

Given an initial board, how can it be transformed, via moves, into the following target board:

To embody the "knight's spirit", they must finish in the minimal number of moves.

Input Format

The first line contains a positive integer $T$ ($T \le 10$), indicating there are $T$ test cases.

Then follow $T$ matrices of size $5 \times 5$, where 0 denotes a white knight, 1 denotes a black knight, and * denotes the empty cell. There is no blank line between two test cases.

Output Format

For each test case, output one line. If the target state can be reached within $15$ moves (inclusive), output the minimal number of moves; otherwise, output -1.

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

7
-1

Hint

Translated by ChatGPT 5