Minesweeper

A minesweeper map is an N x N square grid. Each cell either has no mine, or contains between 1 and 9 mines. A cell without a mine is written as . in the input.

For a cell without a mine, the number written in that cell must be the total number of mines in the up to eight adjacent cells. Cells outside the grid are ignored.

Unlike ordinary minesweeper, this problem allows several mines in one cell. Therefore, you must add the mine counts stored in adjacent cells, not merely count how many adjacent cells contain mines.

Given the mine information for the map, write a program that prints the completed minesweeper map.

The first line contains an integer N. (1 <= N <= 1,000)

Each of the next N lines contains the mine information for the map. Each line is a string of length N, and every character is either . or a digit. . means the cell has no mine, and a digit means the number of mines in that cell.

Print the completed minesweeper map in N lines.

Print * for a cell that contains mines. For a cell without a mine, print the total number of mines in its adjacent cells; if that value is at least 10, print M instead. The output map must contain only digits, M, and *.