아틀란티스에 내리는 비 (Small)

아틀란티스 섬에 비가 내린다. 이 비는 섬의 땅을 남김없이 깎아 없앤다. 주민을 대피시키려면 그때까지 며칠이 걸리는지 알아야 한다.

섬의 지도가 있다. 지도는 격자 모양이고, 각 칸에는 그 칸의 땅 높이가 해수면 기준 미터 단위로 적혀 있다. 지도 밖에 있는 칸은 높이가 모두 0이다. 높이가 0인 칸은 물이고, 높이가 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(\mathrm{WaterLevel}(S) - \mathrm{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이 될 때까지 며칠이 걸리는지 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 세 정수 $H$, $W$, $M$이 공백으로 구분되어 주어진다. $H$와 $W$는 지도의 세로와 가로 크기이고, $M$은 한 칸이 하루에 깎일 수 있는 최대 높이다. 이어지는 $H$개의 줄에는 각각 $W$개의 정수가 주어진다. $i$번째 줄의 $j$번째 정수는 $i$행 $j$열 칸의 높이다.

제한

• $1 \le T \le 40$
• $1 \le H, W \le 10$
• $1 \le M \le 100$
• 모든 높이는 0 이상 100 이하이다.

각 테스트 케이스마다 "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

닷새째에 그 칸까지 깎여 사라지므로 아틀란티스는 5일을 버틴다.