소포

최근 유명 소포 배송 회사의 최고 의사 결정권자(CDM)로 고용되었다. 축하한다! 고객들은 소포가 빠르게 배송되는 것을 좋아하며, 고객을 확보하기 위해 전 세계에서 소포를 배송하는 데 걸리는 시간을 줄이기로 했다. 이 아이디어를 관계자들에게 소개했고, 관계자들은 최대 하나의 새 배송 사무소를 지을 수 있는 충분한 예산을 배정했다.

세계는 R × C개의 정사각형으로 이루어진 격자로 나눌 수 있다. 각 칸에는 배송 사무소가 있거나 없다. 아직 배송 사무소가 없는 격자 칸을 하나 골라 그곳에 새 배송 사무소를 지을 수 있다.

어떤 칸에 배송 사무소가 있다면 그 칸까지의 소포 배송 시간은 0이다. 그렇지 않다면 그 칸과 배송 사무소가 있는 다른 임의의 칸 사이의 맨해튼 거리 중 최솟값으로 정의한다. 전체 배송 시간은 모든 칸의 배송 시간 중 최댓값이다. 새 배송 사무소를 최대 하나 지어서 얻을 수 있는 전체 배송 시간의 최솟값은 얼마인가?

참고: 두 칸 (r1,c1)와 (r2,c2) 사이의 맨해튼 거리는 |r1 - r2| + |c1 - c2|로 정의하며, 여기서 |*| 연산자는 절댓값을 나타낸다.

제한

시간 제한: 테스트 세트당 15초. 메모리 제한: 1GB. 1 ≤ T ≤ 100. 초기 격자에는 적어도 하나의 배송 사무소가 있다.

테스트 세트 1 (공개)

1 ≤ R ≤ 10. 1 ≤ C ≤ 10.

테스트 세트 2 (비공개)

1 ≤ R ≤ 250. 1 ≤ C ≤ 250.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 격자의 행 수 R과 열 수 C가 주어진다. 이어지는 R개의 각 줄에는 집합 {0, 1}에서 선택된 C개의 문자로 이루어진 문자열이 주어진다. 여기서 0는 해당 칸에 배송 사무소가 없음을 나타내고, 1는 해당 칸에 배송 사무소가 있음을 나타낸다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), y는 배송 사무소를 최대 하나 추가한 후 얻을 수 있는 전체 배송 시간의 최솟값이다.

예제 케이스 #1에서는 배송 사무소가 없는 다섯 칸 중 어느 한 곳에 새 배송 사무소를 지으면 전체 배송 시간의 최솟값 1을 얻는다.

예제 케이스 #2에서는 모든 칸에 이미 배송 사무소가 있으므로 전체 배송 시간의 최솟값은 0이다. 배송 사무소를 최대 하나 추가해야 한다는 점에 유의하라.

예제 케이스 #3에서는 전체 배송 시간의 최솟값 2을 얻기 위해 다음 칸 중 어느 곳에든 새 배송 사무소를 지을 수 있다: (2, 3), (3, 2), (3, 3), (3, 4), 또는 (4, 3). 다른 어떤 선택도 2보다 더 큰 전체 배송 시간을 초래한다.