Parcels

You were recently hired as the Chief Decision Maker (CDM) at a well-known parcel delivery company. Congratulations! Customers love fast deliveries, so you have decided to cut the time it takes to deliver parcels around the world. You presented this idea to the authorities, and they gave you a budget to build at most one new delivery office.

The world is divided into an R × C grid of squares. Each square either has a delivery office or does not. You may pick a square without a delivery office and build a new one there.

The delivery time to a square is 0 if the square has a delivery office. Otherwise, it is the minimum Manhattan distance from that square to any other square with a delivery office. The overall delivery time is the maximum delivery time over all squares. What is the minimum overall delivery time you can get by building at most one new delivery office?

Note: The Manhattan distance between squares $(r_1, c_1)$ and $(r_2, c_2)$ is $|r_1 - r_2| + |c_1 - c_2|$.

The first line contains the number of test cases $T$. Each test case begins with a line containing the number of rows $R$ and columns $C$ of the grid. Each of the next $R$ lines contains a string of $C$ characters, each either 0 (no delivery office in that square) or 1 (a delivery office is in that square).

For each test case, print one line in the form Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the minimum overall delivery time you can get after adding at most one delivery office.

$1 \le T \le 100$. The initial grid has at least one delivery office.

In Sample Case #1, building a new delivery office in any of the five squares without one gives a minimum overall delivery time of 1. In Sample Case #2, every square already has a delivery office, so the minimum overall delivery time is 0. You may add at most one office, so adding none is also allowed. In Sample Case #3, the overall delivery time is 2 if you build in (2, 3), (3, 2), (3, 3), (3, 4), or (4, 3). Any other square gives a higher overall delivery time.