Extended Lights Out

Lights Out® is a puzzle in which the goal is to turn every lit light off. In this extended version the board has 5 rows of 6 buttons each, that is, 5 rows and 6 columns. (The original puzzle has 5 rows of 5 buttons each.) Each button carries a light. Pressing a button reverses the state of that button's light and of each of its (up to four) neighbours directly above, below, to the left, and to the right. Reversing means an on light turns off and an off light turns on. A button in a corner therefore changes 3 lights, a button on an edge changes 4 lights, and any other button changes 5 lights. For example, if the buttons marked X in the left image below are pressed, the display changes to the right image.

The aim of the game is, starting from any initial pattern of lit buttons, to press buttons until every light is off. Because pressing adjacent buttons interacts, the action of one button can undo the effect of another. For instance, pressing the button in row 2, column 3 and the button in row 2, column 5 both reverse the light in row 2, column 4, so that light's state is ultimately unchanged.

Notes:

1. The order in which the buttons are pressed does not matter.
2. Pressing a button a second time exactly cancels the first press, so no button ever needs to be pressed more than once. Thus each button is either pressed (1) or not pressed (0).
3. All lights in the first row can be turned off by pressing the corresponding buttons in the second row. Repeating this process row by row turns off all lights in the first four rows. Similarly, by pressing buttons in columns 2, 3, …, all lights in the first five columns can be turned off.

Write a program that determines which buttons must be pressed to solve each puzzle.

The first line of input contains a positive integer $n$, the number of puzzles that follow. Each puzzle is given on five lines, and each line contains six values (0 or 1) separated by one or more spaces. A 0 means that light is initially off, and a 1 means that light is initially on.

For each puzzle, first output a line containing the string PUZZLE #m, where $m$ is the index of the puzzle in the input (starting from 1). After that line, print a 5-by-6 grid in the same format as the input: a 1 marks a button that must be pressed to solve the puzzle, and a 0 marks a button that is not pressed. Print exactly one space between consecutive values within a row.

A solution is guaranteed to exist and to be unique.