지뢰 찾기

지뢰 찾기 지도는 N x N 크기의 정사각형 격자이다. 각 칸에는 지뢰가 없거나, 1개 이상 9개 이하의 지뢰가 묻혀 있다. 지뢰가 없는 칸은 입력에서 .으로 표시된다.

지뢰가 없는 어떤 칸에 적어야 하는 숫자는 그 칸과 인접한 최대 여덟 칸에 묻힌 지뢰의 총개수이다. 격자 밖에 있는 칸은 고려하지 않는다.

일반적인 지뢰 찾기와 달리 이 문제에서는 한 칸에 여러 개의 지뢰가 있을 수 있다. 따라서 인접한 지뢰 칸의 개수가 아니라, 인접한 칸들에 들어 있는 지뢰의 총합을 계산해야 한다.

지도의 지뢰 정보가 주어질 때, 완성된 지뢰 찾기 지도를 출력하는 프로그램을 작성하시오.

첫째 줄에 정수 N이 주어진다. (1 <= N <= 1,000)

다음 N개의 줄에는 지뢰 찾기 지도의 정보가 주어진다. 각 줄은 길이가 N인 문자열이며, 각 문자는 . 또는 숫자이다. .은 지뢰가 없는 칸을 뜻하고, 숫자는 그 칸에 묻힌 지뢰의 개수를 뜻한다.

완성된 지뢰 찾기 지도를 N개의 줄에 출력한다.

지뢰가 있는 칸은 *로 출력한다. 지뢰가 없는 칸에는 인접한 칸들에 묻힌 지뢰의 총개수를 출력하되, 그 값이 10 이상이면 M을 출력한다. 출력 지도는 숫자, M, *로만 이루어져야 한다.