Rains Over Atlantis (Large)

Rain falls on the island of Atlantis, and it will erode every bit of the land away. To organize the evacuation, you need to know how soon that happens.

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

Water piles on top of the land. The height of the land in a cell plus the depth of the water on it is the water level of that cell, written $L(X)$ for cell $X$. Every cell outside the map has water level 0.

Water flows from a source cell to a target cell if the two cells 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 fast, so if the rain water in a cell has nowhere to flow, water piles up in that cell until there is a cell it can flow to. Cells outside the map accept any amount of flow. For example, this map fills up quickly:

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

The water levels become:

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 not connected to the outside of the map, so it only collects water. The 0 on the left edge is connected to the outside of the map, so the water from the 8 beside it flows through that cell and off the map.

Water levels decide the direction of the flow. When a source cell has several cells it can send water to, the water goes to the cell with the lowest water level. Ties do not matter, as you will see.

Now the erosion begins. Each day a cell loses height according to how water flows out of it. If water flows from $S$ to $T$, the height of $S$ drops by $\min(L(S) - L(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 excess water drains away: a cell whose water level is above a neighbour's water level loses water until the two levels match, and water piles up again the way it did on the first day. After the first day the water levels on this map are:

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. Find how many days it takes for every height to erode to 0.

The first line of the input has the number of test cases, $T$. $T$ test cases follow. Each test case begins with a line of three space separated integers $H$, $W$ and $M$. The first two are the size of the map, and the third is the largest height a cell can lose in one day. $H$ lines follow, each with $W$ space separated integers. The $i$-th integer on the $j$-th line is the height of the cell at $(i, j)$.

Limits

• $1 \le T \le 40$
• $1 \le H, W \le 20$
• $1 \le M \le 10^{15}$
• Every height is between $0$ and $10^{15}$, inclusive.

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

Take $M = 3$ and this map.

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

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, things are looking desperate for the Atlanteans.

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

On the fifth day the last cell erodes away. Atlantis lasted for five days. They probably should not have built their city out of brown sugar.