확장판 라이트 아웃

라이트 아웃(Lights Out®)은 켜져 있는 불을 모두 끄는 퍼즐이다. 이 확장판의 판은 한 줄에 6개씩, 5줄로 배치된 버튼으로 이루어진다. 즉 5행 6열이다. (원래 퍼즐은 5행 5열이다.) 각 버튼에는 불이 하나씩 달려 있다. 어떤 버튼을 누르면 그 버튼과 상·하·좌·우로 맞닿은 (최대 네 개의) 이웃 버튼의 불 상태가 함께 반전된다. 즉 켜져 있던 불은 꺼지고, 꺼져 있던 불은 켜진다. 따라서 모서리에 있는 버튼은 불 3개를, 가장자리에 있는 버튼은 불 4개를, 그 밖의 버튼은 불 5개를 바꾼다. 예를 들어 아래 왼쪽 그림에서 X로 표시된 버튼들을 누르면 화면이 오른쪽 그림처럼 바뀐다.

게임의 목표는 임의의 초기 상태에서 시작하여 버튼을 눌러 모든 불을 끄는 것이다. 인접한 버튼을 누르면 한 버튼의 효과가 다른 버튼의 효과를 상쇄할 수 있다. 예를 들어 아래 그림에서 2행 3열 버튼과 2행 5열 버튼을 누르면, 두 버튼 모두 2행 4열의 불을 반전시키므로 결국 2행 4열의 상태는 바뀌지 않는다.

참고:

1. 버튼을 누르는 순서는 결과에 영향을 주지 않는다.
2. 같은 버튼을 두 번 누르면 첫 번째 누름의 효과가 정확히 취소되므로, 어떤 버튼도 두 번 이상 누를 필요가 없다. 즉 각 버튼은 누르거나(1) 누르지 않거나(0) 둘 중 하나다.
3. 둘째 줄의 대응하는 버튼을 누르면 첫째 줄의 불을 모두 끌 수 있다. 이 과정을 각 줄에 반복하면 처음 네 줄의 불을 모두 끌 수 있다. 마찬가지로 2열, 3열, …의 버튼을 누르면 처음 다섯 열의 불을 모두 끌 수 있다.

각 퍼즐에 대해 눌러야 할 버튼을 구하는 프로그램을 작성하라.

입력의 첫 줄에는 뒤따르는 퍼즐의 개수를 나타내는 양의 정수 $n$이 주어진다. 각 퍼즐은 다섯 줄로 이루어지며, 각 줄에는 하나 이상의 공백으로 구분된 여섯 개의 0 또는 1이 놓인다. 0은 그 자리의 불이 처음에 꺼져 있음을, 1은 켜져 있음을 뜻한다.

각 퍼즐에 대해 먼저 PUZZLE #m 형식의 문자열을 한 줄에 출력한다. 여기서 $m$은 입력에서 그 퍼즐의 순번(1부터 시작)이다. 그 다음 줄부터는 입력과 같은 형식의 5행 6열 표를 출력한다. 이 표에서 1은 퍼즐을 풀기 위해 눌러야 하는 버튼을, 0은 누르지 않는 버튼을 나타낸다. 한 줄 안에서 각 0 또는 1 사이에는 정확히 하나의 공백을 둔다.

해는 항상 존재하며 유일하다.