Light Toggle Puzzle

Have you ever played the "Light Toggle" game?

There are 25 lights arranged in a 5×5 grid. Each light has an on/off state, with 1 representing an on light and 0 an off light.

In every move, the player may toggle the state of one light. When a light is toggled, its state changes and the states of its four direct neighbors (up, down, left, right) are also toggled.

For example, given the following initial state:

10111
01101
10111
10000
11011

if the top-left light is toggled, the state becomes:

01111
11101
10111
10000
11011

and then toggling the center light yields:

01111
11001
11001
10100
11011

Your task is: given several initial configurations, determine whether it is possible to turn all the lights on (i.e. all 1’s) in no more than 6 moves.

Mathematically, if we denote toggling of the cell at position \((i,j)\) as applying the operation:

$$ T(i,j):\quad a_{i,j} \oplus= 1,\; a_{i-1,j} \oplus= 1,\; a_{i+1,j} \oplus= 1,\; a_{i,j-1} \oplus= 1,\; a_{i,j+1} \oplus= 1, $$

where \(\oplus\) indicates addition modulo 2, then you are to decide if there exists a set of at most 6 positions (each toggled at most once, since toggling twice cancels out) such that applying these toggles to the given configuration produces a grid where every entry is 1.

inputFormat

The first line contains a single integer \(T\) indicating the number of test cases.

Each test case consists of 5 lines, each line is a string of 5 characters, each character is either '0' or '1', representing the initial state of the corresponding row of the grid.

outputFormat

For each test case, output a single line containing YES if it is possible to turn all lights on within 6 moves, or NO otherwise.

sample

1
11111
11111
11111
11111
11111

YES

</p>