Bạn là người được chọn vào vị trí Giám đốc của một công ty vận chuyển ở Long An. Để tăng lượng khách hàng, bạn quyết định giảm thời gian vận chuyển của các đơn hàng bằng cách mở thêm các văn phòng vận chuyển. Nhưng vì ngân sách có hạn nên bạn chỉ được phép mở thêm một văn phòng.

Nhà của các khách hàng được mô tả bằng một lưới ~R \times C~, với mỗi ô có thể chứa tối đa một văn phòng. Bạn có thể chọn bất kì ô vuông nào để xây dựng văn phòng mới miễn là nó còn trống.

Thời gian để chuyển một bưu kiện là ~0~ nếu có một văn phòng tại ô vuông đó. Ngược lại, thời gian vận chuyển sẽ là khoảng cách Manhattan nhỏ nhất từ ô vuông đó đến một văn phòng bất kì. Tổng thời gian giao hàng cho tất cả các khách hàng sẽ là thời gian lớn nhất để giao một đơn hàng. Là một giám đốc tập sự bạn hãy xác định xem tổng thời gian giao hàng sẽ là bao nhiêu?

Lưu ý: Khoảng cách Manhattan giữa hai ô ~(r1, c1)~ và ~(r2, c2)~ được xác định là ~|r1 − r2| + |c1 − c2|~, trong đó ~|x|~ biểu thị giá trị tuyệt đối của ~x~.

Input

Dòng đầu tiên chứa ~T~ là test. Trong mỗi test có dạng:

• Dòng thứ nhất chứa số ~R~ và ~C~, lần lượt là số dòng và số cột của lưới.
• ~R~ dòng tiếp theo mỗi dòng chứa ~C~ kí tự ~0~ hoặc ~1~. Kí tự ~0~ cho biết ô vuông đó đang trống và kí tự ~1~ thể hiện đang có văn phòng được đặt tại đó.

Output

Với mỗi test, in ra Case #x: y trong đó ~x~ là số thứ tự của test và ~y~ là thời gian vận chuyển nhỏ nhất khi mở thêm một văn phòng.

Subtask 1: ~1 \le R, C \le 10~.

Subtask 2: ~1 \le R, C \le 250~.

Sample input

3
3 3
101
000
101
1 2
11
5 5
10001
00000
00000
00000
10001

Sample output

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