P10449 Puzzling Switches.

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.

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 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`.

The Constraints satisfy $0 < n \le 500$. Translated by ChatGPT 5