Bạn được cho một ma trận kích thước \(N \times N\) với các giá trị 0 và 1. Bạn có thể tráo đổi bất kỳ hai hàng kề nhau nào của ma trận.

Mục tiêu của bạn là đưa tất cả các giá trị 1 trong ma trận xuống dưới hoặc nằm trên đường chéo chính. Nghĩa là, đối với mỗi \(X\) mà \(1 \le X \le N\), không được có giá trị 1 nào ở hàng \(X\) nằm bên phải cột \(X\).

Hãy trả về số lần tráo đổi hàng tối thiểu bạn cần thực hiện để đạt được mục tiêu.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\). Tiếp theo là \(T\) bộ test.
Dòng đầu tiên của mỗi bộ test có một số nguyên, \(N\). Mỗi dòng trong số \(N\) dòng tiếp theo chứa \(N\) ký tự. Mỗi ký tự là 0 hoặc 1.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất ra một dòng:

Case #X: K

Bạn được đảm bảo rằng luôn có lời giải cho mỗi bộ test.

Ràng buộc

• \(1 \le T \le 60\)

Phân nhóm

• Small dataset: \(1 \le N \le 8\)
• Large dataset: \(1 \le N \le 40\)

Đ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ụ

3
2
10
11
3
001
100
010
4
1110
1100
1100
1000

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

Nguồn

Google Code Jam 2009, Vòng 2, bài Crazy Rows.

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