WinMine

Time Limit: 10 Seconds    Memory Limit: 32768 KB
Special Judge

Background:

This is a popular game which requires the player to find out all hidden mines without ever stepping onto a single mine by mistake. By clicking on a grid, it is unveiled to the player in one of these ways:

  • Blank - this grid is not mine (and so you have safely discovered it), and there is no mine in the grids around it.
  • Digit 1 to 8 - this grid is not mine, and there are that many mines (including hidden and unveiled mines), as the digit specify, around it.
  • Mine with red background - this grid is a mine and it has just been detonated so the player loses on it.

Here by 'around' we mean the grids that can be moved vertically, horizontally or diagonally, one step but not off the board, from a current grid.

The player can also mark a grid with a right-mouse-button click on it. If the number of marked grids around a digit grid equals the digit itself, the player can click on the digit grid with left and right mouse buttons together to show all its neighbors (so in this way you can unveil mines without detonating them). If the mark are all on mines correctly, the game goes on, or a mistaken mark will trigger a mine and it is a lost game.

After the player distinguish all the mine and non-mine grids, the game is won and the complete mine positions will be shown.

Here we expect a program to unveil as many grids as possible, taking a game board as input, which gives those grids that are already unveiled. As people can take all different approaches to solve the game, we give a tolerance so if the answer is safe (not detonating any mine) and not less than our standard answer less the tolerance, we assume it a good answer.

Input

One integer in the first line, followed by a blank line, stating the number of test cases. There will be not more than 256 tests.

For each test case, the first line is two integers 'rows' and 'cols' (4 <= rows, cols <= 20) stating the number of rows and columns respectively of the game board. Then 'rows' lines follow each with 'cols' characters describing the game board, in which, a '.' is a blank grid unveiled, a digit 1 to 8 is a digit grid unveiled, a '*' is a mine unveiled, and a '-' is a hidden grid that we expect you to explore. Then an integer 'tol' is given, stating the least number of grids you should unveil. Hence, if your answer is safe (no mine detonated, and does not violate the game board given) and not less than 'tol', the answer will be accepted. We expect your answer to be better than the standard one, i.e. more grids unveiled than we can do! You can assume that the given board configuration is valid, that, 'mines' will not be greater than the maximum mines possibly can be in those hidden grids.

There are cases that some mines may be there but you can't determined it and these grids shall not be unveiled in your output because there are possibility of ending the game in loss or we may misguide the sweeper and we do not want to take this risk. Such a case is shown in the second sample.

You can assume the game board given is consistent, that, the unveiled grids are all shown as they should be, a blank will be a blank and a digit will be a digit.

The test cases will be separated by a single blank line.

Output

The game board with the mines you have discovered marked with '*', and '.' if you determine that there is not a mine (you needn't output the number of mines around it, just '.' is ok), the rest grids consistent with the board given.

Separate test cases with a single blank line.

Sample Input


4

4 4
....
....
11..
-1..
1

4 4
....
....
---.
-1-.
0

4 4
....
....
11..
-1..
0

20 20
1-3-*--**--3-23*-3--
3*-6-*--3-*-*-*-*---
*--**5---2*5-*---*-2
3-5*-**-224*-5--45-*
-*3---6433*-*3*4----
----4*--*---7*5**---
*--1-----*6--**--7*-
3*3-3-5-6---6-55-**-
----2----***--**5--2
-5-5434*--56-6---*--
-***-*5-2-**-*-*--*-
-**3--*--2-6--6-----
--53------4------2-*
*5*--4-*--4**-6-33-*
---5------4--*-4--*3
--*--53-1-4--------*
-4*-**11-3**--33-2--
2*3-2-2----**-*3-2-2
3-4-2--*43-*34--3---
2---2*-*2--212*-3--2
72

Sample Output

....
....
11..
*1..

....
....
---.
-1-.

....
....
11..
-1..

1.3**--**.*3.23*-3--
3**6-*-.3.*.*.***---
**-**5-*.2*5***--*-2
3.5*-***224*.5.-45-*
.*3---6433***3*4----
----4*--*--*7*5**---
*..1-----*6****.*7*-
3*3.3.5-6---6-55***-
*.**2**.-***--**5--2
.5*5434*-.56-6---*--
.***.*5-2.**-*-*--*-
-**3.-*--2-6--6-----
-*53.-----4------2-*
*5**.4-*--4**-6-33.*
---5------4--*-4--*3
--*--53.1.4-------.*
-4*.**11.3**--33-2--
2*3.2.2.**.**.*3-2-2
3*4.2..*43-*34*-3---
2*.*2*-*2.-212*-3--2
Submit

Source: ZOJ 3rd Anniversary Contest