Problem H
Watersheds

Geologists sometimes divide an area of land into different regions based on where rainfall flows down to. These regions are called drainage basins.

Given an elevation map (a 2-dimensional array of altitudes), label the map such that locations in the same drainage basin have the same label, subject to the following rules.

• From each cell, water flows down to at most one of its 4 neighboring cells.

• For each cell, if none of its 4 neighboring cells has a lower altitude than the current cell’s, then the water does not flow, and the current cell is called a sink.

• Otherwise, water flows from the current cell to the neighbor with the lowest altitude.

• In case of a tie, water will choose the first direction with the lowest altitude from this list: North, West, East, South.

Every cell that drains directly or indirectly to the same sink is part of the same drainage basin. Each basin is labeled by a unique lower-case letter, in such a way that, when the rows of the map are concatenated from top to bottom, the resulting string is lexicographically smallest. (In particular, the basin of the most North-Western cell is always labeled ‘a’.)

Input

The first line of the input file will contain the number of maps $T, 1 \le T \le 100$. $T$ maps will follow, each starting with two integers on a line – $H$ and $W$ – the height and width of the map, in cells. You can assume that $1 \le H, W \le 100$. The next $H$ lines will each contain a row of the map, from north to south, each containing $W$ integers, from west to east, specifying the altitudes of the cells. All altitudes are at least 0 and at most $10\, 000$. You can assume that there will be at most 26 basins.

Output

For each test case, output $1+H$ lines. The first line must be of the form “Case #$X$:”, where $X$ is the test case number, starting from 1. The next $H$ lines must list the basin labels for each of the cells, in the same order as they appear in the input.

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

Case #1:
a b b
a a b
a a a
Case #2:
a a a a a a a a a b
Case #3:
a a a
b b b
Case #4:
a a a a a
a a b b a
a b b b a
a b b b a
a a a a a
Case #5:
a b c d e f g h i j k l m
n o p q r s t u v w x y z