Lápis de Cor

Roberto tem um conjunto de lápis com $10$ tons diferentes de uma mesma cor, numerados de $0$ a $9$. Numa folha de caderno quadriculado alguns quadrados foram coloridos inicialmente com o tom $0$. Roberto precisa determinar, para cada quadrado $Q$ não colorido, qual é a distância dele para o quadrado mais próximo de tom $0$. A distância entre dois quadrados é definida com o número mínimo de movimentos ortogonais (para: esquerda, direita, cima, baixo) para ir de um quadrado para o outro. O quadrado $Q$, então, deve ser colorido com o tom cuja numeração corresponde à distância determinada. Se a distância for maior ou igual a $9$, o quadrado deve ser colorido com o tom $9$. Seu programa deve colorir e imprimir a folha quadriculada dada na entrada.

Entrada

A primeira linha da entrada contém apenas um inteiro $N$, determinando as dimensões da folha quadriculada, $N \times N$. As $N$ linhas seguintes definem a folha inicialmente. Cada linha contém uma sequência de $N$ caracteres: ‘*’ se o quadrado não está colorido, e ‘0’ se está colorido com o tom $0$.

Saída

Seu programa deve imprimir o tabuleiro totalmente colorido, de acordo com a regra definida acima.

Restrições

• $3\leq N\leq 1\ 000$

Informações sobre a pontuação

• Em um conjunto de casos de teste somando $40$ pontos, $N \leq 100$.

Exemplos

Exemplo de entrada 1

8
**000***
********
*****0**
********
*****000
*******0
0******0
********

Exemplo de saída 1

21000123
32111123
43221012
34332111
23321000
12332110
01233210
12344321

Exemplo de entrada 2

3
***
***
**0

Exemplo de saída 2

432
321
210