모래성

명우는 여름방학을 맞아 친구들과 바닷가로 놀러 갔다. 이번에 간 해수욕장의 이름은 ALPS다. 수영복을 입은 사람들에게 관심이 많은 원철이와 달리 명우의 관심사는 해변의 모래다. 모래로는 무엇이든 만들 수 있고, 그렇게 만든 작품이 파도에 사라지는 모습은 가장 빛날 수 있는 순간을 알고 스스로 아름답게 산화하는 것처럼 보인다. 아무도 명우의 말에 공감해 주지 않았고, 결국 명우는 혼자서 모래성을 쌓았다.

명우는 언젠가 파도에 무너질 것까지 계산해서 모래성을 만들었다. 모래성은 2차원 격자 위에 놓여 있고, 칸마다 모래의 튼튼함이 다르다. 튼튼함은 1 이상 9 이하의 숫자로 나타낸다.

파도가 한 번 칠 때 각 칸은 자기 주변 8방향(위, 아래, 왼쪽, 오른쪽, 그리고 네 대각선)을 본다. 그중 모래성이 쌓여 있지 않은 칸의 개수가 자기 튼튼함보다 크거나 같으면 그 칸은 무너진다. 그 외의 경우에는 파도가 쳐도 무너지지 않는다. 한 번의 파도에서 무너지는 칸은 그 파도가 치기 직전의 상태를 기준으로 함께 정해지고 동시에 무너진다. 무너진 칸은 그때부터 모래성이 쌓여 있지 않은 칸으로 취급한다.

파도가 계속 치면 모래성의 모양은 언젠가 더 이상 변하지 않는다. 모래성의 모양이 더 이상 변하지 않으려면 파도가 몇 번 쳐야 하는지 구하자.

첫째 줄에 모래성이 놓인 격자의 세로 크기 $H$와 가로 크기 $W$가 주어진다. ($1 \le H, W \le 1000$)

다음 $H$개의 줄에는 각각 $W$개의 문자가 주어져 모래성의 상태를 나타낸다. 각 문자는 1 이상 9 이하의 숫자이거나 '.'이다. 숫자는 그 칸에 쌓인 모래의 튼튼함이고, '.'은 그 칸에 모래성이 없다는 뜻이다.

모래성은 격자의 가장자리와 접해 있지 않다.

모래성의 모양이 더 이상 변하지 않을 때까지 파도가 몇 번 쳐야 하는지 첫째 줄에 출력한다. 처음부터 모양이 변하지 않으면 0을 출력한다.

다음 모래성을 보자.

......
.939..
.3428.
.9393.
......

첫 번째 파도가 치고 나면 모래성은 이렇게 변한다.

......
.9.9..
..428.
.9.9..
......

첫 번째 파도로 2의 주변에 빈 칸이 두 군데 더 생겼고, 다음 파도에서 이 2가 휩쓸린다.

......
.9.9..
..4.8.
.9.9..
......

그다음 파도에서는 가운데 4가 휩쓸린다.

......
.9.9..
....8.
.9.9..
......

이제 아무리 파도가 쳐도 모래성은 이 상태를 유지한다. 즉 파도가 3번 쳐야 모래성의 모양이 바뀌지 않는다.