#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
int r, c;
int map[250][250]; // map 기본 정보
int distance_list[500]; // 거리정보
int max_distance = 0; // 가장 긴 거리
int check[250][250];
int dir_x[4] = { 1,0,-1,0 };
int dir_y[4] = { 0,1,0,-1 };
int one_x[62500]; // 배달 시간 구하는 que
int one_y[62500];
int one_d[62500];
int one_top = 0;
int one_rear = 0;
int zero_x[62500];
int zero_y[62500];
int zero_num = 0;
int k = 0;
void bfs() {
while (one_rear < one_top) {
int x = one_x[one_rear];
int y = one_y[one_rear];
int d = one_d[one_rear++];
for (int i = 0; i < 4; i++) {
int next_x = x + dir_x[i];
int next_y = y + dir_y[i];
int next_d = d + 1;
if (next_x >= 0 && next_y >= 0 && next_x < c && next_y < r) {
if (check[next_y][next_x] == 0 && map[next_y][next_x] == 0) {
check[next_y][next_x] = 1;
one_x[one_top] = next_x;
one_y[one_top] = next_y;
if (distance_list[next_d] == 0) // 거리의 시작 인덱스를 저장
distance_list[next_d] = one_top;
one_d[one_top++] = next_d;
}
}
}
}
}
void binary_search(int start, int end) {// 이진탐색
if (start <= end) {
int num = (start + end) / 2;
int bigger = 0;
int smaller = 0;
for (int i = 0; i < zero_num; i++) { // 0지점들과 거리 비교
for (int j = distance_list[num + 1]; j < one_top; j++) {
int d = abs(zero_x[i] - one_x[j]) + abs(zero_y[i] - one_y[j]);
if (d > num) {
bigger = 1;
break;
}
}
if (bigger == 0) {
smaller = 1;
break;
}
bigger = 0;
}
if (smaller == 1) { // 왼쪽 부분 탐색
k = num;
binary_search(start, num - 1);
}
else { //오른쪽 부분 탐색
binary_search(num + 1, end);
}
}
}
int main() {
int T;
int idx = 0;
cin >> T;
while (idx++ < T) {
string s;
cin >> r >> c;
for (int i = 0; i < r; i++) {
cin >> s;
for (int j = 0; j < c; j++) {
map[i][j] = s[j] - '0';
if (map[i][j] == 1) {
one_x[one_top] = j;
one_y[one_top] = i;
one_d[one_top++] = 0;
}
else if(map[i][j] == 0) { // 나중에 거리비교를 위해 0인 지점의 정보들을 따로 저장
zero_x[zero_num] = j;
zero_y[zero_num++] = i;
}
}
}
if (zero_num <= 1) // 사무실을 하나 새로 건설하기 때문에 0이 한개 이하면 총 배달 시간은 0이 된다.
cout << "Case #" << idx << ": 0" << endl;
else if (one_top == 0) { // 1이 하나도 없는 경우에는 가장 중간에 사무실을 건설
map[r / 2][c / 2] = 1;
one_x[one_top] = r/2;
one_y[one_top] = c/2;
one_d[one_top++] = 0;
bfs();
cout << "Case #" << idx << ": " << one_d[one_top - 1] << endl;
}
else {
bfs();
max_distance = one_d[one_top - 1];
binary_search(1, max_distance);
if(k != 0)
cout << "Case #" << idx << ": " << k << endl;
else
cout << "Case #" << idx << ": " << max_distance << endl;
}
k = 0;
one_top = 0;
one_rear = 0;
zero_num = 0;
memset(check, 0, sizeof(check));
memset(distance_list, 0, sizeof(distance_list));
}
}
