Bases and Plants

Manao is playing a strategy game on a rectangular map of size $N \times M$ , divided into $N \cdot M$ unit cells.
Some cells are buildable (denoted by .), while others are blocked (denoted by X).
Exactly one cell contains an enemy missile pod (denoted by M).

Manao must build exactly $K$ buildings on buildable cells.
There are two types of buildings:

B — a base (produces robots);
E — a power plant (produces energy for the robots).

Each building occupies exactly one cell. If at some point in the game, Manao has no bases or no plants left, the game is lost.

Let the missile pod be located at $(X, Y)$ and let a building be placed at $(i, j)$ .
Destroying that building costs the missile pod $(X - i)^{2} + (Y - j)^{2}$ units of fuel.

Once the buildings have been placed, the missile pod starts shooting at them.
The missile pod always tries to use the minimum amount of total fuel to defeat Manao - in other words, it will destroy either all bases, or all power plants, whichever is cheaper.

Your task is to place $K$ buildings and choose their types (B or E) so that this value $min (total cost to destroy all bases, total cost to destroy all power plants)$ is as large as possible.

Constraints

$1 \leq N, M \leq 50$
$1 \leq K \leq 100$

Input Format

The first line contains an integer $T$ — the number of test cases.

For each test case:

The first line contains three integers $N$ , $M$ , and $K$ .
The next $N$ lines each contain $M$ characters. Each character is:
- . — a buildable cell,
- X — a blocked cell,
- M — the missile pod.

Exactly one cell is M, and the number of buildable cells is at least $K$ .

Output Format

For each test case $i$ ( $1 \leq i \leq T$ ):
On the first line output Case #i: value, where value is the maximum possible energy the laser will have to spend (as defined above).
On the next $N$ lines output the map with exactly $K$ buildable cells replaced by
B (base) or E (power plant), showing one optimal arrangement. All other cells must remain unchanged.
If there are multiple optimal placements, output any of them.

Example

Input

2
3 3 3
M..
...
...
5 3 7
..X
X.X
M..
...
.XX

Output

Case #1: 8
M..
..E
.EB
Case #2: 13
EEX
XEX
M.B
.EB
BXX

Explanation

Sample 1: We have to choose whether we'll build a single base or a single power plant.
Whichever it will be, we have to place it as far away from the missile pod.

Sample 2: Some cells cannot be built on, forcing us to build structures closer to the missile pod.