Rains Over Atlantis (Small)

Rain falls on the island of Atlantis and will erode all of its land down to nothing. To plan the evacuation, you need to know how soon that happens.

You have a map of Atlantis. The map is a grid, and each square holds the height of the land in that square, in metres above sea level. Every square outside the map has height 0. A square of height 0 is water, and a square of greater height is land. No square has a height below 0.

Water flows from a source square to a target square if the two squares share an edge and the water level of the target is lower than or equal to the water level of the source.

The rain falls very fast, so if the rain water in a square has nowhere to flow, water piles up in that square until there is a square it can flow to. Squares outside the map accept any amount of flow. For example, this map

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

fills up at once. Call the height of the water in a square plus the height of the land its water level. The water levels are

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

The 0 in the middle of the land is water, but it is cut off from the outside of the map, so water only piles up there. The 0 on the left edge does reach the outside of the map, so the water from the 8 next to it flows through that square and out.

Water levels decide where water flows. When one square can send its water to several squares, the water flows to the square with the lowest water level. A tie for the lowest water level does not change the result.

Erosion now begins. Each day a square loses height according to how water flows out of it. If water flows from S to T, the height of S drops by $\min(\mathrm{WaterLevel}(S) - \mathrm{WaterLevel}(T), M)$. All erosion happens at the same moment, at the end of the day. With $M = 5$, the map above erodes to

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

After a day of erosion the extra water drains away: a square whose water level is higher than a neighbour's water level loses water until the two are equal, and water piles up again the way it did on the first day. The water levels of this map become

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

After another day of erosion the map looks like this.

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

The Atlanteans have to leave in a hurry. Work out how many days it takes for every height to erode to 0.

The first line of the input gives the number of test cases $T$. Each test case begins with a line containing three space separated integers $H$, $W$ and $M$. The first two give the size of the map, and the third is the largest amount a square can erode in one day. $H$ lines follow, each containing $W$ integers. The $j$-th integer on the $i$-th of those lines is the height of the square in row $i$ and column $j$.

Limits

• $1 \le T \le 40$
• $1 \le H, W \le 10$
• $1 \le M \le 100$
• Every height is between 0 and 100, inclusive.

For each test case, output one line containing "Case #x: y", where x is the case number starting from 1 and y is the number of days it takes to erode the whole island.

In the second test case of the example, the water levels start out like this.

3 8 10 11 10 8
7 7 7 12 8 8
6 9 11 9 8 4

After one day the island looks as follows.

0 5 7 8 7 5
4 5 2 9 8 5
3 6 8 6 5 1

After the second day:

0 2 4 5 4 2
1 4 2 6 5 2
0 3 5 3 2 0

After the third day:

0 0 1 2 1 0
0 1 2 3 2 0
0 0 2 0 0 0

After the fourth day a single square is left.

0 0 0 0 0 0
0 0 1 0 0 0
0 0 0 0 0 0

On the fifth day that square erodes away, so Atlantis lasts five days.