Minesweeper

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian. In case of any discrepancy, the Ukrainian version is authoritative.

Schoolchild, have you ever played "Minesweeper"?

In this problem, we consider a simpler version of this game.

There is a field with mines, which is given by a string of \(n\) characters. Each character of the string is either an empty cell (.) or a cell with a mine (*).

You don’t need to play Minesweeper now, you just need to determine for each empty cell of the field how many mines there are in adjacent cells.

Input

The first line contains an integer \(n\) — the size of the field.

Next, a string of \(n\) characters is given — the description of the field with mines. The \(i\)-th character of the string is . (dot) if the \(i\)-th cell is empty, or * if the \(i\)-th cell contains a mine.

Output

Output a string of \(n\) characters. If the \(i\)-th cell of the field contains a mine, then the \(i\)-th character of your answer must be *. If the \(i\)-th cell of the field is empty, then the \(i\)-th character of the answer must be the number of cells with mines adjacent to the \(i\)-th cell.

Constraints

\(1 \le n \le 10^5\).

Scoring consists of the following blocks:

• 1 point each for the examples from the statement,

• 6 points: the field contains no mines,

• 10 points: each cell of the field contains a mine,

• 80 points: no additional constraints.

You will receive the points for a block only if your program passes all tests in that block.

Samples

Input (stdin) сopy	Output (stdout) сopy
7 .*.*...	1*2*100

Input (stdin) сopy	Output (stdout) сopy
13 .***...**.*.*	1***101**2*2*

Input (stdin) сopy	Output (stdout) сopy
4 ....	0000

Input (stdin) сopy	Output (stdout) сopy
4 ****	****

Notes

In the first example, the answer is 1*2*100.

The first cell does not contain a mine. The first cell has only one adjacent cell — the second one, and the second cell contains a mine. Therefore, the first character of the answer is 1.

The second cell contains a mine, so the second character of the answer is *.

The third cell does not contain a mine. The third cell has two adjacent cells — the second and the fourth, which contain mines. Therefore, the third character of the answer is 2.

The fourth cell contains a mine, so the fourth character of the answer is *.

The fifth cell does not contain a mine. The fifth cell has two adjacent cells — the fourth and the sixth, and only the fourth contains a mine. Therefore, the fifth character of the answer is 1.

Neither the sixth cell nor any of its adjacent cells contain mines, so the sixth character of the answer is 0.

Neither the seventh cell nor its adjacent sixth cell contain mines, so the seventh character of the answer is also 0.