의상 바꾸기

Supervin은 유명한 안무가다. 오늘은 그의 안무 경력 N주년이 되는 날이다. 이를 기념하여 그는 한 변의 길이가 N인 정사각형 격자 모양의 무대에서 춤을 구성하려 한다. 격자의 각 칸에는 무용수가 정확히 한 명씩 선다.

각 무용수는 의상을 입는다. 의상은 색 하나를 가지며, 소재는 울 또는 면 중 하나다. Supervin은 의상을 디자인할 때 1번부터 N번까지 번호가 붙은 N가지 색 중에서 고를 수 있다.

각 무용수는 자신이 특별하다고 느끼고 싶어 한다. 같은 행이나 같은 열에 있는 두 명 이상의 무용수가 색과 소재가 같은 의상을 입고 있으면, 그들은 더 이상 특별하다고 느끼지 않는다.

Supervin은 모든 무용수가 특별하다고 느끼기를 바란다. 그래서 같은 행이나 같은 열에 같은 의상(색과 소재가 같은 의상)을 입은 다른 무용수가 없도록, 필요하면 의상의 색이나 소재를 바꿀 준비가 되어 있다. 의상의 색과 소재를 모두 바꿔도 한 번의 변경으로 센다. 이를 실현하려면 의상을 최소 몇 명의 무용수에게서 바꿔야 하는가?

첫 줄에 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 나온다. 각 테스트 케이스는 정사각형 격자의 한 변의 길이 N이 적힌 줄로 시작한다. 이어서 N개의 줄이 주어지며, 각 줄에는 0이 아닌 정수 N개가 공백으로 구분되어 있다. i행 j열에 있는 무용수의 의상은 i번째 줄의 j번째 값 A_{i,j}로 나타낸다. 값의 절댓값은 색을, 부호는 소재를 나타낸다(음수는 울, 양수는 면).

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 위에서 설명한 대로 의상을 바꿔야 하는 무용수의 최소 인원이다.

$1 \le T \le 100$.

모든 $i, j$에 대해 $-N \le A_{i,j} \le N$.

모든 $i, j$에 대해 $A_{i,j} \ne 0$.

샘플 케이스 #1에서는 같은 의상을 입은 다른 무용수와 행이나 열을 공유하는 무용수가 없으므로 의상을 바꿀 필요가 없다.

샘플 케이스 #2에서는 A를 다음과 같이 바꾸는 것이 최적해 중 하나다.

1 -2
2 1

1행 2열의 값만 1에서 -2로 바뀐다. 다른 최적해도 가능하다. 의상의 색과 소재를 모두 바꿔도 한 번의 변경으로 센다.

샘플 케이스 #3에서는 A를 다음과 같이 바꾸는 것이 최적해 중 하나다.

1 2
2 1

다른 최적해도 가능하다.

샘플 케이스 #4에서는 A를 다음과 같이 바꾸는 것이 최적해 중 하나다.

2 -2
-2 2

다른 최적해도 가능하다.