On a $5 \times 5$ chessboard, there are 12 white knights, 12 black knights, and one empty space. At any time, a knight can move into the empty space according to the standard knight's move (it can move to a square where the difference in the x-coordinate is 1 and the difference in the y-coordinate is 2, or the difference in the x-coordinate is 2 and the difference in the y-coordinate is 1).

Given an initial board configuration, how can it be transformed into the following target board through a sequence of moves:

To embody the spirit of the knight, they must complete the task in the minimum number of steps.

Input

The first line contains a positive integer $T$ ($T \le 10$), representing the total number of test cases. This is followed by $T$ $5 \times 5$ matrices, where $0$ represents a white knight, $1$ represents a black knight, and $*$ represents the empty space. There are no empty lines between data sets.

Output

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

Examples

Input 1

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

Output 1

7
-1

Note

The initial configuration of the second data set in the example corresponds to the following figure: