Consider a 3 × 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 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 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. Output 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’. Sample Input 3 111 100 001 101 000 101 000 000 000 Sample Output 3 0 -1