Problem: You got an old map, which turned out to be drawn by the infamous pirate "Captain Q". It shows the locations of a lot of treasure chests buried in an island.

The map is divided into square sections, each of which has a digit on it or has no digit. The digit represents the number of chests in its 9 neighboring sections (the section itself and its 8 neighbors). You may assume that there is at most one chest in each section.

Although you have the map, you can't determine the sections where the chests are buried. Even the total number of chests buried in the island is unknown. However, it is possible to calculate the minimum number of chests buried in the island. Your mission in this problem is to write a program that calculates it.



Input

The input is a sequence of datasets. Each dataset is formatted as follows.

h w
map

The first line of a dataset consists of two positive integers h and w. h is the height of the map and w is the width of the map. You may assume 1≤h≤15 and 1≤w≤15.

The following h lines give the map. Each line consists of w characters and corresponds to a horizontal strip of the map. Each of the characters in the line represents the state of a section as follows.

'.': The section is not a part of the island (water). No chest is here.

'*': The section is a part of the island, and the number of chests in its 9 neighbors is not known.

'0'-'9': The section is a part of the island, and the digit represents the number of chests in its 9 neighbors.

You may assume that the map is not self-contradicting, i.e., there is at least one arrangement of chests. You may also assume the number of sections with digits is at least one and at most 15.

A line containing two zeros indicates the end of the input.

Output

For each dataset, output a line that contains the minimum number of chests. The output should not contain any other character.

Examples

Input

5 6


Output

6


Input

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


Output

6
5
5
6
23

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 20


struct LOC{
	void set(int arg_row,int arg_col){
		row = arg_row;
		col = arg_col;
	}
	int row,col;
};

int H,W;
int num_number_cell,index_number_cell[NUM][NUM];
int diff_row[9] = {-1,-1,-1,0,0,0,1,1,1},diff_col[9] = {-1,0,1,-1,0,1,-1,0,1};
int ans;
bool is_adj[NUM][NUM];
char first_map[NUM][NUM],base_map[NUM][NUM];
ll table[NUM];
map<ll,int> MAP[NUM][NUM];
LOC loc[NUM];

bool rangeCheck(int row,int col){
	if(row >= 0 && row <= H-1 && col >= 0 && col <= W-1){
		return true;
	}else{
		return false;
	}
}

//最大15個の数字マスを、数値化して返却
ll getCode(ll tmp_array[NUM]){

	ll ret = 0;

	for(int i = 0; i < num_number_cell; i++){
		ret = 10*ret+tmp_array[i];
	}

	return ret;
}

bool is_num(char ch){
	return ch >= '0' && ch <= '9';
}

void recursive(int row,int col,int num_chest,ll tmp_array[NUM]){

	if(num_chest >= ans)return;

	//探索終了
	if(row == H){

		ans = num_chest;
		return;
	}

	//状態を保存
	ll tmp_code = getCode(tmp_array);
	auto at = MAP[row][col].find(tmp_code);

	if(at == MAP[row][col].end()){

		MAP[row][col][tmp_code] = num_chest;

	}else{

		if(MAP[row][col][tmp_code] <= num_chest){ //辿れる未来は同じなので、過去最適でないなら打ち切り
			return;
		}
		MAP[row][col][tmp_code] = num_chest;
	}

	//何もせずに次へ
	if(rangeCheck(row-1,col-1) == true && is_num(base_map[row-1][col-1]) == true &&
			tmp_array[index_number_cell[row-1][col-1]] >= 1){
		//Do nothing(左上に数字マスがあって、それが1以上なら、もう減らせないので遷移しない)
	}else{

		int next_row = row,next_col = col;
		next_col++;
		if(next_col == W){
			next_col = 0;
			next_row++;
		}
		recursive(next_row,next_col,num_chest,tmp_array);
	}

	if(!is_adj[row][col])return; //数字に隣接しないマスならreturn

	ll next_array[NUM];
	for(int i = 0; i < num_number_cell; i++){
		next_array[i] = tmp_array[i];
	}

	//★今回のマスに箱を配置する★
	bool FLG = true;
	int adj_row,adj_col;

	for(int i = 0; i < 9; i++){

		adj_row = row+diff_row[i];
		adj_col = col+diff_col[i];

		if(!rangeCheck(adj_row,adj_col))continue;

		if(is_num(base_map[adj_row][adj_col])){

			if(tmp_array[index_number_cell[adj_row][adj_col]] == 0){

				FLG = false;
				break;

			}else{

				next_array[index_number_cell[adj_row][adj_col]] =  tmp_array[index_number_cell[adj_row][adj_col]]-1;
			}
		}
	}

	if(FLG){

		if(rangeCheck(row-1,col-1) == true && is_num(base_map[row-1][col-1]) == true &&
				next_array[index_number_cell[row-1][col-1]] >= 1){
			//Do nothing(左上に数字マスがあって、それが1以上なら、もう減らせないので遷移しない)
		}else{

			int next_row = row,next_col = col;
			next_col++;
			if(next_col == W){
				next_col = 0;
				next_row++;
			}
			recursive(next_row,next_col,num_chest+1,next_array);
		}
	}
}

void func(){

	num_number_cell = 0;

	//マップ情報の取得
	for(int row = 0; row < H; row++){
		scanf("%s",first_map[row]);
	}

	//枝刈りしやすいように、ダミーセルでマップを囲う
	for(int row = 0; row < H+2; row++){
		for(int col = 0; col < W+2; col++){
			base_map[row][col] = '.';
			index_number_cell[row][col] = -1;
		}
	}

	ll first_tmp_array[NUM];

	for(int row = 0; row < H; row++){
		for(int col = 0; col < W; col++){
			base_map[row+1][col+1] = first_map[row][col];
			if(is_num(base_map[row+1][col+1])){
				loc[num_number_cell].set(row+1,col+1);
				first_tmp_array[num_number_cell] = base_map[row+1][col+1]-'0';
				index_number_cell[row+1][col+1] = num_number_cell++;
			}
		}
	}

	//★ダミーセルの分★
	H += 2;
	W += 2;

	for(int row = 0; row < H; row++){
		for(int col = 0; col < W; col++){
			MAP[row][col].clear();
		}
	}

	//9近傍に数字マスがあるセルを洗い出す
	int adj_row,adj_col;

	int count = 0;

	for(int row = 0; row < H; row++){
		for(int col = 0; col < W; col++){

			if(base_map[row][col] == '.'){ //水
				is_adj[row][col] = false;
				continue;
			}

			if(is_num(base_map[row][col])){
				count++;
				is_adj[row][col] = true;
				continue;
			}

			is_adj[row][col] = false;

			for(int i = 0; i < 9; i++){

				adj_row = row+diff_row[i];
				adj_col = col+diff_col[i];

				if(!rangeCheck(adj_row,adj_col))continue;

				if(is_num(base_map[adj_row][adj_col])){
					count++;
					is_adj[row][col] = true;
					break;
				}
			}
		}
	}

	ans = H*W;

	recursive(0,0,0,first_tmp_array);

	printf("%d\n",ans);

}

/*★★マップ上の数字を、「埋まっている場所未判明の、隣接9近傍にある箱の数」と解釈する★★*/

int main(){

	while(true){
		scanf("%d %d",&H,&W);
		if(H == 0 && W == 0)break;

		func();
	}

	return 0;
}