의상 변경

Supervin은 잘 알려진 안무가이다. 오늘은 그의 안무가 경력 N주년이다. 이를 기념하기 위해 그는 한 변의 크기가 N인 정사각 격자 모양의 무대에서 춤 공연을 계획하고 있다. 각 격자 칸에는 정확히 한 명의 무용수가 선다.

각 무용수는 의상을 입는다. 각 의상은 단 하나의 색을 가지며, 소재는 양모 또는 면 중 하나이다. Supervin은 무용수들의 의상을 디자인할 때 1부터 N까지의 번호가 매겨진 N가지 색 중에서 선택할 수 있다.

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

Supervin은 모든 무용수가 자신이 특별하다고 느끼기를 원한다. 따라서 Supervin은 어떤 무용수도 같은 의상(같은 색과 같은 소재)을 입은 다른 무용수와 행이나 열을 공유하지 않도록 무용수들의 의상 색 및/또는 소재를 바꿀 준비가 되어 있다. 이를 달성하기 위해 의상을 바꿔야 하는 무용수 수의 최솟값은 얼마인가? (의상의 색과 소재를 모두 바꾸더라도 변경은 단 한 번으로 센다는 점에 유의하라.)

제한

1 ≤ T ≤ 100. -N ≤ $A_{i, j}$ ≤ N, 모든 i, j에 대해. $A_{i, j}$ ≠ 0, 모든 i, j에 대해. 시간 제한: 테스트 세트당 15초. 메모리 제한: 1GB.

테스트 세트 1 (공개)

2 ≤ N ≤ 4.

테스트 세트 2 (비공개)

2 ≤ N ≤ 100.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 무용수 격자의 한 변 길이(단위 칸 수)를 나타내는 정수 N이 담긴 한 줄로 시작한다. 그다음 N개의 줄이 주어지며, 각 줄에는 0이 아닌 정수 $A_{i, j}$가 N개씩 주어진다. i번째 줄의 j번째 값은 격자의 i번째 행, j번째 열에 있는 무용수의 의상을 나타낸다. 값의 절댓값은 색을 나타내고, 값의 부호는 소재를 나타낸다(양모는 -, 면은 +).

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

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

예제 케이스 #2에서 최적해 중 하나는 A의 값을 다음과 같이 바꾸는 것이다(굵은 글씨는 바뀐 값을 나타낸다).

다른 최적해도 가능하다. 무용수 한 명의 의상에서 색과 소재를 모두 바꾸더라도 변경은 단 한 번으로 센다는 점에 유의하라.

예제 케이스 #3에서 최적해 중 하나는 A의 값을 다음과 같이 바꾸는 것이다(굵은 글씨는 바뀐 값을 나타낸다).

다른 최적해도 가능하다.

예제 케이스 #4에서 최적해 중 하나는 A의 값을 다음과 같이 바꾸는 것이다(굵은 글씨는 바뀐 값을 나타낸다).

다른 최적해도 가능하다.