You have been hired recently as the Chief Decision Maker (CDM) at a famous parcel delivery company, congratulations! Customers love speedy deliveries of their parcels and you have decided to decrease the time it takes to deliver parcels around the world to win customers. You have introduced this idea to the authorities and they have allocated you enough budget to build at most one new delivery office.
The world can be divided into an grid of squares. Each square either contains a delivery office or it does not. You may pick a grid square that does not already contain a delivery office and build a new delivery office there.
The delivery time of a parcel to a square is if that square contains a delivery office. Otherwise, it is defined as the minimum Manhattan distance between that square and any other square containing a delivery office. The overall delivery time is the maximum of delivery times of all the squares. What is the minimum overall delivery time you can obtain by building at most one new delivery office?
Note: The Manhattan distance between two squares and is defined as , where operator denotes the absolute value.
输入格式
The first line of the input gives the number of test cases, . test cases follow. The first line of each test case contains the number of rows and number of columns of the grid. Each of the next lines contains a string of characters chosen from the set , where denotes the absence of a delivery office and denotes the presence of a delivery office in the square.
输出格式
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the minimum overall delivery time you can obtain after adding at most one additional delivery office.
In Sample Case #1, you get a minimum overall delivery time of by building a new delivery office in any one of the five squares without a delivery office.
In Sample Case #2, all the squares already have a delivery office and so the minimum overall delivery time is . Note you have to add at most one delivery office.
In Sample Case #3, to get a minimum overall delivery time of , you can build a new delivery office in any of these squares: , , , , or . Any other possibility results in a higher overall delivery time than .
Limits
.
There is at least one delivery office in the initial grid.
