Costume Change


Submit solution

Points: 10
Time limit: 15.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
C++

Roberto is a well-known choreographer. Today is the \(N\)-th anniversary of his career as a choreographer. To celebrate, he is planning a dance on a stage that is a square grid of size \(N\) by \(N\). Exactly one dancer will stand in each cell of the grid.

Each dancer will wear a costume; each costume has a single color and is made of either wool or cotton as a material. Roberto has \(N\) colors to choose from when designing the costumes for his dancers, indexed from \(1\) to \(N\).

Each dancer wants to feel special. If two or more dancers share a row or column and also have costumes of the same color and material, they will no longer feel special.

Roberto wants all his dancers to feel special. Therefore, he is prepared to change the color and/or the material of the dancers' costumes so that no dancer shares a row or column with another dancer who has the same costume (same color and same material). What is the minimum number of dancers whose costumes must be changed to achieve this? (Note that changing both the color and the material of a costume still counts as a single change).

Input

The first line of the input gives the number of test cases, \(T\). \(T\) test cases follow. Each begins with one line containing an integer \(N\): the side length (in unit cells) of the square grid of dancers.

Then, \(N\) lines follow; each contains \(N\) non-zero integers \(A_{i,j}\). The \(j\)-th value on the \(i\)-th line represents the costume of the dancer in the \(i\)-th row and the \(j\)-th column of the grid. The magnitude of the value indicates the color, and the sign of the value indicates the material (\(-\) for wool, \(+\) for cotton).

Output

For each test case, you must output one line containing x, where x is the minimum number of dancers whose costumes must be changed, as described above.

Example
Sample Input Sample Output
4
2
1 2
2 1
0
2
1 1
2 1
1
2
1 2
1 2
2
2
2 2
-2 2
1

In Sample Case #1, no costumes need to be changed, as no dancer shares a row or column with another dancer who has the same costume.

In Sample Case #2, an optimal solution is to change the value of \(A\) to the following (bold indicates changed values): 1 -2 2 1 Other optimal solutions are possible. Note that changing both the color and the material of a dancer's costume only counts as one change.

In Sample Case #3, an optimal solution is to change the value of \(A\) to the following (bold indicates changed values): 1 2 2 1 Other optimal solutions are possible.

In Sample Case #4, an optimal solution is to change the value of \(A\) to the following (bold indicates changed values): 2 -2 -2 2 Other optimal solutions are possible.

Source

Google Code Jam 2018, Round 2 — Costume Change.


Comments

There are no comments at the moment.