Bạn vừa xây xong một nhà máy hoàn toàn mới. Nhà máy có \(N\) máy khác nhau, và để hoạt động tốt, mỗi máy cần được đúng một công nhân vận hành.

Bạn cũng thuê \(N\) công nhân để vận hành các máy đó. Vì tuyển người quá gấp, bạn chưa kiểm tra xem họ có thật sự biết dùng máy hay không. Giờ bạn đã hỏi và biết, với mọi \(i,j\), công nhân thứ \(i\) có biết vận hành máy thứ \(j\) hay không.

Trong một ngày làm việc thông thường, công nhân đến nhà máy theo thứ tự ngẫu nhiên và thứ tự có thể khác mỗi ngày. Khi một người tới, họ tìm tất cả máy mà mình biết vận hành và chưa có người vận hành, rồi chọn ngẫu nhiên một máy trong số đó và làm việc với máy ấy suốt ngày. Nếu mọi máy họ biết vận hành đều đã có người, hôm đó họ sẽ không làm việc. Mục tiêu của bạn là bảo đảm mọi máy đều được vận hành mỗi ngày, bất kể công nhân đến theo thứ tự nào và chọn máy nào.

Ví dụ, có hai công nhân A, B và hai máy 1, 2. A biết vận hành cả 1 và 2; B biết vận hành 1 nhưng không biết 2. Nếu B đến trước, B chọn máy 1, rồi A buộc phải chọn máy 2 và nhà máy hoạt động tốt. Nhưng nếu A đến trước, A có thể chọn máy 1; khi B tới sẽ không còn việc, máy 2 không có người vận hành và nhà máy lãng phí cả ngày!

Ví dụ khác, vẫn có A, B và máy 1, 2, nhưng A chỉ biết máy 1 còn B không biết vận hành máy nào. Dù công nhân đến theo thứ tự nào, nhà máy cũng không thể hoạt động tốt.

Trước khi mở nhà máy, để bảo đảm nhà máy luôn hoạt động tốt, bạn có thể dạy công nhân vận hành thêm máy. Mỗi bài học dạy một công nhân vận hành một máy có giá một đô-la. Mỗi bài học chỉ liên quan đến một công nhân và một máy, nhưng bạn có thể dạy bao nhiêu bài cho bao nhiêu người tùy ý, và một người có thể học nhiều bài. Bạn không thể làm một công nhân quên cách vận hành máy họ đã biết.

Cả hai ví dụ trên đều có thể sửa bằng cách dạy B vận hành máy 2. Khi đó, mọi máy chắc chắn có người mỗi ngày, bất kể thứ tự đến và lựa chọn của công nhân khi họ có nhiều phương án.

Số đô-la tối thiểu cần chi cho đào tạo để bảo đảm nhà máy hoạt động tốt mỗi ngày là bao nhiêu?

Dữ liệu vào

Dòng đầu tiên chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng một dòng chứa số nguyên \(N\), là số công nhân (và cũng là số máy). Tiếp theo là \(N\) dòng, mỗi dòng là chuỗi \(N\) ký tự. Ký tự thứ \(j\) của dòng thứ \(i\) là 1 nếu công nhân \(i\) biết vận hành máy \(j\), và là 0 nếu không.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1), còn y là số nguyên không âm: số đô-la tối thiểu cần chi để chắc chắn cả \(N\) máy luôn có người vận hành.

Ràng buộc

• \(1 \le T \le 100\).

Phân nhóm

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

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

5
2
11
10
2
10
00
3
000
000
000
1
1
3
000
110
000

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

Nguồn

Google Code Jam 2016, Vòng 2, bài Freeform Factory.

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