Matrix Flip Bit

1. Each element in the matrix 'MAT' is either a ‘0’ or ‘1.’

2. The flip operation is performed only for the 0s in the original matrix, and not for the new 0s formed as a result of flipping 1s in the original matrix.

3. If a cell is already flipped, don’t flip it twice.

4. Return the minimum number of flips needed.

Let the matrix be:

Then we return 6. As shown in the figure, the cells marked in red will be counted as they lie in the same row or column as 0 and will be flipped.

The first line of input contains ‘T’ denoting the number of test cases.

The first line of each test case contains ‘N’ denoting the dimensions of the ‘N * N’ matrix.

The next ‘N’ lines contain ‘N’ single space-separated integers denoting the matrix 'MAT’.

For each test case, print a single line that contains an integer that denotes the total number of flips made.

You don't have to print the output it has been taken care of. Just implement the given function.

1 <= T <= 5
0 <= N <= 100
MAT[i][j] = 0 or 1

Where ‘T’ is the number of test cases and ‘N’ is the number of rows and columns of the matrix 'MAT'.

Time limit: 1 sec

Sample Input 1:

1
4
1 0 1 1
1 1 0 1
1 1 1 1
1 1 0 1

Sample Output 1:

11

Explanation of sample input 1:

Test case 1:

We can see that ‘MAT’[0][1] is zero so we flip all elements which are 1 in the ith row i.e 0 th row and jth column i.e. 1st column. We can clearly see that there are 3 1s in the 0th row and 3 1s in the 1st column. Hence for the ‘0’ at ‘MAT’[0][1] we make 3 + 3 = 6 flips.

We mark the already counted cells red so we don’t count them twice.

Now we encounter the next zero at ‘MAT’[2][1]. We flip the bits in the first column which are unflipped and are 1 i.e ‘MAT’[2][2] and also the 1s which are unflipped in the second row i.e ‘MAT’[1][0] and ‘MAT’[1][3].

Finally, the count is 6 + 3 = 9, as shown with the cells marked in red.

Now the last cell which is ‘0’ i.e ‘MAT’[3][2]. We check for all the cells in the third row and second column and mark all the 1s which are not marked red and increment the count.

Finally, we will have the following matrix.

We see that there are 11 cells marked red which indicate that we flipped 11 cells so we return 11.

Sample Input 2:

2
5
1 1 0 0 1
1 0 1 1 0
1 1 1 1 1
0 0 1 1 0
1 0 1 0 1
6
0 1 1 1 1 1 
1 1 0 0 0 1 
0 0 1 0 1 1 
0 1 0 0 1 0 
1 0 1 0 1 1 
1 0 0 0 1 1 

Sample Output 2:

16
20