你得到了一张古老的地图，它是由臭名昭著的海盗“Q船长”绘制的。地图上标示了埋藏在一个岛屿上的许多宝箱的位置。

地图被划分为正方形区域，每个区域上可能标有一个数字，也可能没有。数字表示其自身及周围 8 个相邻区域（共 9 个区域）内埋藏的宝箱总数。你可以假设每个区域内最多只能埋藏一个宝箱。

虽然你拥有这张地图，但你无法确定宝箱具体埋藏在哪些区域。甚至岛上埋藏的宝箱总数也是未知的。然而，我们可以计算出岛上埋藏的宝箱的最小可能数量。你的任务是编写一个程序来计算这个最小值。

输入格式

输入包含多组测试数据。每组数据的格式如下：

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 0）时，表示输入结束。

输出格式

对于每组测试数据，输出一行，包含宝箱的最小可能数量。输出中不应包含任何其他字符。

样例

输入样例 1

5 6
*2.2**
..*...
..2...
..*...
*2.2**
6 5
.*2*.
..*..
..*..
..2..
..*..
.*2*.
5 6
.1111.
**...*
33....
**...0
.*2**.
6 9
....1....
...1.1...
....1....
.1..*..1.
1.1***1.1
.1..*..1.
9 9
*********
*4*4*4*4*
*********
*4*4*4*4*
*********
*4*4*4*4*
*********
*4*4*4***
*********
0 0

输出样例 1

6
5
5
6
23