아틀란티스에 내리는 비

아틀란티스섬에 비가 내려 모든 땅이 침식되어 사라질 것이다. 대피를 준비하기 위해 알고 싶은 것은 그 일이 얼마나 빨리 일어날지이다.

아틀란티스의 지도가 있다. 지도는 정사각형 격자이며, 각 칸에는 그 칸에 있는 땅의 해수면 위 높이가 미터 단위로 적혀 있다. 지도 밖의 모든 칸의 높이는 0이다. 높이가 0인 모든 칸은 물이고, 높이가 그보다 큰 모든 칸은 땅이다. 높이가 그보다 낮은 칸은 없다.

원천 칸과 도착 칸이 한 변을 공유하고, 도착 칸의 물 높이가 원천 칸의 물 높이 이하라면 물은 원천 칸에서 도착 칸으로 흐를 수 있다.

비가 매우 빠르게 내리므로, 어떤 칸의 빗물이 흘러갈 곳이 없다면 빗물이 흘러갈 수 있는 칸이 생길 때까지 그 칸에 물이 고인다. 지도에 없는 칸은 흐르는 물을 얼마든지 받아들일 수 있다. 예를 들어, 다음 지도는

5 9 9 9 9 9
0 8 9 0 2 5
3 9 9 9 9 9

빠르게 물로 채워진다. 각 칸에서 물의 높이와 땅의 높이를 더한 값을 수위라고 하자. 수위는 다음과 같아진다.

5 9 9 9 9 9
0 8 9 5 5 5
3 9 9 9 9 9

땅 한가운데의 0은 물이지만 지도 바깥과 연결되어 있지 않으므로 물이 그저 고인다는 점에 유의하라. 그러나 땅의 경계에 있는 0은 지도 바깥과 연결되어 있으므로, 8의 물은 그곳을 통해 바깥으로 흐를 수 있다.

물이 흐르는 방향은 수위에 따라 결정된다. 특정 원천 칸에서 물이 흘러갈 수 있는 칸이 여러 개라면, 그 원천의 물은 수위가 가장 낮은 칸으로 흐른다(뒤에서 알 수 있듯이 동률은 중요하지 않다).

이제 침식이 시작된다. 매일 각 칸은 그 칸에서 물이 어떻게 흐르는지에 따라 침식되어 높이가 감소한다. 물이 S에서 T로 흐른다면 S의 높이는 min(WaterLevel(S) - WaterLevel(T), M)만큼 감소한다. 모든 침식은 하루가 끝날 때 정확히 동시에 일어난다. 예를 들어 M=5이면 위 지도는 다음과 같이 침식된다.

0 4 4 4 4 4
0 3 5 0 2 0
0 4 4 4 4 4

하루 동안 침식된 뒤에는 남는 물이 흘러 나간다. 이웃 칸의 수위보다 수위가 높은 칸은 두 수위가 같아질 때까지 물을 잃는다. 또한 첫날과 같은 방식으로 물이 고인다. 첫날이 지나면 이 지도의 수위는 다음과 같아진다.

0 4 4 4 4 4
0 3 5 2 2 0
0 4 4 4 4 4

하루 더 침식된 뒤 지도는 다음과 같아진다.

0 0 0 0 0 0
0 0 2 0 0 0
0 0 0 0 0 0

...그리고 아틀란티스인들은 매우 서둘러 탈출해야 할 것이다. 모든 높이가 0까지 침식되는 데 며칠이 걸리는지 구하는 것이 과제이다.

제한

1 ≤ T ≤ 40. 메모리 제한: 1GB.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ H, W ≤ 10. 1 ≤ M ≤ 100. 0 ≤ 모든 높이 ≤ 100. 시간 제한: 30초.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ H, W ≤ 20. 1 ≤ M ≤ $10^{15}$. 0 ≤ 모든 높이 ≤ $10^{15}$. 시간 제한: 60초.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 공백으로 구분된 세 정수 H, W, M이 있는 줄로 시작한다. 앞의 두 정수는 지도의 크기를 나타내고, 세 번째 정수는 위에서 설명한 대로 한 칸이 하루에 침식될 수 있는 최대량을 나타낸다. 이어서 H개의 줄이 주어지며, 각 줄에는 공백으로 구분된 W개의 정수가 있다. $j^{th}$번째 줄의 $i^{th}$번째 정수는 (i, j)에 있는 칸의 높이를 나타낸다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작), y는 섬 전체가 침식되는 데 걸리는 일수이다.

두 번째 케이스에서 물의 높이는 다음과 같다: 3 8 10 11 10 8 7 7 7 12 8 8 6 9 11 9 8 4

하루가 지나면 섬은 다음과 같아진다: 0 5 7 8 7 5 4 5 2 9 8 5 3 6 8 6 5 1

그리고 둘째 날이 지나면 다음과 같다: 0 2 4 5 4 2 1 4 2 6 5 2 0 3 5 3 2 0

그리고 셋째 날에는 다음과 같다: 0 0 1 2 1 0 0 1 2 3 2 0 0 0 2 0 0 0

넷째 날이 지나면 아틀란티스인들의 상황은 절박해진다: 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0

마침내 다섯째 날에 마지막 칸이 침식되어 사라진다. 아틀란티스는 닷새 동안 버텼다. 아마 도시를 흑설탕으로 짓지 말았어야 했다.