22163_Flipthecoins

Have you ever played the game like this? There are coins placed on an N*N matrix. Initially some coins are facing upwards, and some are facing downwards. Each time, you can choose one of the following rules to take a move.

Select one row of the matrix and flip all coins in that row, which means replace all upward coins with downward coins and all downward coins with upward coins.

Select one column of the matrix and flip all coins in that column.

Select one diagonal of the matrix and flip all coins in that diagonal. Flip coins in diagonals is shown as Figure 1. Notice that there are 2*N diagonal in total. You can recognize them when taking the following picture.

Figure 1 Flip coins in diagonals

Your task is to use minimal movement to achieve an even number of downward-faced coins in each row and each column.

The first line of input there is one integer T ( T ≤ 100 ), giving the number of test cases in the input. Each test case starts with a line containing a positive integer N ( N ≤ 20 ), representing the size of the matrix. Next N line each line contains N integer, giving the status of coins in that row. Value 0 means the coin is facing upwards, while value 1 means the coin is facing downwards.

For each case, output the answer of minimal movement to achieve the goal. If it is impossible to find a solution, output -1 instead.

1
3
0 1 1
0 1 0
0 0 1

2