Problem Description

Have you ever played the “Turn Off the Lights” game?

There are $25$ lights arranged in a $5 \times 5$ square.

Each light has a switch, and the player can change its state.

In each move, the player can change the state of one light.

Changing the state of one light causes a chain reaction: the lights adjacent to it in the up, down, left, and right directions will also change their states accordingly.

We use the digit $1$ to represent a light that is on, and the digit $0$ to represent a light that is off.

For example, the following state:

10111
01101
10111
10000
11011

After changing the state of the top-left light, it becomes:

01111
11101
10111
10000
11011

Then, after changing the state of the center light, it becomes:

01111
11001
11001
10100
11011

Given some initial game states, write a program to determine whether the player can make all the lights turn on within $6$ moves.

Input Format

The first line contains a positive integer $n$, meaning there are $n$ initial game states to solve in the input testdata.

The following lines are divided into $n$ groups. Each group contains $5$ lines, and each line contains $5$ characters.

Each group describes an initial state of the game.

Groups are separated by a blank line.

Output Format

Output a total of $n$ lines. Each line contains an integer less than or equal to $6$, which represents the minimum number of moves needed to turn on all the lights for the corresponding game state in the input.

If it is impossible to turn on all the lights within $6$ moves for a certain initial state, output -1.

3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111

3
2
-1

Hint

The Constraints satisfy $0 < n \le 500$.

Translated by ChatGPT 5