Q 선장의 보물

오래된 지도 한 장을 손에 넣었는데, 알고 보니 악명 높은 해적 “Q 선장”이 그린 것이었습니다. 이 지도에는 어느 섬에 묻혀 있는 수많은 보물 상자의 위치가 표시되어 있습니다.

지도는 정사각형 칸들로 나뉘어 있으며, 각 칸에는 숫자가 하나 적혀 있거나 아무 숫자도 적혀 있지 않습니다. 칸에 적힌 숫자는 그 칸을 중심으로 한 인접 9개 칸(자기 자신과 8개의 이웃 칸)에 묻혀 있는 상자의 개수를 나타냅니다. 각 칸에는 상자가 최대 한 개만 묻혀 있다고 가정해도 됩니다.

지도가 있더라도 상자가 정확히 어느 칸에 묻혀 있는지는 알 수 없고, 섬에 묻힌 상자의 총 개수조차 알 수 없습니다. 하지만 섬에 묻혀 있을 수 있는 상자의 최솟값은 계산할 수 있습니다. 이 문제에서 여러분이 할 일은 그 최솟값을 계산하는 프로그램을 작성하는 것입니다.

입력은 여러 개의 데이터셋으로 이루어집니다. 각 데이터셋의 형식은 다음과 같습니다.

h w
map

각 데이터셋의 첫 번째 줄에는 두 양의 정수 $h$와 $w$가 주어집니다. $h$는 지도의 세로 길이(높이), $w$는 지도의 가로 길이(너비)입니다. $1 \le h \le 15$, $1 \le w \le 15$라고 가정해도 됩니다.

이어지는 $h$개의 줄에 지도가 주어집니다. 각 줄은 $w$개의 문자로 이루어지며, 지도의 한 가로줄에 해당합니다. 각 문자는 해당 칸의 상태를 다음과 같이 나타냅니다.

• . : 섬이 아닌 칸(바다)입니다. 이 칸에는 상자가 없습니다.
• * : 섬에 속하는 칸이며, 인접 9개 칸에 있는 상자의 개수는 알 수 없습니다.
• 0–9 : 섬에 속하는 칸이며, 이 숫자는 인접 9개 칸에 있는 상자의 개수를 나타냅니다.

지도는 모순되지 않는다고, 즉 조건을 만족하는 상자 배치가 적어도 하나는 존재한다고 가정합니다. 또한 숫자가 적힌 칸의 개수는 1개 이상 15개 이하라고 가정해도 됩니다.

두 개의 0으로만 이루어진 줄은 입력의 끝을 나타냅니다.

각 데이터셋마다 상자의 최소 개수를 한 줄에 출력합니다. 출력에는 그 외의 다른 문자가 포함되어서는 안 됩니다.