택배

당신은 최근 유명 택배 회사의 최고 결정 책임자(CDM)로 새로 임명되었다. 축하한다! 고객은 택배가 빨리 도착하는 것을 좋아한다. 그래서 세계 곳곳에 택배를 배송하는 시간을 줄이기로 했다. 이 아이디어를 당국에 제안했고, 당국은 새 배송 사무소를 최대 한 곳 지을 수 있는 예산을 배정했다.

세계는 R × C 격자 칸으로 나뉘어 있다. 각 칸에는 배송 사무소가 있거나 없다. 배송 사무소가 없는 칸을 골라 새 배송 사무소를 지을 수 있다.

칸에 도착하는 택배의 배송 시간은 그 칸에 배송 사무소가 있으면 0이다. 없으면 그 칸과 다른 배송 사무소가 있는 칸 사이의 맨해튼 거리 중 최솟값이다. 전체 배송 시간은 모든 칸의 배송 시간 중 최댓값이다. 새 배송 사무소를 최대 한 개 지어서 얻을 수 있는 전체 배송 시간의 최솟값은 얼마인가?

참고: 두 칸 $(r_1, c_1)$과 $(r_2, c_2)$ 사이의 맨해튼 거리는 $|r_1 - r_2| + |c_1 - c_2|$이다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 격자의 행 수 $R$과 열 수 $C$가 주어진다. 다음 $R$개의 줄에는 각각 $C$개의 문자로 이루어진 문자열이 주어진다. 문자 0은 그 칸에 배송 사무소가 없음을, 1은 있음을 뜻한다.

각 테스트 케이스마다 한 줄에 Case #x: y 형식으로 출력한다. 여기서 $x$는 테스트 케이스 번호(1부터 시작)이고, $y$는 배송 사무소를 최대 한 개 추가한 뒤 얻을 수 있는 전체 배송 시간의 최솟값이다.

$1 \le T \le 100$. 초기 격자에는 배송 사무소가 최소 한 개 있다.

예제 1에서는 배송 사무소가 없는 다섯 칸 중 어느 곳에 새로 지어도 전체 배송 시간이 1이 된다. 예제 2에서는 모든 칸에 이미 배송 사무소가 있으므로 전체 배송 시간은 0이다. 사무소는 최대 한 개까지만 지을 수 있으며 한 개도 짓지 않아도 된다는 점에 유의하라. 예제 3에서 전체 배송 시간을 2로 만들려면 (2, 3), (3, 2), (3, 3), (3, 4), (4, 3) 중 한 곳에 지으면 된다. 다른 곳에 지으면 전체 배송 시간이 2보다 커진다.