There's a popular puzzle game where you try to uncover mines on a grid. EasySweeper is a version of this game, but it's a little different.

EasySweeper is played on a grid, and each grid square either contains a mine or it doesn't. When you start you get a partially filled-in grid of integer clues like the ones shown below. Think of a clue as being at the center of a ~3 \times 3~ area. The clue itself represents the total number of mines in that ~3 \times 3~ area.

The pictures to the right show two of the ~126~ possible arrangements of mines represented by the 5 in the top right corner of the example (a black square represents a grid space with a mine in it and a shaded square represents an empty grid space). Only one of the ~126~ possible arrangements will work when all the other clues are taken into account (in fact, the second one shown below can already be ruled out because of the 1 clue above and to the left of the 5). Your task is to figure out an arrangement of mines that satisfies all the clues on the board at once.

This game is called EasySweeper because solving the puzzles will never require any advanced logic or guesswork.

For example in the puzzle shown, there must be mines in all the grid squares around the 9 and around the 6 on the bottom row. Once you've marked those squares as containing a mine, you can see that the 7 just above the 6 you filled in is satisfied – you have found all ~7~ mines. That means there are no mines in the remaining two places. You can continue like that until you find the unique solution to the puzzle. This process is diagrammed below.

the starting board…

	4		1
				5
5		6	4
	9			7
		8	7		5
3			6

~\Longrightarrow~

fill in around the 9…

	4		1
				5
5		6	4
	9			7
		8	7		5
3			6

~\Longrightarrow~

fill in around the 6…

	4		1
				5
5		6	4
	9			7
		8	7		5
3			6

~\Longrightarrow~

the 7 is done…

	4		1
				5
5		6	4
	9			7
		8	7		5
3			6

The input will contain ~5~ test cases. Each test case consists of ~N~ lines of ~N~ characters, representing an ~N \times N~ puzzle grid ~(5 \le N \le 20)~. Each character will either be a clue from 0 to 9 or it will be a hyphen character - (ASCII code ~45~). Your job is to find the unique solution for the puzzle and print it in the format shown below, where an uppercase M stands for a mine and a dot character for no mine. You should separate each board in your output file by a blank line, but there will be no blank lines separating boards in the input file.

To help the judges, you should configure your IDE so that its text output is displayed in a fixed-width font like Courier New. If you can't do that, you can cut and paste the output into notepad or a similar text editor that displays in a fixed-width font.

Note that there are only two test cases in the sample data, but the real data files will contain ~5~ test cases each.

Sample Input

-4-1--
----5-
5-64--
-9--7-
--87-5
3--6--
2-20---33-
3-2---3---
-2----222-
-210---3-3
2-1--6-5-4
23--44---4
---5-42---
1-5--1-02-
----2-1--3
0-1-01-1--

Sample Output

MMM..M
.M...M
MMMMMM
MMM..M
MMMMMM
.MMMMM
.M...MMM.M
.M......M.
M........M
.....MM...
.M...M.MMM
M...MMM.MM
..MM......
.M.MM....M
..M......M
......M..M

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org