Consider a 3 x 3 grid of numbers g where each cell contains either a 0 or a 1. We define a function f that transforms such a grid: each cell of the grid f(g) is the sum (modulo 2) of its adjacent cells in g (two cells are considered adjacent if and only if they share a common side).
Furthermore, we define f (i)(g) recursively as f (0)(g) = g and f (i+1)(g) = f(f (i)(g)) (where i ≥ 0). Finally, for any grid h, let kg(h) be the number of indices i such that h = f (i)(g) (we may have kg(h) = ∞). Given a grid g, your task is to compute the greatest index i such that kg(f (i)(g)) is finite.
Input begins with the number of test cases on its own line.
Each case consists of a blank line followed by three lines of three characters, each either 1 or 0.
The j'th character
of the i'th row of the test case is the value in the j'th cell
of the i'th row of the grid g.
For each test case, output the greatest index i such that kg(f (i)(g)) is finite. If there is no such index, output -1.
3 111 100 001 101 000 101 000 000 000
3 0 -1