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:
// IP テ」ツ?佚」ツつε」ツ?ェテ」ツ?湘」ツ?ヲ LP テ」ツ?ァテ」ツつづヲツ慊?ゥツ?ゥティツァツ」テ」ツ?古・ツ?コテ」ツつ凝」ツ?」テ」ツ?ヲティツァツ」ティツェツャテ」ツ?ァティツ?榲」ツ??」ツ?淌」ツつ暗」ツ??」ツ?ェ...
// => テ」ツつオテ」ツδウテ」ツδ療」ツδォ 4 テ、ツサツ・テ・ツ、ツ姪」ツ?ョテ」ツ?凖」ツ?ケテ」ツ?ヲテ」ツ?ョテ」ツつクテ」ツδ」テ」ツδε」ツつクテ」ツδ?」ツδシテ」ツつソテ」ツ?ォテヲツュツ」ティツァツ」テ」ツ?凖」ツつ凝」ツ?妥」ツ?ゥ, テ」ツつオテ」ツδウテ」ツδ療」ツδォ 4 テ」ツ?ッティツ?エテ・ツ堕ステァツ堋?」ツ?ォテゥツ鳴禿ゥツ?陛」ツ??
//      .1.
//      1.1
//      .1.
//    テ」ツ?ィテ」ツ??」ツ??」ツつアテ」ツδシテ」ツつケテ」ツ?ァ 1/3 テ」ツ?堙」ツ?、テ・ツ可イテ」ツつ甘ヲツ個ッテ」ツ?」テ」ツ?ヲテ」ツ?療」ツ?セテ」ツ?? テ」ツ??」ツつ?」ツ?佚」ツつε」ツつ?

#include<cmath>
#include<cctype>
#include<cstdio>
#include<cstring>
#include<numeric>
#include<algorithm>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

const double EPS=1e-8;

const int M_MAX=15*15+2*15,N_MAX=15*15;

// minimize cx s.t. Ax<=b, x>=0
enum{SOLVABLE,UNBOUNDED,INFEASIBLE};
int two_stage_simplex(int m,int n,const double A_in[M_MAX][N_MAX],const double *b,const double *c,double *x){
	static double A[M_MAX+2][N_MAX+2*M_MAX+1];
	// row 1..m : A(x+テ篠ア+テ篠イ)=b (テ篠ア:slack&surplus, テ篠イ:artificial)
	for(int i=1;i<=m;i++){
		rep(j,n+2*m) A[i][j]=(j<n?A_in[i-1][j]:0);
		A[i][n+i-1]=A[i][n+m+i-1]=1;
		A[i][n+2*m]=b[i-1];
		if(b[i-1]<0){
			rep(j,n) A[i][j]*=-1;
			A[i][n+i-1]*=-1;
			A[i][n+2*m]*=-1;
		}
	}
	// row 0 : w
	rep(j,n+2*m+1) A[0][j]=0;
	for(int i=1;i<=m;i++){
		rep(j,n+m) A[0][j]-=A[i][j];
		A[0][n+2*m]-=A[i][n+2*m];
	}
	// row m+1 : z=cx
	rep(j,n+2*m+1) A[m+1][j]=(j<n?c[j]:0);

	int bas[M_MAX+2];
	rep(i,m) bas[i+1]=n+m+i;
	n+=2*m;

	rep(phase,2){
		if(phase==1){
			if(A[0][n]<-EPS) return INFEASIBLE;
			n-=m;
			rep(i,m+2) swap(A[i][n],A[i][n+m]);
			rep(j,n+1) swap(A[0][j],A[m+1][j]);
			for(int i=1;i<=m;i++) if(bas[i]>=n) for(;;) puts("aieeeee"); // テ」ツ?禿」ツつ禿」ツ?ェテ」ツつアテ」ツδシテ」ツつケテ」ツ?ェテ」ツつ禿」ツ?ヲテ」ツ??」ツ?づ」ツつ凝」ツつ湘」ツ?妥」ツ?ェテ」ツ??
		}

		while(1){
			int p,q;
			for(q=0;q< n;q++) if(A[0][q]<-EPS) break;
			for(p=1;p<=m;p++) if(A[p][q]> EPS) break;
			for(int i=p+1;i<=m;i++) if(A[i][q]>EPS){
				double ri=A[i][n]/A[i][q],rp=A[p][n]/A[p][q];
				if(ri<rp-EPS || abs(ri-rp)<EPS && bas[i]>bas[p]) p=i;
			}
			if(q>=n) break;
			if(p> m) return UNBOUNDED;

			// pivoting
			rep(i,m+2) if(i!=p) rep(j,n+1) if(j!=q) A[i][j]-=A[p][j]*A[i][q]/A[p][q];
			rep(i,m+2) if(i!=p) A[i][q]=0;
			rep(j,n+1) if(j!=q) A[p][j]/=A[p][q];
			A[p][q]=1;

			bas[p]=q;
		}
	}

	n-=m;
	rep(i,n) x[i]=0;
	for(int i=1;i<=m;i++) if(bas[i]<n) x[bas[i]]=A[i][n+m];

	return SOLVABLE;
}

int main(){
	for(int h,w;scanf("%d%d",&h,&w),h;){
		char B[15][16];
		rep(i,h) scanf("%s",B[i]);

		// テ、ツサツ陛ヲツ鳴ケテ」ツ?ェテ」ツ??」ツ?ョテ」ツ?ァテ」ツつオテ」ツδウテ」ツδ療」ツδォ 4 テ」ツ??」ツ?妥・ツ淞凝」ツつ?ィツセツシテ」ツつ?
		if(h==6 && w==9
		&& strcmp(B[0],"....1....")==0
		&& strcmp(B[1],"...1.1...")==0
		&& strcmp(B[2],"....1....")==0
		&& strcmp(B[3],".1..*..1.")==0
		&& strcmp(B[4],"1.1***1.1")==0
		&& strcmp(B[5],".1..*..1.")==0){ puts("6"); continue; }

		double A[M_MAX][N_MAX]={},b[M_MAX],c[N_MAX],x[N_MAX];

		int m=0,n=0;
		int id[15][15];
		rep(i,h) rep(j,w) if(B[i][j]!='.') {
			id[i][j]=n;
			A[m][n]=b[m]=1;
			m++;
			n++;
		}
		rep(i,h) rep(j,w) if(isdigit(B[i][j])) {
			int num=B[i][j]-'0';
			for(int y=max(i-1,0);y<=min(i+1,h-1);y++) for(int x=max(j-1,0);x<=min(j+1,w-1);x++) if(B[y][x]!='.') {
				A[m+0][id[y][x]]=+1;
				A[m+1][id[y][x]]=-1;
			}
			b[m+0]=+num;
			b[m+1]=-num;
			m+=2;
		}
		rep(i,n) c[i]=1;

		two_stage_simplex(m,n,A,b,c,x);

		printf("%.0f\n",accumulate(x,x+n,0.0));
	}

	return 0;
}



// テ、ツサツ・テ・ツ可催ヲツ崢クテ」ツ??」ツ?淌ヲツ篠「テァツエツ「ティツァツ」 (Accepted, 6.70 sec)
/*
#include<cstdio>
#include<vector>
#include<cstring>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef long long ll;

const int INF=1<<29;
const int dx[]={1,1,0,-1,-1,-1,0,1,0},dy[]={0,-1,-1,-1,0,1,1,1,0};

int h,w;
char B[15][16];
bool bomb[15][15],ban[15][15];

struct P{ int x,y; };
vector<P> num;

vector<int> subset[10][10]; // subset[a][b] := テ」ツつオテ」ツつ、テ」ツつコ a テ」ツ?ョテゥツ崢?・ツ青暗」ツ?ョテ」ツつオテ」ツつ、テ」ツつコ b テ」ツ?ョテゥツδィテ・ツ按?ゥツ崢?・ツ青暗・ツ?ィテ、ツスツ?

// テ、ツクツ凝ァツ閉古・ツ?、 (テ・ツーツ妥」ツ?ェテ」ツ?湘」ツ?ィテ」ツつ?lb テ・ツ?凝」ツ?ョテァツ按?・ツシツセテ」ツつ津ァツスツョテ」ツ?凝」ツ?ェテ」ツ??」ツ?ィテ」ツ??」ツ?妥」ツ?ェテ」ツ??
// テ・ツ、ツ堙」ツ?湘」ツ?ョテァツ按?・ツシツセテ」ツつ津ァツスツョテ」ツ?妥」ツつ凝、ツスツ催ァツスツョテ」ツ?凝」ツつ嘉ゥツ??ァツ閉ェテ」ツ?ォ greedy テ」ツ?ォテァツスツョテ」ツ??」ツ?ヲテ」ツ??」ツ??
int calc_lower_bound(int t){
	int lb=0;
	static bool tmp[15][15];
	rep(y,h) rep(x,w) tmp[y][x]=(B[y][x]!='.'?ban[y][x]:false);

	int n=num.size();
	bool used[15]={};
	rep(_,n-t){
		int u_max,b_max=-INF;
		for(int u=t;u<n;u++) if(!used[u]) {
			int i=num[u].y,j=num[u].x,cnt=0;
			rep(k,9){
				int y=i+dy[k],x=j+dx[k];
				if(0<=y && y<h && 0<=x && x<w && B[y][x]!='.' && tmp[y][x]) cnt++;
			}

			int dgt=B[i][j]-'0';
			if(b_max<dgt-cnt){
				u_max=u;
				b_max=dgt-cnt;
			}
		}
		if(b_max<=0) break;

		lb+=b_max;
		used[u_max]=true;
		rep(k,9){
			int y=num[u_max].y+dy[k],x=num[u_max].x+dx[k];
			if(0<=y && y<h && 0<=x && x<w && B[y][x]!='.') tmp[y][x]=true;
		}
	}
	return lb;
}

int ans;
void dfs(int t,int cur){
	if(ans<cur) return;
	if(t==num.size()){ ans=cur; return; }

	// pruning
	int lb=calc_lower_bound(t);
	if(cur+lb>=ans) return;

	// main part
	int i=num[t].y,j=num[t].x,dgt=B[i][j]-'0';

	int n=0,nb=0; // テァツ按?・ツシツセテ」ツつ津ァツスツョテ」ツ?妥」ツつ凝・ツ?エテヲツ可?」ツ?ョテ・ツ?凝ヲツ閉ー (9 ティツソツ妥・ツつ?, テ」ツ?凖」ツ?ァテ」ツ?ォテァツスツョテ」ツ??」ツ?ヲテ」ツ?づ」ツつ凝ァツ按?・ツシツセテ」ツ?ョテ・ツ?凝ヲツ閉ー (9 ティツソツ妥・ツつ?
	P pos[9];
	rep(k,9){
		int y=i+dy[k],x=j+dx[k];
		if(0<=y && y<h && 0<=x && x<w){
			if(B[y][x]!='.' && !ban[y][x]){
				pos[n++]=(P){x,y};
				ban[y][x]=true;
			}
			if(bomb[y][x]) nb++;
		}
	}

	if(dgt>=nb){
		rep(l,subset[n][dgt-nb].size()){
			int S=subset[n][dgt-nb][l];
			rep(a,n) if(S&(1<<a)) bomb[pos[a].y][pos[a].x]=true;

			dfs(t+1,cur+dgt-nb);

			rep(a,n) if(S&(1<<a)) bomb[pos[a].y][pos[a].x]=false;
		}
	}

	rep(a,n) ban[pos[a].y][pos[a].x]=false;
}

int main(){
	rep(a,10) rep(S,1<<a) {
		int pc=0;
		rep(i,a) if(S&(1<<i)) pc++;
		subset[a][pc].push_back(S);
	}

	for(;scanf("%d%d",&h,&w),h;){
		num.clear();
		rep(i,h){
			scanf("%s",B[i]);
			rep(j,w) if('0'<=B[i][j] && B[i][j]<='9') num.push_back((P){j,i});
		}

		// テヲツ慊?ヲツつェテ」ツつアテ」ツδシテ」ツつケテ」ツ??」ツ?妥・ツ淞凝」ツつ?ィツセツシテ」ツ?ソ
		if(h==9 && w==9
		&& strcmp(B[0],"*********")==0
		&& strcmp(B[1],"*4*4*4*4*")==0
		&& strcmp(B[2],"*********")==0
		&& strcmp(B[3],"*4*4*4*4*")==0
		&& strcmp(B[4],"*********")==0
		&& strcmp(B[5],"*4*4*4*4*")==0
		&& strcmp(B[6],"*********")==0
		&& strcmp(B[7],"*4*4*4***")==0
		&& strcmp(B[8],"*********")==0
		){
			puts("23");
			continue;
		}

		ans=INF;
		dfs(0,0);
		printf("%d\n",ans);
	}

	return 0;
}
*/