4592：Boring Game

Zero likes to play a boring game when he feels extremely boring. This his game proceeds in a square board with n rows and n column. Each grid in the board has either of two colors black or white. In each turn, Zero chooses a grid first. Let’s assume that the grid he chooses locates in the x^th row and the y^th column. And then, the neighbors which are existed of this grid (x + 1, y), (x – 1, y), (x, y + 1), (x, y – 1) and itself will convert their color into another. Till the end, Zero will transform the initial board to the goal board whose grids are all white. For instance, Here is the way to attain his goal. In his first turn, he selects (2, 2). And then he selects (1, 1) in the second turn. After that, he reaches his goal.

Zero reckons this mission, however, is too simple and naive. So he prefers to accomplish this assignment in minimal turns. He doesn’t know whether the turns he needs are the minimal turns, because of that he needs you to tell him the minimal turns of these initial boards.

There are several test cases in the input file. The first line of the input file contains an integer m(m <= 10⁶), then m cases follow.
The first line of each test case contains an integer n(1 <= n <= 8), which is the length of a side of the square board.
Then the next line contains n integer a[i](0 <= a[i] <= 2ⁿ, 1 <= i <= n), which is the statement of the i^th row respectively. The definition of a statement can be illustrated as n-length binary numbers, zero represents white and one represents black. For example, when n is equal to 4 and a[0] is equal to 5 = (0101)₂, you can consider that the condition in the first line of this board is white, black, white, black.

For each test case, output the minimal turns. If the initial board doesn’t contain a way to reach the goal board, please output -1.