#include <bits/stdc++.h>
using namespace std;

#define dump(n) cout<<"# "<<#n<<'='<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;

const int INF=1e9;
const int MOD=1e9+7;
const double EPS=1e-9;

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}
template<typename T>
ostream& operator<<(ostream& os,const vector<T>& a){
	os<<'[';
	rep(i,a.size()) os<<(i?" ":"")<<a[i];
	return os<<']';
}

int getsize(const vvi& grid,int i0,int j0)
{
	int h=grid.size(),w=grid[0].size();
	int res=0;
	for(int k=1;k<=min(h-i0,w-j0);k++){
		bool ok=true;
		rep(i,k) rep(j,k) if(grid[i0+i][j0+j]==0)
			ok=false;
		if(!ok) break;
		res=k;
	}
	return res;
}

bool ok(const vvi& grid,const vvi& cur)
{
	int h=grid.size(),w=grid[0].size();
	rep(i,h) rep(j,w) if(grid[i][j]!=!!cur[i][j]) return false;
	return true;
}

//void dfs(const vvi& grid,const vvi& size,vvi& cur,int i,int j,int cnt,int& res)
//{
//	if(cnt>=res) return;
//	
//	int h=grid.size(),w=grid[0].size();
//	if(i==h){
//		//cout<<"--------------------"<<endl;
//		//rep(k,h) dump(cur[k]);
//		if(ok(grid,cur))
//			res=min(res,cnt);
//		return;
//	}
//	
//	if(size[i][j]==-1){
//		if(grid[i][j]==0 || cur[i][j])
//			dfs(grid,size,cur,i+(j+1)/w,(j+1)%w,cnt,res);
//	}
//	else{
//		if(cur[i][j])
//			dfs(grid,size,cur,i+(j+1)/w,(j+1)%w,cnt,res);
//		int sz=size[i][j];
//		rep(k,sz) rep(l,sz) cur[i+k][j+l]++;
//		dfs(grid,size,cur,i+(j+1)/w,(j+1)%w,cnt+1,res);
//		rep(k,sz) rep(l,sz) cur[i+k][j+l]--;
//	}
//}

void dfs(const vvi& grid,const vvi& size,const vector<pii>& cand,vvi& cur,int i,int j,int cnt,int& res)
{
	if(cnt>=res) return;
	
	int h=grid.size(),w=grid[0].size();
	if(i==h){
		//cout<<"--------------------"<<endl;
		//rep(k,h) dump(cur[k]);
		if(ok(grid,cur))
			res=min(res,cnt);
		return;
	}
	
	if(binary_search(all(cand),mp(i,j))){
		if(cur[i][j])
			dfs(grid,size,cand,cur,i+(j+1)/w,(j+1)%w,cnt,res);
		int sz=size[i][j];
		rep(k,sz) rep(l,sz) cur[i+k][j+l]++;
		dfs(grid,size,cand,cur,i+(j+1)/w,(j+1)%w,cnt+1,res);
		rep(k,sz) rep(l,sz) cur[i+k][j+l]--;
	}
	else{
		if(grid[i][j]==0 || cur[i][j]>0)
			dfs(grid,size,cand,cur,i+(j+1)/w,(j+1)%w,cnt,res);
	}
}

int main()
{
	for(int w,h;cin>>w>>h && w|h;){
		//dump(mp(h,w));
		vvi grid(h,vi(w));
		rep(i,h) rep(j,w) cin>>grid[i][j];
		
		// size[i][j]:(i,j)を左上とする正方形が極大であるとき，一辺の長さ
		vvi size(h,vi(w));
		rep(i,h) rep(j,w){
			int sz=getsize(grid,i,j);
			if(sz==size[i][j])
				size[i][j]=-1;
			else{
				rep(k,sz) rep(l,sz)
					size[i+k][j+l]=max(size[i+k][j+l],min(sz-k,sz-l));
			}
		}
		
		vector<vector<vector<pii>>> cover(h,vector<vector<pii>>(w));
		rep(i,h) rep(j,w) if(size[i][j]!=-1){
			int sz=size[i][j];
			rep(k,sz) rep(l,sz)
				cover[i+k][j+l].emplace_back(i,j);
		}
		
		vector<pii> must;
		rep(i,h) rep(j,w) if(cover[i][j].size()==1)
			must.push_back(cover[i][j][0]);
		sort(all(must));
		must.erase(unique(all(must)),end(must));
		
		vvi cur(h,vi(w));
		for(auto p:must){
			int i,j; tie(i,j)=p;
			int sz=size[i][j];
			rep(k,sz) rep(l,sz) cur[i+k][j+l]=1;
		}
		
		vector<pii> cand;
		rep(i,h) rep(j,w) if(cover[i][j].size() && !cur[i][j])
			for(auto p:cover[i][j]) if(!binary_search(all(must),p))
				cand.push_back(p);
		sort(all(cand));
		cand.erase(unique(all(cand)),end(cand));
		
		int res=INF;
		dfs(grid,size,cand,cur,0,0,0,res);
		//dump(must.size()); dump(res);
		cout<<must.size()+res<<endl;
	}
}

Measured memory_bytes: 1232