Open Contest 2006

The puzzle “Minesweeper” is based on the widely known game "Minesweeper", available for almost all MS Windows users, starting from version 2.0. The goal is simple -- to discover (or more precisely: uncover) the positions of all mines in rectangular grid. After a field without a mine on it is uncovered, the revealed value shows how many neighboring cells (at most 8) are occupied by mines. In the puzzle, just as in the game, you know the total number of mines on the board. But unlike in the game, you are not asked to risk your life by uncovering fields. Instead, you are given a list of uncovered fields (without mines, with numbers on them) and are requested to hazard a guess at the locations of all the mines.

Input

t – the number of test cases, and then t tests follow [t <= 500].
Each test starts with three integers H, W, N equal to the height, width and number of mines on the grid, respectively [5 <= H, W <= 50] [1 <= N <= H*W]
Then exactly H lines follow, each of them consisting of W symbols.
The description of the grid consists of ASCII characters: '1'-'8' – the number of mines in neighbouring cells and '.' – a cell with unknown content. You can be sure that no other characters are present in the grid description.

Output

For each test you should output the text char Y in a separate line if you wish to solve this test, or char N otherwise. In the former case, you should then output a grid with the same size as that of the test, with mines placed on it in stead of some characters '.'. Mines are defined by the character 'X'. The number of mines should be equal to the number of mines N given in the test description.

Score

The score of your program is the total of scores awarded for individual test cases. The score for a test is equal to the number of cells around which mines are placed correctly (i.e. the number of mines is equal to the integer displayed in the cell). The number of cells for which mines are placed incorrectly is subtracted from this sum. Negative test case scores are treated as zero scores. If a test case is solved entirely correctly, the score is multiplied by 10.
Additional info: The score is given as xxx.aaa, where aaa is number of tests solved entirely correctly.

Example

Input:

2
8 8 19
........
2323..2.
..23...2
.3..33..
2.321...
....1.32
.3...3..
1...2..2
6 6 6
111.1.
1.2121
112.21
..112.
122111
1..1..

Output:

Y
X.X.....
2323X.2X
.X23XX.2
X3X.33.X
2.321X.X
.XX.1.32
.3...3X.
1X.X2XX2
Y 
111X1.
1X2121
112X21
..112.
122111
1.X1XX

Score:

The first test is solved entirely correctly, for which 23*10 = 230 points are awarded. The score for the second test case is equal to 10-15 = -5, treated as 0. The total score is thus 230.001.