Supervin là một biên đạo múa nổi tiếng. Hôm nay là kỷ niệm năm thứ \(N\) trong sự nghiệp biên đạo của anh. Để ăn mừng, anh lên kế hoạch cho một điệu múa trên sân khấu là lưới vuông \(N\times N\), mỗi ô có đúng một vũ công.

Mỗi vũ công mặc một bộ trang phục có đúng một màu và làm bằng len hoặc cotton. Supervin có \(N\) màu, được đánh số từ 1 đến \(N\).

Mỗi vũ công muốn cảm thấy mình đặc biệt. Nếu có ít nhất hai vũ công cùng hàng hoặc cùng cột, đồng thời mặc trang phục cùng màu và cùng chất liệu, họ sẽ không còn cảm thấy đặc biệt.

Supervin muốn tất cả vũ công đều đặc biệt. Anh sẵn sàng đổi màu và/hoặc chất liệu của một số trang phục sao cho không vũ công nào chung hàng hoặc cột với một người có cùng kiểu trang phục. Cần đổi trang phục của ít nhất bao nhiêu vũ công? Đổi cả màu lẫn chất liệu của một bộ vẫn chỉ tính là một lần đổi.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\).

Mỗi bộ test bắt đầu bằng \(N\), độ dài cạnh sân khấu tính theo số ô. Tiếp theo là \(N\) dòng, mỗi dòng chứa \(N\) số nguyên khác 0 \(A_{i,j}\). Giá trị thứ \(j\) trên dòng thứ \(i\) biểu diễn trang phục tại hàng \(i\), cột \(j\): trị tuyệt đối là màu, dấu âm là len và dấu dương là cotton.

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, trong đó \(x\) là số thứ tự bộ test, bắt đầu từ 1, và \(y\) là số vũ công ít nhất phải đổi trang phục.

Ràng buộc

• \(1\le T\le100\).
• \(-N\le A_{i,j}\le N\) với mọi \(i,j\).
• \(A_{i,j}\ne0\) với mọi \(i,j\).

Phân nhóm

• Test Set 1 (Hiển thị): \(2\le N\le4\).
• Test Set 2 (Ẩn): \(2\le N\le100\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

4
2
1 2
2 1
2
1 1
2 1
2
1 2
1 2
2
2 2
-2 2

Case #1: 0
Case #2: 1
Case #3: 2
Case #4: 1

  1 -2
  2 1

  1 2
  2 1

  2 -2
  -2 2

Nguồn

Google Code Jam 2018, Vòng 2, bài Costume Change.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.