#2662 Chulseung The Universal Set

1 s   128 MB  

Description

철승이의 지식은 우주와 같다. 모든 것을 포함함과 동시에 끊임없이 팽창하기 때문이다. 이
 
세상의 지식들을 집합으로 표현하자면 철승이의 지식은 전체 집합(Universal set)이라고 할 수
 
있다. 그렇기에 우리의 지식은 아무리 늘어나도 언젠가는 철승이의 부분집합이 될 수 밖에 없다. 
 
하지만 인간은 언제나 연구와 발명을 통해 새로운 지식을 만들어낸다. 이런 새로운 지식은
 
철승이라도 알 수 없다. 하지만 철승이는 그 어떤 지식도 쉽게 습득할 수 있다. 그로 인해
 
철승이의 지식은 곧 다시 전체집합이 될 수 있다. 아래의 그림은 철승이가 세상의 지식을 습득하는
 
과정을 나타낸다. 흰색은 이미 철승이의 부분집합이 된 지식을 나타낸다. 칠해져 있는 칸은
 
철승이가 아직 습득하지 않은 지식을 나타낸다. 그 중 철승이가 이미 습득한 지식과 상하좌우 중
 
하나 이상의 방향으로 접해있는 지식(회색 칸)은 철승이는 다음 날 습득할 수 있게 된다.
 
 
 

 
왼쪽의 그림의 예제에서 회색 칸은 철승이가 습득하지 않은 지식이지만, 철승이의 지식과
 
맞닿아있는 지식들을 나타낸다. 오른쪽 그림은 그 후 하루가 지난 상태를 나타낸다. 이처럼
 
철승이의 지식은 빠른 속도로 우리의 지식을 포함해간다. 오늘 새로 생겨난 지식들의 상태를
 
나타낸 정보를 통해, 철승이가 모든 지식을 습득할 때 까지 걸리는 시간을 계산하는 프로그램을
 
작성하시오.
 

Input

첫 줄에는 테스트 케이스의 수 T 가 주어진다.
 
각 테스트 케이스의 첫 줄에는 지도의 세로 칸의 수 R 과, 가로 칸의 수 C 가 차례로 주어진다. 
 
R 과 C 는 100 이하의 자연수이다. 
 
그 후 R 줄에 걸쳐 지식 분포 정보가 주어진다. 각 칸의 정보는 공백으로 구분되며 1 혹은 0 으로
 
표시된다. 0 으로 표시된 칸은 이미 철승이가 습득한 정보를 나타낸다. 1 로 표시된 칸은 철승이가
 
아직 습득하지 않은 정보를 나타낸다.

Output

각 테스트 케이스 별로 한 줄에 철승이가 모든 지식을 습득하기까지 필요한 날짜를 정수로
 
출력하시오.

Sample Input

Sample Output

1
5 6
0 0 0 0 0 0
0 1 1 0 0 0
0 1 1 1 0 0
0 1 1 1 1 1
0 0 0 0 1 1
2